[알고리즘]선택 정렬(Select Sort)

선택 정렬>

다음과 같은 순서를 반복하며 정렬하는 알고리즘

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

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

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

 

참조 사이트>

https://visualgo.net/bn/sorting

VisuAlgo - Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix)

 

참조 동영상>

 

 

정렬 그리기>

데이터 구조가 이렇게 이렇게 되어있다고 생각하면

이를 선택 정렬을 한다고 하면

최솟값을 찾아보면 2 를 찾을수 있다.

이를 기준점인 17과 비교하면 2가 작으므로 맨 앞으로 보낸다.

이렇게 해서 한칸씩 옆으로 가면서 비교 하여 작은것이 선택되서 앞으로 오는 과정을 하면 된다.

이렇게 정렬을 하면 최종적으로 정렬된것은

위와 같은 데이터 구조가 될것이다.

 

참고 Code>

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

 

Python Code>

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
    
data_list = [17, 6, 8, 11, 2, 3]
print(selection_sort(data_list))

 

결과값>

[2, 3, 6, 8, 11, 17]