[기술면접/알고리즘] Bubble Sort

Bubble Sort에 대해 설명하세요

Keyword

비교,swap

---

Script

Bubble Sort는 정렬 알고리즘으로, 서로 인접한 원소를 비교하여 크기의 순서에 맞게 정렬을 수행하는 알고리즘입니다. 배열의 크기가 n일때, 0번 index부터 n-1번 index까지 모든 index를 순차적으로 비교하면서 정렬합니다. 매 회전마다 가장 큰 원소가 가장 뒤에 위치하게 되고, 이 원소는 다음 회전에서 정렬을 수행할 필요가 없어집니다. 시간복잡도는 O(n^2)입니다.

---

Additional

시간복잡도

비교 횟수
1회전 - n-1번
2회전 - n-2번
...
n-1회전 - 1번
으로, 총 n(n-1)/2

교환 횟수
배열이 역순으로 정렬되어 있는 최악의 경우, 모든 비교에서 교환을 실행한다.
교환의 경우, 3번의 이동(Swap 함수)이 필요하므로 3n(n-1)/2 번이 필요하다.
최선의 경우(이미 정렬된 경우)는 교환이 일어나지 않는다.

T(n) = O(n^2)

그림

코드 (python)

def bubble_sort(arr):
    for i in range(len(arr) - 1, 0, -1):
        for j in range(i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

정렬 알고리즘 시간복잡도 비교