정렬 알고리즘 - 선택 정렬(Selection Sort)

해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘입니다.

1. 주어진 배열 중에 최소값을 찾습니다.
2. 그 값을 맨 앞에 위치한 값과 교체합니다.
3. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체합니다.

시간복잡도는 데이터의 개수가 n개라고 했을 때, 비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 배열을 정렬하는데

O(n^2) 만큼의 시간이 걸립니다. 최선, 평균, 최악의 경우 시간복잡도는 O(n^2) 으로 동일합니다.

• 첫 번째 회전에서의 비교횟수 : 1 ~ (n-1) => n-1
• 두 번째 회전에서의 비교횟수 : 2 ~ (n-1) => n-2
• (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2

공간복잡도는 주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n) 입니다.

 

장점

• Bubble sort와 마찬가지로 알고리즘이 단순합니다.
• 정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이
• 일어나야 하는 자료상태에서 비교적 효율적입니다.
• Bubble Sort와 마찬가지로 정렬하고자 하는 배열 안에서 교환하는 방식으로 다른 메모리 공간을 필요로
• 하지 않습니다. => 제자리 정렬(in-place sorting)

단점

• 시간복잡도가 O(n^2)으로, 비효율적입니다.
• 불안정 정렬(Unstable Sort) 입니다.

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