[python] 선택 정렬 (selection sort)

정의

선택 정렬이란 배열에서 가장 작은 원소를 찾아 첫 번째 원소와 교환하고, 두 번째 작은 원소를 찾아 두 번째 원소와 교환하는 방식으로 전체가 정렬될 때까지 계속함

정의

- 제자리 정렬

- 불안정적

- 입력 자료의 순서에 민감하지 않음

- 작은 키와 매우 큰 레코드를 가지는 화일을 정렬하는데 적합함

선택 정렬 ADL

selectionSort(a[], n)
   for (i ← 1; i < n; i ← i + 1) do {
       minIndex ← i;
       for (j ← i + 1; j ≤ n; j ← j + 1) do 
            if (a[j] < a[minIndex]) then minIndex ← j;
       a[i]와 a[minIndex]를 교환;   
       }
end selectionSort()

선택 정렬 구현

def selection_sort(a, n):
    for i in range(1 , n):
        minIndex = i
        for j in range(i + 1, n + 1):
            if a[j] < a[minIndex]:
                minIndex = j
        a[minIndex], a[i] = a[i], a[minIndex]
    return a