TIL D-66 선택정렬 Selection Sort

오늘 배운 것>

• 정렬 알고리즘 - 선택 정렬(selection sort), 카운팅 정렬(counting sort)

1.    정렬 알고리즘은 ‘정렬되지 않은 상태에서 같은 키값을 가진 원소의 순서가 정렬 후에도 유지된다면’ 안정 정렬(stable sort)로 구분한다. 

예를 들어, 4(1) 5 3 4(2) 1을 선택정렬(selection sort)한다면 선택정렬은 최소값을 찾아서 이 최소값을 배열의 첫번째 요소와 교환한다. 따라서 선택정렬의 과정은 다음과 같다.

4(1) 5 3 4(2) 1

1 5 3 4(2) 4(1)

1 3 5 4(2) 4(1)

1 3 4(2) 5 4(1)

1 3 4(2) 4(1) 5

 

그 결과 4(1)과 4(2)의 순서가 바뀌었음을 알 수 있다.

이를 해결하여 안정 정렬로 만들기 위해서는 최소값을 배열의 첫번째 요소와 교환하는 대신, 최소값을 첫번째 자리에 삽입하고 나머지 요소들을 뒤로 푸시하는 방법이 있다.

 

 

따라서 P1 input data의 stable sort 결과는 다음과 같다.

Stable sorting result