[C/C++]정렬 - 선택정렬 selection sort
이번 글을 시작으로 8개의 정렬을 작성해볼겁니다. 정렬들은 모두 오름차순으로 진행되며 복잡도 계산은 깊게 하지 않겠습니다.
선택정렬부터 시작합니다.
선택정렬은 오른쪽 배열에서 가장 작은 값을 "선택"하여 왼쪽 배열로 추가하는 작업입니다. 오른쪽 배열이 공백상태가 되면 정렬이 끝납니다.
정렬된 배열은 같은 크기의 새 배열에 넣는 것이 아니라 값의 교환을 통해 이루어집니다. 입력배열을 제외한 공간을 사용하지 않는 방식입니다.
void sort_selection(int list[], int size){
int least, tmp;
for(int i=0;i<size-1;i++){
least=i;
for(int j=i;j<size;j++){
if(list[j]<list[least]) least=j;
SWAP(list[i],list[least],tmp);
}
}
}매개 변수는 배열과 배열의 크기 입니다.
처음 시작할 때는 왼쪽 배열은 없고 오른쪽 배열만 있게 되므로 정렬할 배열의 시작이 왼쪽 배열이라고 생각하면 됩니다.
least의 의미는 오른쪽 배열 중 가장 작은 값의 인덱스 입니다. 이중 for문에서 내부 for문이 오른쪽 배열에서 값을 골라오는 내용입니다.
최소값을 찾으면 least에 오른쪽 배열의 최소값 위치인 j값 을 넣고, 값을 위치 i와 바꿔줍니다.
여기서 만약 현재위치의 값이 제일 작은 경우에는 자기자신과 위치를 바꾸게 됩니다. 제자리걸음이죠.
if(least!=i)를 SWAP에 조건으로 붙여서 제자리걸음하는 경우를 생략해줄 수 있습니다.
SWAP함수는 매크로 함수로 만들었습니다.
#define SWAP(x,y,t) ((t=x),(x=y),(y=t))주의점은 인수를 제 위치에 넣어야한다는 거죠. 일반 함수와 동일하게 사용합니다.
SWAP(list[i],list[least],tmp);이걸 해석해보면, 왼쪽 배열의 값과 오른쪽 배열의 값을 바꾼다는 이야기입니다. 이 문장의 least는 오른쪽 배열의 least가 됩니다.
외부 for문은 n-1번 작동하는 데, 이 이유는 매우 자연스럽습니다. 선택정렬을 하다보면 마지막에 남는 원소는 자연히 제일 큰 값이 되기 때문이죠. 그래서 n-1번 작동합니다.
선택정렬은 안정적이지 않은 정렬방법입니다.
안정적이라는 의미는, 동일한 키값이 여러개일 때 정렬 후에도 키값들의 상대적위치가 바뀌지 않는 것인데 선택정렬의 경우 상대적인 위치가 바뀌기도 하죠.
▣복잡도 계산
이중 for문에서 외부 for문의 반복횟수는 n-1번, 내부 for문의 반복횟수는 (n-1)-i번입니다.
내부 for문에서 비교연산이 n-1 + n-2 + n-3 + ... + 3 + 2 + 1 이 되면서 (n(n-1))/2로 O(n²)이 됩니다.
"댓글, 공감 버튼 한 번씩 누르고 가주시면 큰 힘이 됩니다"
