버블 정렬 (Bubble Sort)

버블 정렬은 정렬 알고리즘 중 가장 비효율적인 알고리즘입니다. 2008년 버락 오바마가 대통령 후보시 접견한 구글 CEO 에릭 슈미트가 "32비트 정수 100만 개를 정렬하는 가장 효율적인 방법은 무엇인가요?"라고 물었을 때, 변호사 출신인 오바마가 이런 대답을 했다고 합니다. "버블정렬은 잘못된 시작일 것 같습니다". 

법학을 전공한 오바마조차 이런 말을 한 것은 다음 코드를 보면 매우 자명합니다.

 

파이썬 코드

from typing import List

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

 

배열 길이만큰 for 문을 돌면서 배열의 아이템을 매번 쭉 살펴봅니다. 연달아 있는 원소 2개가 순서가 잘못될 경우 두 원소를 바꿉니다. 배열 전체를 살펴보는 것을 n번 수행하기 때문에 시간 복잡도는 무조건 $O(n^2)$ 가 되겠죠.

 

홍머스 정리

• 가끔 구현해 보라고 물어보는 면접관이 있다더라.
• 노가다 정렬

참조

• <파이썬 알고리즘 인터뷰>, p480 - p481