선택 정렬

가장 최소인 값을 맨 앞 값이랑 바꿔주는 "선택" 정렬

 

 

패턴 파악

데이터 3개  (턴 2번, 1. 최솟값과 비교 2번 2. 최솟값과 비교 1번)

1. 턴 한번

5

4

2

2

4

5

 

데이터 4개  (턴 3번, 1. 최솟값과 비교 3번 2. 최솟값과 비교 2번 3. 최솟값과 비교 1번)

5	4	3	1
1	4	3	5
1	3	4	5

 

파악되는 중요 패턴은 다음과 같다.

1. 매 턴마다 앞 자리가 정해지면서 반복 횟수가 줄어든다.

2. (매 반복에서) 맨 앞 인덱스의 값과 최솟값을 바꾼다.

 

 

psudo 코드 

for i in range( len(data) -1 ):
   min = i

   for j in range( i+1, len(data) ) :
      if data[min] > data[j]:
          min = j

   swap(data[min], data[j])

 

 

파이썬 코드

def selection_sort(data):
    for stand in range(len(data) - 1):
        min = stand # 최솟값의 기준이 될 index
        for idx in range(stand + 1, len(data)):
            if data[min] > data[idx]:
                min = idx
        data[min], data[stand] = data[stand], data[min]
        
    return data

import random

data_list = random.sample(range(100), 10)
selection_sort(data_list)

 

 

시간 복잡도

반복문이 2개인데, N만큼 반복하기 때문에, O(N^2).