버블 정렬

Python으로 배우는 자료구조와 알고리즘

Miriam Antona

Software engineer

정렬 알고리즘

  • {{1}}을(를) 깊이 학습
  • 정렬되지 않은 컬렉션을 오름차순/내림차순으로 정렬하는 방법 해결
  • 문제 복잡도 감소에 도움
  • 정렬 알고리즘 예:
    • 버블 정렬
    • 선택 정렬
    • 삽입 정렬
    • 병합 정렬
    • 퀵정렬
Python으로 배우는 자료구조와 알고리즘

버블 정렬

정렬되지 않은 숫자 목록의 개략도. 첫 번째 요소와 두 번째 요소를 가리키는 포인터가 하나씩 있다.

  • 첫 값 > 둘째 값
Python으로 배우는 자료구조와 알고리즘

버블 정렬

정렬되지 않은 숫자 목록의 개략도. 첫 번째 요소와 두 번째 요소를 가리키는 포인터가 하나씩 있다. 첫 번째와 두 번째 요소가 서로 바뀌었다.

  • 첫 값 > 둘째 값
    • 교환
  • 둘째 값 > 첫 값
    • 그대로 둠
Python으로 배우는 자료구조와 알고리즘

버블 정렬

정렬되지 않은 숫자 목록의 개략도. 두 번째 요소와 세 번째 요소를 가리키는 포인터가 하나씩 있다.

  • 첫 값 > 둘째 값
    • 교환
  • 둘째 값 > 첫 값
    • 그대로 둠
Python으로 배우는 자료구조와 알고리즘

버블 정렬

정렬되지 않은 숫자 목록의 개략도. 세 번째 요소와 네 번째 요소를 가리키는 포인터가 하나씩 있다.

  • 첫 값 > 둘째 값
    • 교환
  • 둘째 값 > 첫 값
    • 그대로 둠
Python으로 배우는 자료구조와 알고리즘

버블 정렬

정렬되지 않은 숫자 목록의 개략도. 세 번째 요소와 네 번째 요소를 가리키는 포인터가 하나씩 있다. 세 번째와 네 번째 요소가 서로 바뀌었다.

  • 첫 값 > 둘째 값
    • 교환
  • 둘째 값 > 첫 값
    • 그대로 둠
Python으로 배우는 자료구조와 알고리즘

버블 정렬

정렬되지 않은 숫자 목록의 개략도. 네 번째 요소와 다섯 번째 요소를 가리키는 포인터가 하나씩 있다.

  • 첫 값 > 둘째 값
    • 교환
  • 둘째 값 > 첫 값
    • 그대로 둠
Python으로 배우는 자료구조와 알고리즘

버블 정렬

정렬되지 않은 숫자 목록의 개략도. 네 번째 요소와 다섯 번째 요소를 가리키는 포인터가 하나씩 있다. 네 번째와 다섯 번째 요소가 서로 바뀌었다.

  • 첫 값 > 둘째 값
    • 교환
  • 둘째 값 > 첫 값
    • 그대로 둠
Python으로 배우는 자료구조와 알고리즘

버블 정렬

정렬되지 않은 숫자 목록의 개략도. 네 번째 요소와 다섯 번째 요소를 가리키는 포인터가 하나씩 있다. 다섯 번째 요소는 정렬되어 파란색으로 표시되었다.

  • 첫 값 > 둘째 값
    • 교환
  • 둘째 값 > 첫 값
    • 그대로 둠
Python으로 배우는 자료구조와 알고리즘

버블 정렬

정렬되지 않은 숫자 목록의 개략도. 첫 번째 요소와 두 번째 요소를 가리키는 포인터가 하나씩 있다. 마지막 요소는 파란색으로 표시되었다.

  • 첫 값 > 둘째 값
    • 교환
  • 둘째 값 > 첫 값
    • 그대로 둠
Python으로 배우는 자료구조와 알고리즘

버블 정렬

정렬되지 않은 숫자 목록의 개략도. 두 번째 요소와 세 번째 요소를 가리키는 포인터가 하나씩 있다. 마지막 요소는 파란색으로 표시되었다.

  • 첫 값 > 둘째 값
    • 교환
  • 둘째 값 > 첫 값
    • 그대로 둠
Python으로 배우는 자료구조와 알고리즘

버블 정렬

정렬되지 않은 숫자 목록의 개략도. 두 번째 요소와 세 번째 요소를 가리키는 포인터가 하나씩 있다. 두 번째와 세 번째 요소가 서로 바뀌었다. 마지막 요소는 파란색으로 표시되었다.

  • 첫 값 > 둘째 값
    • 교환
  • 둘째 값 > 첫 값
    • 그대로 둠
Python으로 배우는 자료구조와 알고리즘

버블 정렬

정렬되지 않은 숫자 목록의 개략도. 세 번째 요소와 네 번째 요소를 가리키는 포인터가 하나씩 있다. 마지막 요소는 파란색으로 표시되었다.

  • 첫 값 > 둘째 값
    • 교환
  • 둘째 값 > 첫 값
    • 그대로 둠
Python으로 배우는 자료구조와 알고리즘

버블 정렬

정렬되지 않은 숫자 목록의 개략도. 세 번째 요소와 네 번째 요소를 가리키는 포인터가 하나씩 있다. 마지막 두 요소는 파란색으로 표시되었다.

  • 첫 값 > 둘째 값
    • 교환
  • 둘째 값 > 첫 값
    • 그대로 둠
Python으로 배우는 자료구조와 알고리즘

버블 정렬

정렬되지 않은 숫자 목록의 개략도. 첫 번째 요소와 두 번째 요소를 가리키는 포인터가 하나씩 있다. 마지막 두 요소는 파란색으로 표시되었다.

  • 첫 값 > 둘째 값
    • 교환
  • 둘째 값 > 첫 값
    • 그대로 둠
Python으로 배우는 자료구조와 알고리즘

버블 정렬

정렬되지 않은 숫자 목록의 개략도. 첫 번째 요소와 두 번째 요소를 가리키는 포인터가 하나씩 있다. 첫 번째와 두 번째 요소가 서로 바뀌었다. 마지막 두 요소는 파란색으로 표시되었다.

  • 첫 값 > 둘째 값
    • 교환
  • 둘째 값 > 첫 값
    • 그대로 둠
Python으로 배우는 자료구조와 알고리즘

버블 정렬

정렬되지 않은 숫자 목록의 개략도. 두 번째 요소와 세 번째 요소를 가리키는 포인터가 하나씩 있다. 마지막 두 요소는 파란색으로 표시되었다.

  • 첫 값 > 둘째 값
    • 교환
  • 둘째 값 > 첫 값
    • 그대로 둠
Python으로 배우는 자료구조와 알고리즘

버블 정렬

정렬되지 않은 숫자 목록의 개략도. 두 번째 요소와 세 번째 요소를 가리키는 포인터가 하나씩 있다. 마지막 세 요소는 파란색으로 표시되었다.

  • 첫 값 > 둘째 값
    • 교환
  • 둘째 값 > 첫 값
    • 그대로 둠
Python으로 배우는 자료구조와 알고리즘

버블 정렬

정렬되지 않은 숫자 목록의 개략도. 첫 번째 요소와 두 번째 요소를 가리키는 포인터가 하나씩 있다. 마지막 세 요소는 파란색으로 표시되었다.

  • 첫 값 > 둘째 값
    • 교환
  • 둘째 값 > 첫 값
    • 그대로 둠
Python으로 배우는 자료구조와 알고리즘

버블 정렬

정렬되지 않은 숫자 목록의 개략도. 첫 번째 요소와 두 번째 요소를 가리키는 포인터가 하나씩 있다. 마지막 네 요소는 파란색으로 표시되었다.

  • 첫 값 > 둘째 값
    • 교환
  • 둘째 값 > 첫 값
    • 그대로 둠
Python으로 배우는 자료구조와 알고리즘

버블 정렬

정렬되지 않은 숫자 목록의 개략도. 첫 번째 요소와 두 번째 요소를 가리키는 포인터가 하나씩 있다. 모든 요소가 파란색으로 표시되었다.

  • 첫 값 > 둘째 값
    • 교환
  • 둘째 값 > 첫 값
    • 그대로 둠
Python으로 배우는 자료구조와 알고리즘

버블 정렬 - 구현

def bubble_sort(my_list):
  list_length = len(my_list)
  for i in range(list_length-1):
    for j in range(list_length-1-i):

      if my_list[j] > my_list[j+1]:

        my_list[j] , my_list[j+1] = my_list[j+1] , my_list[j]

  return my_list

print(bubble_sort([4,3,7,1,5]))

[1, 3, 4, 5, 7]
Python으로 배우는 자료구조와 알고리즘

버블 정렬 - 구현

def bubble_sort(my_list):
  list_length = len(my_list)
  is_sorted = False

  while not is_sorted:

    is_sorted = True

    for i in range(list_length-1):

      if my_list[i] > my_list[i+1]:

        my_list[i] , my_list[i+1] = my_list[i+1] , my_list[i]

        is_sorted = False

    list_length -= 1

  return my_list
Python으로 배우는 자료구조와 알고리즘

버블 정렬 - 복잡도

  • 최악: $O(n^2)$
  • 최선 - 기본 버전: $\Omega(n^2)$
  • 최선 - 개선 버전: $\Omega(n)$
  • 평균: $\Theta(n^2)$
  • 매우 뒤죽박죽인 큰 리스트에서는 성능이 낮음
  • 다음에 적합:
    • 큰 정렬됨/거의 정렬된 리스트
    • 작은 리스트
Python으로 배우는 자료구조와 알고리즘

Vamos praticar!

Python으로 배우는 자료구조와 알고리즘

Preparing Video For Download...