선택 정렬 (Selection Sort)

선택 정렬(Selection Sort)은 비교 기반 정렬 알고리즘의 하나로, 리스트를 반복적으로 순회하면서 정렬되지 않은 부분에서 가장 작은(또는 큰) 요소를 선택하여 정렬된 부분의 끝에 위치시키는 방식으로 동작한다. 이 과정은 리스트가 정렬될 때까지 계속된다.

동작 원리

1. 초기 상태: 리스트의 처음부터 끝까지 순회한다.
2. 가장 작은 요소 찾기: 현재 위치에서 시작하여 정렬되지 않은 부분에서 가장 작은 요소를 찾는다.
3. 교환: 찾은 가장 작은 요소를 현재 위치의 요소와 교환한다.
4. 반복: 리스트 전체가 정렬될 때까지 위 과정을 반복한다.

알고리즘 단계

1. 리스트의 첫 번째 요소를 최소값(min_index)으로 가정한다.
2. 나머지 요소들을 순회하며 현재 최소값보다 작은 요소가 있는지 확인한다.
3. 작은 요소가 발견되면 그것을 새로운 최소값으로 설정한다.
4. 리스트의 첫 번째 요소와 최소값 요소를 교환한다.
5. 리스트의 두 번째 요소를 기준으로 1~4 단계를 반복한다.
6. 리스트의 끝까지 위 과정을 반복한다.

예제

정렬할 리스트: [64, 25, 12, 22, 11]

1. 첫 번째 순회:
   • 초기 리스트: [64, 25, 12, 22, 11]
   • 최소값 찾기: 11
   • 교환: [11, 25, 12, 22, 64]
2. 두 번째 순회:
   • 초기 리스트: [11, 25, 12, 22, 64]
   • 최소값 찾기: 12
   • 교환: [11, 12, 25, 22, 64]
3. 세 번째 순회:
   • 초기 리스트: [11, 12, 25, 22, 64]
   • 최소값 찾기: 22
   • 교환: [11, 12, 22, 25, 64]
4. 네 번째 순회:
   • 초기 리스트: [11, 12, 22, 25, 64]
   • 최소값 찾기: 25 (이미 제자리에 있음)
   • 교환: [11, 12, 22, 25, 64]

리스트가 완전히 정렬되었다.

시간 복잡도

선택 정렬의 시간 복잡도는 최선, 평균, 최악의 경우 모두 O(n^2)이다. 각 단계에서 최소값을 찾기 위해 리스트의 남은 부분을 모두 순회해야 하기 때문이다.

공간 복잡도

선택 정렬은 제자리 정렬(in-place sorting) 알고리즘으로, 추가적인 메모리를 거의 사용하지 않기 때문에 공간 복잡도는 O(1)이다.

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]

arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("Sorted array is:", arr)

선택 정렬은 간단하고 이해하기 쉬운 정렬 알고리즘이지만, 효율성 면에서는 다른 정렬 알고리즘에 비해 낮은 편이다. 특히, 큰 데이터 세트에는 퀵 정렬(Quick Sort)이나 병합 정렬(Merge Sort) 같은 더 효율적인 알고리즘을 사용하는 것이 좋다. 그러나 선택 정렬은 데이터의 크기가 작을 때나 교육용으로 유용하다.

 

모든 코드는 github에 저장되어 있습니다.

https://github.com/SeongUk18/Algorithm/tree/main/Data_structure_algorithms