버블 정렬

CS50 2019 강의를 듣고 내용을 정리한 시리즈 글입니다.

---

학습목표

버블 정렬의 원리와 실행 시간을 설명하고 구현할 수 있습니다.

핵심 단어

• 버블 정렬

강의 내용

1. 버블 정렬

정렬되지 않은 리스트를 탐색하는 것 보다 정렬한 뒤 탐색하는 것이 더 효율적이며 버블 정렬은 정렬 알고리즘 중 하나다.

버블 정렬은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법을 말한다.

버블 정렬은 단 두 개의 요소만 정렬해주는 좁은 범위의 정렬에 집중하기 때문에 간단하지만 단 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수도 있다.

1~8의 숫자가 임의로 나열되어 있는 리스트로 버블 정렬을 실행해보자

전: 6 3 8 5 2 7 4 1
후: 3 6 8 5 2 7 4 1

작업을 반복해보자

3 6 5 8 2 7 4 1
3 6 5 2 8 7 4 1
3 6 5 2 7 8 4 1
3 6 5 2 7 4 8 1
3 6 5 2 7 4 1 8

...

최종적으로 아래와 같이 오름차순으로 정렬이 완료된다.

1 2 4 3 5 6 7 8

버블정렬을 python으로 나타내면 아래와 같다.

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

버블정렬은 중첩 루프를 돌아야 하고, n개의 값이 주어졌을 때 각 루프는 각각 n-1번 반복되므로 Big O는 O(n^2)이다.

정렬 여부에 관계 없이 루프를 돌며 비교하기 때문에 Big Ω 또한 Ω(n^2)이 된다.

생각해보기

버블 정렬이 효율적인 경우는 어떤 경우인가요? 반대로 어떤 경우에 비효율적이게 될까요?

기본적으로 버블정렬의 경우 Big O, Big Ω 둘 다 n^2이기 때문에 n의 크기가 커지면 커질수록 더욱 비효율적이게 된다.

또한 배열이 정렬되지 않은 경우에는 교환 연산이 많이 실행되기 때문에 비효율적이다.

반대로 배열이 정렬되어 있다면 교환 연산이 실행되지 않기 때문에 상대적으로 효율적이라고 볼 수 있다.