파이썬으로 정리하는 버블정렬

개념

• 서로 인접한(연속된) 두 원소를 확인해 정렬하는 알고리즘
  • 인접한 2개의 원소를 확인하여 조건에 맞는 순서로 교환
• 비교와 교환으로 이루어진 알고리즘

순서(오름차순 기준)

1. 연속된 두 항목을 가리킨 후 비교한다.
2. 두 항목의 값의 크기가 뒤바뀌어 있으면 값을 교환한다.
3. 비교 포인터를 오른쪽 한칸씩 이동한다.
4. 배열의 끝까지 또는 정렬된 항목까지 1~2단계를 반복한다.

특징

장점

• 구현이 간단

단점

• 순차적으로 확인하기 때문에 크기에 맞지 않는 비교가 발생
• 순차적으로 확인하기 때문에 N개의 길이가 있다면 N번 교환 발생

예제 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def buble_sort(input_list):
    unsorted_until_idx = len(input_list) - 1
    is_sorted = False

    while not is_sorted:
        is_sorted = True
        for i in range(unsorted_until_idx):
            if input_list[i] > input_list[i + 1]:
                temp = input_list[i]
                input_list[i] = input_list[i + 1]
                input_list[i + 1] = temp
                is_sorted = False
    return input_list

시간복잡도

주어진 데이터의 원소 길이가 5일때 두 수의 비교를 순차적으로 끝까지 하게 되면 총 4번의 횟수가 발생한다.

이때 끝까지 비교를 하면 4+3+2+1 = 10번이 발생한다. (n-1) + (n-2) ... + 1

교환도 마찬가지로 비교와 동일하게 10번이 발생하게 된다.

비교와 교환의 두 횟수를 최악의 상황에서 더하게 되면 20단계라고 볼 수 있다.