[Algorithm] 선택 정렬 (Selection Sort)

선택 정렬 (Selection Sort)

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

Selection Sort와 Insertion Sort를 헷갈려하는 사람들이 종종 있는데, Selection Sort는 배열에서 해당 자리를 선택하고 그 자리에 오는 값을 찾는 것이라고 생각하면 편하다.

 

프로세스

1. 주어진 배열 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다. (pass)
3. 1회전을 수행하고 나면 가장 작은 값의 자료가 맨 앞에 오게 되므로 그 다음 회전에서는 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.
4. 하나의 원소만 남을 때까지 위의 1~3 과정을 반복한다.
   

 

ex)

• 1회전
  
  • 첫 번째 자료 9를 두 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 첫 번째 위치에 옮겨 놓는다. 이 과정에서 자료를 4번 비교한다.
• 2회전
  
  • 두 번째 자료 6을 세 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 두 번째 위치에 옮겨 놓는다. 이 과정에서 자료를 3번 비교한다.
• 3회전
  • 세 번째 자료 7을 네 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 세 번째 위치에 옮겨 놓는다. 이 과정에서 자료를 2번 비교한다.
• 4회전
  • 네 번째 자료 9와 마지막에 있는 7을 비교하여 서로 교환한다.

var selectionSort = function(array) {
  var length = array.length;
  var minIndex, temp, i, j;
  for (i = 0; i < length - 1; i++) { // 처음부터 훑으면서
    minIndex = i;
    for (j = i + 1; j < length; j++) { // 최솟값의 위치를 찾음
      if (array[j] < array[minIndex]) {
        minIndex = j;
      }
    }
    temp = array[minIndex]; // 최솟값을 저장
    array[minIndex] = array[i];
    array[i] = temp; // 최솟값을 제일 앞으로 보냄
  }
  return array;
};

selectionSort([5,1,4,7,2,6,8,3]); // [1,2,3,4,5,6,7,8]

 

시간복잡도

평균	최선	최악
Θ(n^2)	Ω(n^2)	O(n^2)

• 비교 횟수
  • 두 개의 for 루프의 실행 횟수
  • 외부 루프: (n-1)번
  • 내부 루프(최솟값 찾기): n-1, n-2, … , 2, 1 번
  • 데이터의 개수가 n개라고 했을 때,
    • 첫 번째 회전에서의 비교횟수 : 1 ~ (n-1) => n-1
    • 두 번째 회전에서의 비교횟수 : 2 ~ (n-1) => n-2
    • ...
    • (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2
• 교환 횟수
  
  • 외부 루프의 실행 횟수와 동일. 즉, 상수 시간 작업
  • 한 번 교환하기 위하여 3번의 이동(SWAP 함수의 작업)이 필요하므로 3(n-1)번

T(n) = (n-1) + (n-2) + … + 2 + 1 => n(n-1)/2 => O(n^2)

비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 배열을 정렬하는데 O(n^2) 만큼의 시간이 걸린다. 최선, 평균, 최악의 경우 시간복잡도는 (n^2)으로 동일하다.

공간복잡도

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

 

장점

• 자료 이동 횟수가 미리 결정된다.
• Bubble sort와 마찬가지로 알고리즘이 단순하다.
• 정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료상태에서 비교적 효율적이다.
• Bubble Sort와 마찬가지로 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. => 제자리 정렬(in-place sorting)

단점

• 시간복잡도가 O(n^2)으로, 비효율적이다.
• 불안정 정렬(Unstable Sort) 으로 안정성을 만족하지 않는다.
  • 즉 값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다.

 

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

• 단순(구현 간단)하지만 비효율적인 방법
  • 삽입 정렬, 선택 정렬, 버블 정렬
• 복잡하지만 효율적인 방법
  • 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬