자료의 정렬 - 선택 정렬(Select sorting)

선택 정렬(Select sorting)

나열된 숫자들 중 작은 순서대로 찾아서 왼쪽으로 정렬하는 방법.

최소값을 찾아 맨 앞으로 이동시키는 단순한 정렬 방법이다.

선택정렬(Select sorting)의 방법

 ① 주어진 리스트중에서 최소값을 찾는다.

 ② 그 값을 맨 앞에 위치한 값과 교체한다.

 ③ 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

선택정렬(Select sorting)의 예시

1. 20, 7, 12, 8을 선택정렬을 이용하여 배열해보자.

위 숫자를 배열해보자.

첫 번째 숫자와 교환하고 난 후

가장 작은 항목을 찾아 첫 번째 숫자와 비교하고 자리를 바꾼다.

두 번째 숫자와 교환하고 난 후

가장 작은 항목을 찾아 두 번째 숫자와 비교하고 자리를 바꾼다.

가장 작은 항목을 찾아 세 번째 숫자와 비교하고 자리를 바꾸려고 했지만,

세 번째 숫자가 더 작으니 이대로 놔두고 정렬완료.

2. 8, 31, 48, 73, 3, 65, 20, 29, 11, 15를 선택정렬을 이용하여 배열해보자.

위 배열을 정렬해보자.

가장 큰 수(73)인 찾고, 맨 오른쪽 수(15)와 자리를 바꾼다.

맨 오른쪽 수를 제외한 나머지에서 가장 큰 수(65)를 찾고, 맨 오른쪽 수(11)와 자리를 바꾼다.

맨 오른쪽 두 수를 제외한 나머지에서 가장 큰 수(48)를 찾고, 위와 같은 과정을 반복한다.

8을 맨 오른쪽 수(3)와 자리 바꾼다. 정렬완료.

선택정렬(Select sorting)의 알고리즘

코드 및 내용 참고

https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

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

선택정렬(Select sorting) 특징

  -시간복잡도: O(n²)

 

메모리가 제한적인 경우에 사용시 성능 상의 이점이 크다.

 

 

도움되는 사이트

  - https://visualgo.net/en/sorting

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

정렬되는 모습을 실시간으로 보여주는 사이트이다.

사진으로 보는것보다 직접 정렬되는 모습을 보면 이해하기 더욱 쉽다.