버블 정렬 vs 선택 정렬: 개념부터 핵심 차이점까지 한눈에 정리

이 글에서는 대표적인 기본 정렬 알고리즘인 버블 정렬(Bubble Sort)과 선택 정렬(Selection Sort)의 개념과 동작 방식, 그리고 두 알고리즘의 핵심 차이점을 살펴봅니다.

버블 정렬(Bubble Sort)이란?

• 가장 단순한 형태의 정렬 알고리즘 중 하나입니다.
• 리스트를 처음부터 끝까지 순회하면서 인접한 두 요소를 반복적으로 비교합니다.
• 인접 요소의 순서가 올바르지 않으면 두 요소를 서로 교환(swap)합니다.
• 값을 맞바꾸는 요소 교환(exchange) 방식을 사용합니다.
• 모든 요소가 제자리에 놓일 때까지 순회와 교환 과정을 반복 수행합니다.
• 이미 정렬된 데이터라면 최선의 경우 O(n)으로 빠르게 종료되지만, 일반적인 평균·최악의 시간 복잡도는 O(n²)입니다.
• 교환 횟수가 많기 때문에 일반적으로 선택 정렬보다 속도가 느리고 효율성이 떨어집니다.

버블 정렬 의사 코드(Pseudocode)

begin BubbleSort(list)
  for all elements of list
    if list[i] > list[i+1]
      swap(list[i], list[i+1])
    end if
  end for
  return list
end BubbleSort

선택 정렬(Selection Sort)이란?

• 리스트에서 최솟값(또는 최댓값)을 먼저 찾아내는 방식으로 동작합니다.
• 오름차순 또는 내림차순 어느 방향으로든 정렬할 수 있습니다.
• 아직 정렬되지 않은 부분 배열에서 최솟값(또는 최댓값)을 선택해, 정렬된 부분 배열 바로 다음 위치에 배치합니다.
• 같은 값의 상대적 순서가 유지되지 않을 수 있으므로 불안정 정렬(unstable sort)로 분류됩니다.
• 최선·평균·최악의 모든 경우에서 시간 복잡도가 O(n²)입니다.
• 삽입 정렬(insertion sort)에 비해서는 효율성이 떨어집니다.
• 반복 과정에서 수행되는 비교 연산 횟수가 실제 요소 교환 횟수보다 훨씬 많습니다.
• 리스트 내 각 요소의 최종 위치가 미리 정해져 있으므로, 해당 자리에 들어갈 요소만 찾으면 됩니다.
• 교환이 적어 버블 정렬에 비해 효율적이고 빠르게 동작하는 편입니다.
• 요소를 골라 배치하는 선택(selection) 방식이 알고리즘 이름의 유래입니다.

선택 정렬 절차

1단계 : MIN을 0번 위치(첫 번째 요소)로 설정한다
2단계 : 리스트 전체에서 최솟값을 탐색한다
3단계 : 최솟값을 MIN 위치의 값과 교환(swap)한다
4단계 : MIN을 다음 요소를 가리키도록 1 증가시킨다
5단계 : 리스트가 모두 정렬될 때까지 2~4단계를 반복한다

버블 정렬과 선택 정렬의 핵심 차이점 비교

정리하면, 버블 정렬은 구현이 매우 간단하지만 잦은 요소 교환 때문에 성능이 떨어지는 반면, 선택 정렬은 교환 횟수를 최소화하기 때문에 실제 실행에서 더 나은 성능을 보이는 경우가 많습니다. 두 알고리즘 모두 정렬의 기본 원리를 익히기에 좋은 출발점이므로, 학습용 예제로 활용하기에 적합합니다.