정렬: 선택 정렬

출처: 위키백과

 

선택 정렬이란?

선택 정렬(Selection Sort)은 배열이나 리스트를 정렬하는 데 사용되는 간단한 비교 기반 알고리즘입니다. 이 방법은 각 반복에서 '선택' 과정을 통해 가장 작은(또는 가장 큰) 요소를 찾아 현재 정렬 위치에 있는 요소와 교체합니다.

 

선택 정렬의 작동 원리

선택 정렬은 배열 전체를 순회하며 현재 위치에 들어갈 가장 작은 요소를 '선택'합니다. 선택된 요소는 현재 위치의 요소와 자리를 바꾸며, 이 과정을 배열의 모든 요소에 대해 반복합니다.

 

선택 정렬의 단계별 과정

1. 배열의 첫 번째 요소를 현재 위치로 설정합니다.
2. 현재 위치 이후의 배열에서 가장 작은 요소를 찾습니다.
3. 가장 작은 요소와 현재 위치의 요소를 교환합니다.
4. 현재 위치를 한 칸 오른쪽으로 이동하고 위의 과정을 배열의 끝까지 반복합니다.

 

선택 정렬의 복잡도

• 시간 복잡도: 선택 정렬은 각 요소에 대해 나머지 모든 요소와 비교를 수행하기 때문에 시간 복잡도가 O(n^2)입니다.
• 공간 복잡도: O(1)로, 추가적인 메모리 공간은 하나만 필요합니다.

Pseudocode

for i from 0 to N-1
  min_index = i
  for j from i+1 to N
    if array[j] < array[min_index]
      min_index = j
  if min_index != i
    swap(array[i], array[min_index])

 

실제 예시로 이해하기

예를 들어, [29, 10, 14, 37, 13] 이라는 배열을 오름차순으로 정렬한다고 해봅시다. 선택 정렬 과정은 다음과 같습니다:

1. 첫 번째 요소(29)를 현재 위치로 설정하고, 가장 작은 요소(10)를 찾아 위치를 교환합니다: [10, 29, 14, 37, 13]
2. 두 번째 요소(29)를 현재 위치로 설정하고, 가장 작은 요소(13)를 찾아 위치를 교환합니다: [10, 13, 14, 37, 29]
3. 세 번째 요소(14)는 이미 가장 작으므로 교환하지 않고, 나머지 과정을 계속합니다.
4. 네 번째 요소(37)와 다섯 번째 요소(29)를 비교하고 교환합니다: [10, 13, 14, 29, 37]

결과적으로 오름차순으로 정렬된 배열 [10, 13, 14, 29, 37]을 얻을 수 있습니다.

 

선택 정렬은 그 구현이 단순하여 알고리즘을 처음 배우는 학생들이나 배열의 크기가 작은 경우에 적합합니다. 그러나 큰 데이터 세트에 대해서는 더 효율적인 정렬 알고리즘을 사용하는 것이 좋습니다.