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


  • 주어진 리스트 중에서 최솟값 확인
  • 그 값을 리스트의 맨 앞에 위치한 값과 교환
  • 맨 처음 위치를 제외한 나머지 리스트를 대상으로 위 과정 반복
  • 시간 복잡도 : 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]

  • 저장되어 있는 자료로부터 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]