개념
버블 정렬(Bubble Sort)은 컴퓨터 과학에서 가장 간단한 정렬 알고리즘 중 하나입니다. 인접한 두 개의 요소를 비교하고 필요한 경우 위치를 교환하여 리스트를 정렬하는 과정을 반복합니다. 정렬 과정에서 큰 값이 "위로 올라가는(bubble up)" 것처럼 보이기 때문에 "버블 정렬"이라는 이름이 붙었습니다.
버블 정렬의 동작 과정은 다음과 같습니다:
- 리스트의 첫 번째 요소부터 시작하여 인접한 요소를 순서대로 비교합니다.
- 만약 앞의 요소가 뒤의 요소보다 크다면, 두 요소의 위치를 교환합니다.
- 리스트의 끝까지 도달하면, 가장 큰 요소가 맨 뒤로 이동한 상태가 됩니다.
- 이제 정렬되지 않은 리스트에서 가장 큰 요소가 맨 뒤에 위치하게 되었으므로, 다시 첫 번째 요소부터 시작하여 위의 과정을 반복합니다.
- 정렬된 요소는 고정되고, 나머지 요소들에 대해 위의 과정을 반복하여 전체 리스트가 정렬될 때까지 반복합니다.
이 과정을 리스트의 크기보다 하나 적은 횟수만큼 반복하면 모든 요소들이 올바른 위치에 정렬되게 됩니다.
버블 정렬은 구현이 간단하고 이해하기 쉬운 편이지만, 큰 리스트에 대해서는 비효율적인 알고리즘입니다. 최선의 경우에도 시간 복잡도는 O(n^2)이며, 이로 인해 큰 규모의 데이터에 대해서는 다른 정렬 알고리즘을 사용하는 것이 좋습니다. 그러나 리스트가 이미 거의 정렬된 상태거나, 리스트의 크기가 작을 경우에는 버블 정렬이 다른 알고리즘보다 효율적일 수 있습니다.
예시
예시를 위해 주어진 배열이 [5, 2, 8, 1, 9]라고 가정해 보겠습니다.
첫 번째 패스:
- 인덱스 0과 1의 원소인 5와 2를 비교하여 5가 더 크므로 교환합니다. 배열은 [2, 5, 8, 1, 9]가 됩니다.
- 인덱스 1과 2의 원소인 5와 8을 비교하여 정렬된 상태이므로 교환하지 않습니다. 배열은 그대로 [2, 5, 8, 1, 9]입니다.
- 인덱스 2와 3의 원소인 8과 1을 비교하여 8이 더 크므로 교환합니다. 배열은 [2, 5, 1, 8, 9]가 됩니다.
- 인덱스 3과 4의 원소인 8과 9를 비교하여 정렬된 상태이므로 교환하지 않습니다. 배열은 그대로 [2, 5, 1, 8, 9]입니다.
첫 번째 패스를 마치면 배열은 [2, 5, 1, 8, 9]로, 가장 큰 원소인 9이 맨 뒤로 이동했습니다.
두 번째 패스:
- 인덱스 0과 1의 원소인 2와 5를 비교하여 정렬된 상태이므로 교환하지 않습니다. 배열은 그대로 [2, 5, 1, 8, 9]입니다.
- 인덱스 1과 2의 원소인 5와 1을 비교하여 5가 더 크므로 교환합니다. 배열은 [2, 1, 5, 8, 9]가 됩니다.
- 인덱스 2와 3의 원소인 5와 8을 비교하여 정렬된 상태이므로 교환하지 않습니다. 배열은 그대로 [2, 1, 5, 8, 9]입니다.
- 인덱스 3과 4의 원소인 8과 9를 비교하여 정렬된 상태이므로 교환하지 않습니다. 배열은 그대로 [2, 1, 5, 8, 9]입니다.
두 번째 패스를 마치면 배열은 [2, 1, 5, 8, 9]로, 두 번째로 큰 원소인 8이 맨 뒤에서 두 번째로 이동했습니다.
세 번째 패스:
- 인덱스 0과 1의 원소인 2와 1을 비교하여 2가 더 크므로 교환합니다. 배열은 [1, 2, 5, 8, 9]가 됩니다.
- 인덱스 1과 2의 원소인 2와 5를 비교하여 정렬된 상태이므로 교환하지 않습니다. 배열은 그대로 [1, 2, 5, 8, 9]입니다.
- 인덱스 2와 3의 원소인 5와 8을 비교하여 정렬된 상태이므로 교환하지 않습니다. 배열은 그대로 [1, 2, 5, 8, 9]입니다.
- 인덱스 3과 4의 원소인 8과 9를 비교하여 정렬된 상태이므로 교환하지 않습니다. 배열은 그대로 [1, 2, 5, 8, 9]입니다.
세 번째 패스를 마치면 배열은 [1, 2, 5, 8, 9]로, 세 번째로 큰 원소인 5가 맨 뒤에서 세 번째로 이동했습니다.
네 번째 패스:
- 인덱스 0과 1의 원소인 1과 2를 비교하여 정렬된 상태이므로 교환하지 않습니다. 배열은 그대로 [1, 2, 5, 8, 9]입니다.
- 인덱스 1과 2의 원소인 2와 5를 비교하여 정렬된 상태이므로 교환하지 않습니다. 배열은 그대로 [1, 2, 5, 8, 9]입니다.
- 인덱스 2와 3의 원소인 5와 8을 비교하여 정렬된 상태이므로 교환하지 않습니다. 배열은 그대로 [1, 2, 5, 8, 9]입니다.
- 인덱스 3과 4의 원소인 8과 9를 비교하여 정렬된 상태이므로 교환하지 않습니다. 배열은 그대로 [1, 2, 5, 8, 9]입니다.
네 번째 패스를 마치면 배열은 [1, 2, 5, 8, 9]로, 네 번째로 큰 원소인 2가 맨 뒤에서 네 번째로 이동했습니다.이렇게 패스를 반복하면서 가장 큰 원소가 맨 뒤로 이동하게 되고, 나머지 원소들도 순차적으로 정렬되는 과정을 거치면 최종적으로 배열이 정렬됩니다.
