알고리즘, 자료구조/정리

버블 정렬 알고리즘 (Bubble sort Algorithm)

jaee 2023. 3. 27. 13:48

 
틀린 내용을 발견하신 경우 말씀 부탁드립니다! 🙇

 
버블정렬 알고리즘은 서로 인접한 두 개의 값을 비교하여 정렬하는 방식이다. 오름차순 정렬이라고 가정했을 때, 1회전이 끝나면 가장 큰 값이 맨 뒤에 위치하게 되며 각 회전이 끝날 때마다 비교해야하는 값이 하나씩 감소한다. 주어진 배열에서 값을 교환(swap) 하기 때문에 제자리 정렬 알고리즘에 속한다. 값을 정렬할 때 발생하는 교환 작업(swap)이 복잡하기 때문에 단순한 알고리즘임에도 불구하고 잘 쓰이지 않는다.

https://codepumpkin.com/bubble-sort/

 

Pseudo code

n개의 요소로 이루어진 (정렬되지 않은) 배열을 오름차순으로 정렬하는 경우,
(1회전 차) 첫 번째 값과 두 번째 값을 비교한다. 작은 값은 첫 번째 인덱스에, 큰 값은 두 번째 인덱스에 놓는다.
(1회전 차) 두 번째 값과 세 번째 값을 비교한다. 작은 값은 두 번째 인덱스에, 큰 값은 세 번째 인덱스에 놓는다.
...
(1회전 차) n-1번째 값과 n번째 값을 비교한다. 작은 값은 n-1번째 인덱스에, 큰 값은 n번째 인덱스에 놓는다.
(2회전 차) 첫 번째 값과 두 번째 값을 비교한다. 작은 값은 첫 번째 인덱스에, 큰 값은 두 번째 인덱스에 놓는다.
...
(2회전 차) n-2번째 값과 n-1번째 값을 비교한다. 작은 값은 n-2번째 인덱스에, 큰 값은 n-1번째 인덱스에 놓는다.
(3회전 차) 첫 번째 값과 두 번째 값을 비교한다. 작은 값은 첫 번째 인덱스에, 큰 값은 두 번째 인덱스에 놓는다.
...
n-1 번 회전을 한 후 정렬을 종료한다.

 

Python code

def bubblesort(list):
    for i in reversed(range(len(list))):
        for j in range(i):
            if list[j] > list[j+1]:
                list[j], list[j+1] = list[j+1], list[j]

    return list

bubblesort([3,4,0,1,5,6,2])
# result: [0, 1, 2, 3, 4, 5, 6]

온라인 컴파일러에서 실행해보기

 

시간복잡도

버블 정렬 알고리즘의 시간복잡도는 O(N^2)이다.
(n - 1) + (n - 2) + ... 2 + 1 = n(n - 1) /2  → O(N^2)

 

장단점

장점

  • 단순하고 직관적이다.
  • 제자리 정렬이므로 추가적인 메모리가 거의 필요없다.
  • 안정 정렬(Stable sort)이다.
    → 안정 정렬이 장점인 이유: 값이 동일한 경우 입력 순서를 기준으로 정렬해야하는 경우가 있을 수 있기 때문이다.

단점

  • 시간 측면에서 비효율적이다.
  • 교환(swap) 연산이 많이 발생하며, 올바른 위치에 있는 값이라도 최종 정렬이 되기 전까지는 자리가 교환될 수 있다.

 
 

참고 자료