선택 정렬 (Selection Sort)

선택 정렬은 현재 위치에 들어갈 값을 찾아서 선택하는 알고리즘 이다.

 

값을 비교 하면서 찾기 때문에 비교 정렬 이라고도 할 수 있다.

데이터 (값)를 서로 교환 (스왑)하는 과정에서 임시 변수 (tmp) 공간을 필요로 한다.

 

이 말들이 추상적이기에 아래에 추가 설명이 필요 할듯 하다.

 

선택 정렬의 전체적인 흐름은 아래와 같다.

 

루프 첫번째 때 0번째 배열 의 값을 기준으로 잡는다.

 

1. 배열에서 최소값을 찾는다.

2. 최소값을 0번째 배열에 위치하는 값과 교환한다. // 교환 알고리즘 사용.

3. 다음 루프 부터는 기준이 되었던 앞 자리를 제외한 나머지 값들 중 최소값을 찾아 과정을 반복 한다.

 

글이라서 개념이 안잡힐 수 있기 때문에 그림을 보자.

 

 

마지막 8번째 루프는 돌지 않는 이유가 뒤에 더 이상 비교할게 없기 때문에, 굳이 참조를 해줄 필요가 없다.

그래서 조건을 배열 길이 - 1 로 잡아 준다.

 

이클립스 에서 구현 하기

 

 

[ 선택 정렬의 장점 및 단점 ]

 

장점

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

 

단점

1. 시간복잡도가 O(N2) 이다.

2. 안정 정렬이 아니다.

 

단점은 나중에 짚어 보겠다.

 

 

 

정리

 

선택 정렬이란 정렬 방식 중의 하나로 '최솟값' 혹은 '최대값'을 선택하여 정렬 하는 방식이다.

임시변수 tmp만 추가적으로 사용하나,

전체적으로 매우 적은 용량이기 때문에 "제자리 정렬"이라고도 불린다.

 

선택 정렬 말고도 그 밖에 많은 정렬 방법이 존재 하는 것을 알게 됬고, 정렬 알고리즘의 기초다 보니 성능상 좋지 않다는 것도 알게 되었다.

 

삽입 정렬, 거품 정렬, 셀 정렬, 힙 정렬, 기수 정렬 등 다른 종류 들도 다뤄보면 정렬 알고리즘에 대한 공부에 있어서 많은 도움이 될듯 하다.