선택 정렬

• 포켓볼 순서대로 정렬하기
  • 흩어진 당구공을 오른쪽 정리한다고 하자. 어떻게 하겠는가?
  • 많은 사람들은 당구대 위에 있는 공 중 가장 작은 숫자의 공부터 골라서 차례대로 정리할 것이다.
    이것이 바로 선택 정렬이다.

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

• 정렬 과정

  • 주어진 리스트 중에서 최솟값을 찾는다.
  • 그 값을 리스트의 맨 앞에 위치한 값과 교환한다.
  • 맨 처음 위치를 제외한 나머지 리스트를 대상으로 위의 과정을 반복한다.

• 시간 복잡도 : O(n^2)

정렬 과정

알고리즘

def SelectionSort(a[], n)
	for i from 0 to n-2
    	a[i],...,a[n-1] 원소 중 최소값 a[k] 찾음
        a[i]와 a[k] 교환

코드

def selectionSort(a, N):
    for i in range(N - 1):
        min_idx = i
        for j in range(i + 1, N):
            if a[min_idx] > a[j]:
                min_idx = j
        a[i], a[min_idx] = a[min_idx], a[i]