버블 정렬 알고리즘

• 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다.
• 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.
• 선택 정렬과 기본 개념이 유사하다.
• 거품 정렬은 점점 큰 값들을 뒤에서 부터 앞으로 하나씩 쌓여 나가게 때문에 후반으로 갈수록 정렬 범위가 하나씩 줄어들게 된다.

시간 복잡도가 O(n$^2$)으로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다. 양방향으로 번갈아 수행하면 칵테일 정렬이 된다.

오름차순으로 정렬하는 버블 정렬의 과정

55 07 78 12 42 초기값[파란색은 sorting]
07 55 78 12 42 첫 번째 패스(pass)
07 55 78 12 42
07 55 12 78 42
07 55 12 42 78 두 번째 패스(pass)
07 55 12 42 78
07 12 55 42 78
07 12 42 55 78 세 번째 패스(pass)
07 12 42 55 78 네 번째 패스(pass)
07 12 42 55 78 다섯 번째 패스(pass)
07 12 42 55 78 정렬 끝

• 무작위 배열수의 거품 정렬 예
  

[참고]https://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC

특징

장점

• 구현이 매우 간단하다

단점

• 순서에 맞지 않은 요소를 인접한 요소와 교환한다
• 하나의요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다
• 일반적으로 버블정렬은 단순성에도 불구하고 거의 쓰이지 않는다(비효율적)

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]