Algorithm - Bubble Sort

Algorithm

어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법

 

Bubble Sort

서로 인접한 두 원소의 대소를 비교하여 정렬하는 알고리즘

 

구현

• 첫 번째 요소부터 서로 인접한 다음 요소와의 크기를 비교하여 다음 요소의 크기가 작다면(크다면) 값을 교환
• 1회전을 수행하고 나면 가장 큰 요소(가장 작은 요소)가 맨 마지막 요소로 이동하므로, 다음 회전 때는 마지막 요소를 제외하고 회전 수행

def bubbleSort(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]
    return

 

 

공간 복잡도

별도의 추가 공간을 사용하지 않고 주어진 배열 원소의 위치만 바꾸기 때문에 O(1)

 

시간 복잡도

n-1부터 0까지의 인덱스에 접근해야하기 때문에 O(n)의 시간을 소요하고,

한 인덱스의 루프에서는 주어진 배열 원소의 값의 대소 비교 후 자리 교환을 하기 위해 O(n)의 시간이 추가로 필요함

그래서 O(n^2)의 시간복잡도를 가짐

인덱스가 n - 1일 때 n-1번, n-2일 때 n-2번...
(n-1) + (n-2) + ... + 1 = (n-1) * n / 2 = O(n^2)

 

장점

• 구현이 쉬움
• 코드가 직관적임

 

단점

• O(n^2)의 시간 복잡도를 가지기 때문에 효율적이지 않음

 

시간복잡도 최적화

처음부터 정렬된 배열이 들어오거나, 정렬 중간에 정렬이 완료되는 경우 더 이상 비교를 하지 않고 결과를 바로 반환하여 시간 복잡도를 줄일 수 있음

 

배열을 한 번 회전했을 때, 교환이 한 번도 일어나지 않았다면(flag=False) 정렬을 중지하고 바로 반환하는 방식

def bubbleSort(arr):
    for i in range(len(arr) - 1, 0, -1):
        flag = False
        for j in range(i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                flag = True
        if not flag:
            break
    return

처음부터 정렬된 배열이 들어올 경우, 한 번만 배열의 원소를 비교하면 되기 때문에 O(n)의 시간 복잡도를 가질 수 있음