[알고리즘 개념] 선택정렬 (Selection Sort)

기본 정렬 알고리즘

선택 정렬 (Selection Sort)

• 정렬 순서

  1. 주어진 리스트 중에 최소값을 찾는다

  2. 그 값을 맨 앞에 위치한 값과 교체한다

  3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다

• 예시

  순서	리스트	최소값
  0	[ 3, 5, 2, 7, 6 ]	2
  1	[ 2, 5, 3, 7, 6 ]	3
  2	[ 2, 3, 5, 7, 6 ]	5
  3	[ 2, 3, 5, 7, 6 ]	6
  4	[ 2, 3, 5, 6, 7 ]	7

• 코드

def selection_sort(x):
    length = len(x)
    
    for i in range(length - 1):
        min_idx = i
        for j in range(i + 1 , length):
            if x[i] > x[j] :
                min_idx = j

        x[i], x[min_idx] = x[min_idx], x[i]

    return x

• 시간 복잡도 비교

  기본 정렬 알고리즘	최적	평균	최악
  선택 정렬	N^2	N^2	N^2
  버블 정렬	N^2	N^2	N^2
  삽입 정렬	N	N^2	N^2