[알고리즘] 선택 정렬 (Selection Sort) (정렬#2)

(2번째 정렬 Story)

선택 정렬

원리가 가장 간단한 알고리즘 중 하나로

오른쪽 리스에서 가장 작은 숫자를 선택하여 왼쪽 리스트로 이동작업을

오른쪽 리스트가 공백 상태가 될 때 까지 되풀이 하는 방법이다.




말로 하면 이해하기 힘드니

아래 그림을 보면 쉽게 이해를 할 것이다.

지금 5 3 8 1 2 7 이라는 오른쪽 공간이 있다.

여기서 가장 작은 수를 찾는 것이다.

그 작은 수를 왼쪽 공간에 차례로 넣어주면서

오른쪽 공간에서 더이상 수가 존재하지않으면

선택정렬은 종료가 되는 것이다.




하지만.... 항상 그래 왔듯이 

 여기에는 문제점이 있다.

그래 저번에 배운 공간 복잡도에 대해서
 
생각을 하지 않은 것이다.



위에서 표현하는 자료는 비록 6개의 자료를 담고 있지만

회사에서 사용하는 10만개가 넘어가는 자료들을 정렬한다면

10만개 만큼의 공간 즉,  자료의 크기만큼 임시 공간이 필요하다는 것이다.

당연히 우리는 이런걸 허용할 수 없다.




그래서... 뭐?

좀 개량해보자고 ㅡ,ㅡ;

자료공간을 효율적으로 사용할려면?



음.....

이런 방법은 어떨가?

왼쪽 데이터 공간 대신 오른쪽 공간에 위치하는 수와

자리를 바꾼다면, 즉 SWAP 한다면

오..... 그러면 되겠구나 !

 근데 난 이해가 잘안가는데,,,, 그림으로 설명해줘 ,ㅡ,ㅡ




자 봐보자

5 - 3 - 8 - 1 - 2 - 7  이라는 수를 정렬한다면




= 진행 =

5 - 3 - 8 - 1 - 2 - 7      작은 수를 찾는다       1
1 - 3 - 8 - 5 - 2 - 7      SWAP 한다              5 <-> 1
1 - 3 - 8 - 5 - 2 - 7      정렬 고정                1


1 - 3 - 8 - 5 - 2 - 7      작은 수를 찾는다       2
1 - 2 - 8 - 5 - 3 - 7      SWAP 한다              3 <-> 2
1 - 2 - 8 - 5 - 3 - 7      정렬 고정                2

1 - 2 - 8 - 5 - 3 - 7      작은 수를 찾는다      3
1 - 2 - 3 - 5 - 8 - 7      SWAP 한다              8 <-> 3
1 - 2 - 3 - 5 - 8 - 7      정렬 고정                3

1 - 2 - 3 - 5 - 8 - 7      작은 수를 찾는다      5
1 - 2 - 3 - 5 - 8 - 7      넘어간다                 5
1 - 2 - 3 - 5 - 8 - 7      정렬 고정                5

1 - 2 - 3 - 5 - 8 - 7      작은 수를 찾는다      7
1 - 2 - 3 - 5 - 7 - 8      SWAP 한다              8 <-> 7
1 - 2 - 3 - 5 - 7 - 8      정렬 고정                7

1 - 2 - 3 - 5 - 7 - 8      정렬 고정                5
1 - 2 - 3 - 5 - 7 - 8      넘어 간다                8
1 - 2 - 3 - 5 - 7 - 8      정렬 고정                8

1 - 2 - 3 - 5 - 7 - 8      종료                

이렇게 진행되는 정렬을 In-PlaceSort 이라 한다.



그럼 소스 코드를 한번 살펴보자

위의 소스를 가지고

5 - 1 - 7 - 4 - 2 - 6 -3 이라는 예제를 실행 해보자

그 결과를 차례로 나타낸 것이다.

이것 역시

시간 복잡도는 O(n^2) 이다

여기서 주의할 점은 그냥 SWAP문만 돌려도 되겠지만

자신의 자리는 이동하지 않도록 설계를 하면

시간을 많이 줄일 수 있다.




일반적인으로  비교연산 (위에서 if문)  1개가

이동연산 (SWAP) 3개보다

적게 걸린다는 것이다.


선택정렬은

문제점은 안전성을 만족하지 않는다는 것이다.

한마디로

값이 같은 레코드가 있는 경우

상대적인 위치가 변경될 수도 있다는 것이다.

.
.
.

선택 정렬에 대해서 다 알게 되었다면

리플을 남겨주세요 !