[알고리즘] 선택 정렬 Selection Sort

    해당 순서에 넣을 넣을 위치는 이미 정해져 있고, 그 위치에 어떤 원소를 넣을지 선택하는 방법이다. 그 원소의 index값을 저장하고 있다.

• 불안정 정렬(unstable sort)
• 제자리 정렬(In-place)
• Bubble Sort와 유사하지만 실제 교환이 일어나는 횟수가 적다.
      

  1. 주어진 배열의 최소값을 찾는다.
  2. 그 갚을 맨 앞에 위치한 값과 교체한다.
  3. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.
  4. 하나의 원소만 남을 때 까지 1~3을 반복한다.

• 코드

#include <iostream>

using namespace std;

int main() {
    int data[] = {9, 6, 7, 3, 5};
    
    for(int i=0; i<4; i++){             
        int index = i;
        for(int j=i+1; j<5; j++){      
            if(data[j]<data[index]){    
                index = j;
            }
        }
        int temp = data[index];
        data[index] = data[i];
        data[i] = temp;
    }

    return 0;
}

• 시간복잡도: O(n^2)

  시간복잡도
  최선	Ω(n^2)
  평균	Θ(n^2)
  최악	O(n^2)

  (n-1) + (n-2) + (n-3) + .... + 2 + 1 = n(n-1)/2
  첫 번째 순회에서 1~(n-1)까지 n-1번 비교, 두 번째 순회에서 2~(n-1)까지 n-2번 비교 ...
  최악, 평균, 최선의 경우 시간복잡도가 모두 같다

• 공간복잡도: O(1)

참고 링크