반응형
선택 정렬은 정렬 알고리즘의 한 방법입니다.
버블 정렬과 마찬가지로 간단한 정렬 알고리즘에 속합니다.
가장 작은(혹은 큰) 값을 찾아서 맨 앞(혹은 맨 뒤)로 차곡차곡 이동시키는 방법입니다.
기본적으로 생각할 수 있는 방법으로 정렬합니다.
선택 정렬의 코드는 다음과 같습니다.
#include <iostream> using namespace std; template <class T> void MySwap(T& a, T &b) { T tmpVal = a; a = b; b = tmpVal; } template <class T> void SelectionSort(T* arVal, int nCount) { int maxidx; int i, j; for (i = nCount - 1 ; i >= 0 ; --i) { for (maxidx = i, j = i - 1 ; j >= 0 ; --j) { if (arVal[maxidx] < arVal[j]) maxidx = j; } if (maxidx != i) MySwap(arVal[maxidx], arVal[i]); } } int main() { int arNoSort[10] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 }; for (int i = 0; i < sizeof(arNoSort) / sizeof(int); ++i) { cout << arNoSort[i] << " "; } cout << endl; SelectionSort(arNoSort, sizeof(arNoSort) / sizeof(int)); for (int i = 0; i < sizeof(arNoSort) / sizeof(int); ++i) { cout << arNoSort[i] << " "; } cout << endl; }
C++의 템플릿 버전입니다.
위의 코드는 가장 큰 값을 기준으로 맨 뒤로 이동시키는 코드입니다.
약간만 수정하면 가장 작은 값을 앞으로 이동시키는 방법을 사용할 수도 있습니다.
맨 뒤에서 앞까지 이동하면서 가장 큰 값의 위치를 찾습니다.
그리고 맨 앞까지 이동해서 가장 큰 값의 위치가 확정되면 가장 큰 값과 맨 뒤의 값의 위치를 변경합니다.
맨 뒤의 값은 이미 가장 큰 값이기 때문에 그 앞부터 이동하면서 다시 가장 큰 값을 찾습니다.
다시 찾았으면 맨 뒤의 값 앞에 위치시킵니다.
값이 맨 뒤를 기준으로 차곡차곡 이동하는 것을 확인할 수 있습니다.
간단한 정렬 알고리즘이기 때문에 이해하는 것이 어렵지는 않을 것입니다.
반응형
'Programming > Algorithm' 카테고리의 다른 글
[정렬 알고리즘] 퀵 소트(Quick Sort) (0) | 2018.05.18 |
---|---|
2개의 스택(Stack)으로 큐(Queue) 구현하기 (0) | 2017.03.15 |
[정렬 알고리즘] 삽입 정렬(Insertion Sort) (0) | 2015.02.12 |
[정렬 알고리즘] 버블 소트(거품정렬) (0) | 2014.12.07 |
간단한 GCD 알고리즘(Euclid 호제법) (0) | 2014.11.21 |