[알고리즘] Selection Sort

Abstract

Selection Sort는 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘 이다.

Process(Ascending)

1. 주어진 배열 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다.
3. 맨 처음 위치를 제외한 나머지 배열을 같은 방법으로 교체한다.

C++ Code(Ascending)

#include <iostream>
#include <vector>
using namespace std;

void SelectionSort(vector<int> arr){
  int indexMin, temp = 0;
  for(int i=0; i<arr.size()-1; i++){    // 1
    indexMin = i;
    for (int j=i+1; j<arr.size(); j++){ // 2
      if(arr[j] < arr[indexMin]){       // 3
        indexMin = j;
      }
    }
    swap(arr[indexMin], arr[i]);        // 4
  }
}

주석 설명

1. 범위에서 가장 작은 값이 들어갈 위치를 선택한다.
2. i+1번째 인덱스에서부터 끝까지 값을 확인한다.
3. 범위에서 가장 작은 값을 찾아서 인덱스를 indexMin에 저장한다.
4. indexMin 위치의 값과 가장 작은 값이 들어갈 위치의 값을 교환한다.

GIF로 이해하는 Selection Sort

시간복잡도

(n-1) + (n-2) + (n-3) + ... + 2 + 1 ➡ n(n-1)/2 이므로 시간복잡도는 O(n^2).
정렬 여부에 상관없이 비교를 하기 때문에 최선, 평균, 최악의 경우 모두 O(n^2).

공간복잡도

주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(n).

장점

• 구현이 매우 간단하고 소스코드가 직관적이다.
• 정렬하려는 배열 안에서 교환하는 제자리 정렬(in-place sorting) 방식이므로 다른 메모리 공간이 필요하지 않다.
• 정렬을 위한 비교횟수는 많지만, Bubble Sort 에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료상태에서 비교적 효율적이다.

단점

• 시간복잡도가 최악, 최선, 평균 모두 O(n^2)로 비효율적이다.
• 동일한 값에 대해 기존의 순서가 유지되지 않는 불안정 정렬(Unstable Sort) 입니다.

참고 사이트

선택 정렬
안정 정렬과 불안정 정렬