[Algorithms] 단순 선택 정렬(Straight Selection Sort)

깃허브: https://github.com/PSLeon24/DataStructure/blob/main/Sorting%20algorithm.ipynb

기본 정렬(Sorting algorithms)

기본 정렬의 종류

선택 정렬, 버블 정렬, 삽입 정렬

오늘은 이 중 먼저 가장 이해하기 쉬운 선택 정렬부터 학습하고자 함

 

단순 선택 정렬(Straight Selection Sort)

단순 선택 정렬: 가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하며 정렬하는 알고리즘

리스트 Arr[0...n-1]에서 가장 작은 원소를 찾아 리스트의 맨 앞자리 원소 A[n-1]과 자리를 swap

그러면 swap된 가장 작은 원소는 자기 자리를 찾았으므로 fix됨(즉, 가장 왼쪽에 자리 잡은 원소에 관해서는 정렬이 끝남)

이제 이 원소를 제외한 나머지 원소들인 A[1...n-1]를 대상으로 같은 작업을 반복하면 됨

https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC

단순 선택 정렬에서 교환 과정

https://www.hackerearth.com/practice/algorithms/sorting/selection-sort/tutorial/

1. 아직 정렬하지 않은 부분에서 값이 가장 작은 원소 a[min]을 선택

2. a[min]과 아직 정렬하지 않은 부분에서 맨 앞에 있는 원소를 교환(swap)

 

[23, 78, 45, 8, 32, 56]의 데이터로 이루어진 임의의 배열을 선택 정렬로 정렬을 수행하면 아래와 같이 손 로직을 돌릴 수 있다.

총 6번의 과정을 진행하며 매 과정에서 정렬되지 않은 원소 부분에서 최솟값을 선택해 맨 앞에 있는 원소와 교환하는 것을 반복하는 것을 확인할 수 있고, 최종적으로 fix된 데이터들을 형광펜으로 이어보면 삼각형 모양이 나타남을 확인할 수 있다.

 

파이썬 실습

단순 선택 정렬 알고리즘의 원솟값을 비교하는 횟수: (n²-n)/2

ex) 위 예제에서 배열의 크기 len(arr) = 10 → (100 - 10)/2 = 45

 

단순 선택 정렬 알고리즘의 단점

서로 이웃하지 않는 떨어져 있는 원소를 교환하므로 안정적이지 않음(unstable)

Do it 자료구조와 함께 배우는 알고리즘 입문(파이썬 편) p.239

위 그림에서 값이 3인 원소는 3L과 3R, 2개 있음

이 배열은 정렬한 후 두 원소(3L, 3R)의 순서가 바뀌었음을 확인할 수 있음

따라서, 중본된 값으로 정렬이 필요 없는 데이터인 3L과 3R의 위치를 바꾸었으므로 이 알고리즘은 안정적이지 않음