선택 정렬 selection sort

제자리 정렬 알고리즘

• 장점

  • 구현이 쉽다.
  • 제자리 정렬(추가 저장 공간이 필요 없음)

• 단점

  • 데이터의 양에 유연하지 않습니다.

알고리즘 구현

1. 목록에서 최소값을 찾습니다.
2. 찾은 최소값을 맨 앞의 값(혹은 현재 위치의 값)과 교체합니다.
3. 배열의 전체 요소가 정렬될 때까지 이 과정을 반복합니다.

void selctionSort(int[] list, int n) {
    int i, j, min, temp;
    for (i = 0; i < n - 1; i++) {
        min = i;
        for (j = i + 1; j < n; j++) {
            if (list[j] < list[min]) {
                min = j;
            }
        }
        temp = list[min];
        list[min] = list[i];
        list[i] = temp;
    }
}

 

성능

최악의 경우 복잡도 O(n²)

최선의 경우 복잡도 O(n)

평균 복잡도 O(n²)

최악의 경우 공간 복잡도 O(1) 보조공간