정렬: 버블 정렬

출처: 위키백과

 

버블 정렬의 개요

버블 정렬은 가장 기본적인 정렬 알고리즘 중 하나로, 이해하기 쉽고 구현하기 간단합니다. 배열의 요소들을 하나씩 비교하며, 큰 값이 배열의 끝으로 '떠오르도록' 반복해서 요소의 위치를 바꿉니다.

 

버블 정렬의 작동 원리

버블 정렬은 '스왑'이라는 단순한 연산을 통해 이루어집니다. 이 연산은 두 요소의 위치를 바꾸는 것으로, 배열을 반복하면서 인접한 요소끼리 크기를 비교하여 필요에 따라 교환합니다.

 

버블 정렬의 단계별 과정

1. 배열의 첫 번째 요소부터 시작하여 인접한 요소와 비교합니다.
2. 현재 요소가 다음 요소보다 크다면, 두 요소의 위치를 교환합니다.
3. 다음 요소로 이동하여 같은 과정을 배열의 끝까지 반복합니다.
4. 한 번의 패스가 끝날 때마다, 가장 큰 요소가 배열의 끝으로 이동합니다.
5. 교환이 한 번도 일어나지 않을 때까지, 즉 배열이 완전히 정렬될 때까지 과정을 반복합니다.

버블 정렬의 복잡도

• 시간 복잡도: 버블 정렬은 최악의 경우와 평균적인 경우 모두 시간 복잡도가 O(n^2)입니다. 하지만 이미 정렬된 배열에서는 O(n)의 시간 복잡도를 가집니다.
• 공간 복잡도: O(1)로, 추가적인 메모리 공간은 하나만 필요합니다.

실제 예시로 이해하기

예를 들어, [5, 1, 4, 2, 8] 이라는 배열을 오름차순으로 정렬한다고 해봅시다. 버블 정렬 과정은 다음과 같습니다:

1. 첫 번째 요소(5)와 두 번째 요소(1)를 비교하고, 5가 더 크기 때문에 위치를 교환합니다: [1, 5, 4, 2, 8]
2. 두 번째 요소(5)와 세 번째 요소(4)를 비교하고, 5가 더 크기 때문에 위치를 교환합니다: [1, 4, 5, 2, 8]
3. 세 번째 요소(5)와 네 번째 요소(2)를 비교하고, 5가 더 크기 때문에 위치를 교환합니다: [1, 4, 2, 5, 8]
4. 네 번째 요소(5)와 다섯 번째 요소(8)를 비교하고, 교환할 필요가 없습니다: [1, 4, 2, 5, 8]
5. 이제 가장 큰 값인 8이 맨 끝으로 이동했으니, 나머지 배열에 대해 같은 과정을 반복합니다.

이 과정을 계속 반복하면, 결국 오름차순으로 정렬된 배열 [1, 2, 4, 5, 8]을 얻을 수 있습니다.

 

Pseudocode

for i from 0 to N-1
  for j from 0 to N-i-1
    if array[j] > array[j+1]
      swap(array[j], array[j+1])

 

버블 정렬은 효율적인 정렬 알고리즘은 아니지만, 알고리즘의 기본 개념을 이해하고 학습하는 데에는 매우 유용합니다. 그리고 작은 데이터 세트에 대해서는 충분히 실용적인 방법일 수 있습니다. 이러한 기본적인 알고리즘을 통해 더 복잡한 정렬 알고리즘을 이해하는 기초를 다질 수 있습니다.