2. 선택 정렬(Selection Sort) - O(n2)

선택 정렬은 말 그대로 현재 위치에 들어갈 데이터를 찾아 선택하는 알고리즘이다.

 

데이터를 비교하며 들어가기 때문에 "비교정렬"

정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않기 때문에  "제자리 정렬"

마지막으로 "불안정 정렬"이다.

 

---

과정을 알아보자

1. 주어진 리스트에서 최솟값을 찾는다.
2. 최솟값을 맨 앞 자리의 값과 교환한다.
3. 맨 앞 자리를 제외한 나머지 값들 중 최솟값을 찾아 위와 같은 방법으로 반복한다.

손으로 만든거라 양해 부탁드립니다...

저런식으로 배열을 하는것이 선택 정렬이다 

 

중요한것이 있다

그림으로는 표현하지 않았지만 index8까지는 계속해서 정렬하고 마지막 인덱스를 제외하고 정렬을 마친다

그 이유는 N-1개가 정렬이 되어있다는 뜻으로 결국 마지막 원소는 자연적으로 최댓값이 되었다는 뜻이다.

 

 

구현은 나의 깃허브에 해놓았다 시간이 된다면 보는것을 적극 추천한다

https://github.com/ProblemSolveStudy/Tae_sik/tree/master/Sorts

GitHub - ProblemSolveStudy/Tae_sik

 

선택 정렬의 장점 및 단점

 

◐ 장점

 = 추가적인 메모리 소비가 작다.

순서를 바꿀때 굳이 다른 메모리를 사용하여 저장소를 두지않고 본인들끼리 바꾼다.

 

 

◑ 단점

 = 시간복잡도가 O(n2)이다

선택정렬은 N(N - 1) / 2를 가지고 있다.

즉 O(n2)으로 이는 정렬중에서도 굉장히 느린 속도라고 할 수 있다.

 

= 안정정렬이 아니라는것이다.

예를 들자면 우리가 key와 value가 있는 배열을 받았다.

[(국자, 20), (강준, 30), (동영, 35),(강기, 30)]

여기서 먼저 이름으로 정렬을 한다하면

이렇게 정렬될것이고

[(강기, 30),(강준, 30), (국자, 20), (동영, 35)]

 

우선 숫자로 나열하면

1. [(국자, 20), (강준, 30), (강준, 30), (동영, 45)]

국자와 강준을 비교하여 자리를 바꿔주었는데

숫자를 비교하는 중이라 여기서 더이상 나아가지 못한다.

 

이래서 불안정 정렬이다

 

시간복잡도

	시간복잡도
Counting Sort(계수 정렬)	O(n)
Select Sort(선택 정렬)	O(n2)