선택정렬(Selection Sort) C++ / 장단점 / 시간복잡도 / 공간복잡도 :: DANIDANI

알고리즘 개념

• 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘
• 첫 번째 자리에는 첫 번째~마지막 원소 중 가장 작은 원소를, 두 번째 자리에는 두 번째~마지막 원소 중 가장 작은 원소를...

과정

1. 주어진 배열에서 최솟값을 찾는다.
2. 그 최솟값과 맨 앞에 위치한 값을 교체한다.(swap)
3. 맨 앞에 위치한 값을 제외한 나머지 배열에 대해서 같은 방법으로 교체한다.

코드

for (int i = 0; i < n; i++){
        int minIdx = i;
        for (int j = i + 1; j < n; j++){
            if (arr[j] < arr[minIdx])
                minIdx = j;
        }
        int temp = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = temp;
}

장점

• 구현이 간단하고 단순하다.

단점

• 성능이 좋지 않다(O(n^2))

시간 복잡도

• (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2
• 최선, 평균, 최악 모두 O(n^2)

공간복잡도

• O(n)
• 별도의 메모리 공간이 필요하지 않은 제자리 정렬(in-place sorting)

---

정렬 알고리즘 시간 복잡도 정리

정렬	최선	평균	최악
선택정렬(Selection Sort)	O(n^2)	O(n^2)	O(n^2)
거품정렬(Bubble Sort)	O(n^2)	O(n^2)	O(n^2)
삽입정렬(Insertion Sort)	O(n)	O(n^2)	O(n^2)
퀵정렬(Quick Sort)	O(nlogn)	O(nlogn)	O(n^2)
병합정렬(Merge Sort)	O(nlogn)	O(nlogn)	O(nlogn)
힙정렬(Heap Sort)	O(nlogn)	O(nlogn)	O(nlogn)