선택 정렬

1. 선택 정렬(selection sort)란?

• 다음과 같은 순서를 반복하며 정렬 하는 알고리즘
  • 주어진 데이터 중, 최소값을 찾음
  • 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함
  • 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복

 

출처 : 위키피디아

2. 선택 정렬 코드 연습

 

데이터가 두 개일 때

data_list = [8, 4]

if data_list[0] > data_list[1]:
    data_list[0], data_list[1] = data_list[1], data_list[0]

데이터가 세 개 이상일 때

data_list = [8, 4, 2]

for index in range(len(data_list)-1):
    for index2 in range(len(data_list)-1):
        if data_list[index2] > data_list[index2+1]:
            data_list[index2], data_list[index2+1] = data_list[index2+1], data_list[index2]

 

3. 알고리즘 구현

1. for stand in range(len(data_list)-1)로 반복
2. 가장 작은 값 저장 위해 lowest = stand로 인덱스 저장
3. for num in range(stand, len(data_list)) stand+1부터 배열 끝까지 반복
4. 내부 반복문 안에서 dat_list[lowest] > data_list[num] 이면 lowest에 num 저장
5. 반복문 벗어난 후(값 전부 체크 후) data_list[lowest]와 data_list[stand] 값을 바꿔줌

def selectionSort(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)
print(data_list)

selectionSort(data_list)
print(data_list)

출력값 : [33, 66, 87, 3, 91, 41, 32, 48, 73, 83]

           [3, 32, 33, 41, 48, 66, 73, 83, 87, 91]

 

4. 알고리즘 분석

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