[알고리즘] - 선택 정렬

선택 정렬 (Selection Sort)

주어진 자료들 중 가장 작은 값의 원소부터 차례대로 선택하여 위치를 교환하는 방식으로 셀렉션 알고리즘을 적용한 것

• 정렬 과정

1. 주어진 배열에서 최소값을 찾는다.
2. 그 값을 배열의 맨 앞에 위치한 값과 교환한다.
3. 맨 처음 위치를 제외한 나머지 배열을 대상으로 위의 과정을 반복한다.

• 시간 복잡도
  • O(n2)

예시

# 오름차순으로 정렬
lst = [64, 25, 10, 22, 11]

1. 주어진 배열에서 최소값 찾기
   
2. 배열의 맨 앞에 위치한 값과 교환하기
   
3. 미정렬 배열에서 다시 최소값 찾기
   
4. 배열의 맨 앞에 위치한 값과 교환하기
   
5. 정렬될 때까지 반복하기
   

코드로 구현

lst = [64, 25, 10, 22, 11]
min_val = 0

for i in range(len(lst)-1):
    min_val = i
    for j in range(i, len(lst)):
        if lst[j] < lst[min_val]:
            min_val = j  # 최소값의 인덱스를 찾는다
    lst[i], lst[min_val] = lst[min_val], lst[i]  # 위치 교환하기

셀렉션 알고리즘 (Selection Algorithm)

저장되어 있는 자료로부터 k번째로 크거나, 작은 원소를 찾는 방법
=> 최소값, 최대값 혹은 중간값을 찾는 알고리즘

k번째로 작은 원소 찾기

• 1번부터 k번째까지 작은 원소들을 찾아 배열의 앞쪽으로 이동시키고, 배열의 k번째를 반환한다.
• k가 비교적 작을 때 유용하며 O(kn)의 수행시간을 필요로 한다.

def select(arr, k):
    for i in range(0, k):
        minIndex = i
        for j in range(i+1, len(arr)):
            if arr[minIndex] > arr[j]:
                minIdex = j
        arr[i], arr[minIdex] = arr[minIdex], arr[i]
    return arr[k-1]