(Python) 버블 정렬(bubble sort)

(Python) 버블 정렬(bubble sort)¶

---

버블 정렬(bubble sort)란?

• 서로 인접한 두 원소들을 순차적으로 비교하여 정렬하는 알고리즘이다.
  (인접해 있는 두 원소의 크기가 순서에 맞지 않다면 서로 교환한다.)

In [1]:

from IPython.display import Image
Image("img/bubble_sort.png")

Out[1]:

버블 정렬(bubble)의 시간복잡도

• 비교 횟수
  • best, average, worst가 모두 일정하다.
  • n-1, n-2, n-3, ... , 2, 1번 비교하므로 총 n(n-1)/2번 비교한다.

• 교환 횟수
  • 입력 자료가 이미 정렬되어 있는 경우라면, 자료의 이동이 일어나지 않는다.
  • 최악의 경우는 입력 자료가 역순으로 정렬되어 있는 경우이다.
    두 항목을 서로 교환해주기 위해선 3번의 이동작업이 필요하다.
    따라서, 3n(n-1)/2번 발생한다.

시간복잡도

• Best : n제곱
• Average : n제곱
• Worst : n제곱

---

In [2]:

# 배열에서 인접한 두 항목을 서로 교환하는 함수
def swap_f(index_a, index_b, array):
    t = array[index_a]
    array[index_a] = array[index_b]
    array[index_b] = t

In [3]:

def bubble_sort(array):
    j = len(array)
    for _ in range(len(array)-1):
        i = 0
        j = j-1
        for x in range(j):
            print(array)
            if array[i] > array[i+1]:
                swap_f(i, i+1, array)
            i = i+1
    return array

In [4]:

bubble_sort([4,3,2,1])

[4, 3, 2, 1]
[3, 4, 2, 1]
[3, 2, 4, 1]
[3, 2, 1, 4]
[2, 3, 1, 4]
[2, 1, 3, 4]

Out[4]:

[1, 2, 3, 4]

Reference¶

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html