[Algorithm] 정렬 2. Selection Sort

TOC

• 선택 정렬(Selection Sort)
  • 정렬 과정
  • 구현
• Selection Algorithm
  • 선택 과정
  • k번째로 작은 원소를 찾는 알고리즘

선택 정렬(Selection Sort)

주어진 자료들 중 가장 작은 값의 원소부터 차례대로 선택하여 위치 교환

정렬 과정

• 주어진 리스트 중에서 최솟값 확인
• 그 값을 리스트의 맨 앞에 위치한 값과 교환
• 맨 처음 위치를 제외한 나머지 리스트를 대상으로 위 과정 반복
• 시간 복잡도 : O(n2)

구현

알고리즘은 다음과 같다.

def selectionSort(a[], n)
  0부터 n-2까지 순회하는 i마다
    a[i],...,a[n-1] 원소 중 최솟값 a[k] 찾음
    a[i]와 a[k] 교환

k는 최솟값의 인덱스이므로 최솟값을 발견한다면 최솟값 인덱스 k도 저장해둘 필요가 있다.

이를 python 코드로 나타내보자.

def selectionSort(a, N):
    for i in range(N-1):
        minIdx = i
        for j in range(i+1, N):
            if a[minIdx] > a[j]:
                minIdx = j
        a[i], a[minIdx] = a[minIdx], a[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]:
                minIndex = j
        arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr[k-1]