알고리즘 : 선택정렬(selection sort)

선택 정렬(selection sort)은?

1. 주어진 데이터 중, 최소값을 찾음

2. 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함

3. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함

 

출처 : 위키피디아

 

코드로 만들려면?

1. 데이터 두 개의 경우
data_list = [8, 2]
  data_list[0] > data_list[1] 이므로 data_list[0]값과 data_list[1] 값을 교환

2. 데이터 세 개의 경우
data_list = [8, 2, 6]
  처음 한 번 실행하면 2, 8, 6이 됨
  두 번째 실행하면 2, 6, 8이 됨

3. 데이터 네 개의 경우
data_list = [8, 4, 3, 2]
  처음 한 번 실행하면 2, 4, 3, 8이 됨
  두 번째 실행하면 2, 3, 4, 8 됨
  세 번째 실행하면 변화 없음

 

알고리즘 구현

1. for stand in range(len(data_list) - 1)로 반복
2. lowest = stand
3. for num in range(stand, len(data_list)) stand 이후부터 반복
   내부 반복문 안에서 data_list[lowest] > data_list[num]이면
      lowest = num
4. data_list[num], data_list[lowest] = data_list[lowest], data_list[num]

def selection_sort(data):
	for stand in range(len(data) - 1):
    	lowest = stand
    	for index in range(stand + 1, len(data)):
    		if data[lowest] > data[index]
        		lowest = index
    	data[lowest], data[stand] = data[stand], data[lowest]
    return data

import random

data_list = random.sample(range(100), 10)
selection_sort(data_list)
#출력결과 [9, 12, 13, 24, 53, 55, 69, 80, 87, 98]

 

알고리즘 분석

• 반복문이 두 개 O(n²)
• 실제로 상세하게 계산하면 n*(n-1) / 2