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

정렬 알고리즘을 배울때

가장 처음 배우는

선택 정렬 알고리즘

입니다.

이번 포스팅에서는

선택 정렬에 대해서

최대한 알기 쉽게

써보도록 하겠습니다.

선택 정렬

알고리즘의 과정은

모든 값들을 차례대로

돌면서 정렬기준에

맞는 값을 찾는

알고리즘 이죠.

간단히 예를 들면

제가 초등학생 때는

번호를 키 순으로

정했었는데요.

선생님이 모든 학생을

비교해 보고

가장 작은 학생들을

차례대로 줄세워 놓고

학생들의 번호를

매겼습니다.

이 과정이

선택 정렬 알고리즘

입니다.

그림으로 다시

설명해 보겠습니다.

설명하기에 앞서서

아래 그림처럼

원통의 색깔에

따라서 보시면 됩니다.

처음에 아래같은

정렬이 안된 배열이

있다고 하면

계속 루프를 돌면서

정렬이 완료 될 때 까지

아래의 사이클을 계속 돕니다.

최솟값으로 고정된 값을

제외한 모든 값들을

돌면서 가장 최솟값을 찾고

그 값을 최솟값으로 고정된

값의 바로 다음의 값으로

교체 합니다.

두번째 사이클을 돕니다.

그리고 두번째 최솟값

10을 찾습니다.

그다음 세번째 사이클을

돌면 다음 최솟값 26을

찾습니다.

4번째 사이클을 돌면

그다음 최솟값 32를 찾습니다.

만약 최솟값의 위치가 같다면

굳이 교체를 하지 않아도

됩니다.

마지막으로 사이클을 돌면

그다음 최솟값 48이

찾아 집니다.

이렇게 해서

아래처럼 정렬이

완료 됩니다.

소스코드로 표현하면

대략 아래같이

표현 됩니다.

(코드는 최대값 찾는걸로

되어 있네요.)

void Selection(int A[], int N) { for(int Last = N-1; Last >= 1; --Last) { int Largest = 0; for(int Current = 1; Current <= Last; Current++) { if (A[Current] > A[Largest]) { Largest = Current; } } int Temp = A[Last]; A[Last] = A[Largest]; A[Largest] = Temp; } }

참조

C.C++ 로

배우는 자료구조론

선택 정렬의

복잡도는

아래와 같습니다.

사실 간단하긴 하지만

효율적이지는 않죠.

이상 선택 정렬

알고리즘 이었습니다.