선택 정렬(Select sort)

: 제자리 정렬 알고리즘. 가장 작은원소를 찾아 첫번째 자리에, 그 다음을 찾아 두번째 자리에 .... 이러한 방식으로 진행

• 기본적으로 O(n^2) 의 시간복잡도를 갖는다.
• 장점: 자료 이동 횟수가 미리 결정됨
• 단점: 값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다.
  • 정렬 안정성을 만족하지 않는다. -> 안정성 있게 구현도 가능할 것 같다.
• 교환(이동) 횟수: 3(n - 1) (SWAP함수 작업)

제자리 정렬(in-place)

: 배열 내에서 정렬하기 때문에 따로 메모리 공간이 필요 없다.

정렬에서의 안정성

: 키 값이 같은 원소들끼리 “정렬되기 전의 순서”와 “정렬되고 나서의 순서”가 유지되는가 되지 않는가?

코드

void selectSort(int data[], int size) {
    for(int i = 0; i < size; i++) {
        int idx = i;
        for(int j = i + 1; j < size; j++) {
            if(data[idx] > data[j]) {
                idx = j;
            }
        }
        
        int tmp = data[i];
        data[i] = data[idx];
        data[idx] = tmp;
    }
}

Reference)

https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC

https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html