선택 정렬

제일 간단한 정렬 중 하나로, 사람이 하는 정렬과 굉장히 유사합니다.

배열의 앞 인자부터 하나하나 선택하여 정렬하므로 선택 정렬이라는 이름이 생겼습니다.

당연히 효율적이지는 않겠죠..

 

 

특징

• 비교 횟수는 많으나, 교환 횟수는 상당히 적음
• 역순 정렬일 때, 최적의 효율을 보여줌 (정렬할 인자가 많음)
• 반대로, 정렬할 인자가 적을 때는, 최악의 효율
• 비교 특성 상 맨 앞으로 순차적으로 정렬이 됩니다

시간 복잡도

• 최악: O (n^2)
• 최선: O (n^2)
• 평균: O (n^2)

시간 복잡도는 굉장히 비 효율적인 편입니다.

예시 그림

구현 코드

void selectionSort(int arr[], int size) {
    int minIndex;
    int i, j;
    for (i = 0; i < size - 1; i++) {
        minIndex = i;
        for (j = i + 1; j < size; j++) 
            if (arr[j] < arr[minIndex])
                minIndex = j;
         
        swap(&arr[i], &arr[minIndex]);
    }
}