[알고리즘] 선택정렬

선택 정렬(selection sort) 알고리즘 개념 요약

• 제자리 정렬(in-place sorting) 알고리즘의 하나

  • 입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법

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

  • 첫 번째 순서에는 첫 번째 위치에 가장 최솟값을 넣는다.

  • 두 번째 순서에는 두 번째 위치에 남은 값 중에서의 최솟값을 넣는다.

• 과정 설명

  1. 주어진 배열 중에서 최솟값을 찾는다.

  2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).

  3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

  4. 하나의 원소만 남을 때까지 위의 1~3 과정을 반복한다.

선택 정렬(selection sort) 알고리즘의 구체적인 개념

• 선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다.

• 1회전을 수행하고 나면 가장 작은 값의 자료가 맨 앞에 오게 되므로 그 다음 회전에서는 두 번째 자료를 가지고 비교한다. 마찬가지로 3회전에서는 세 번째 자료를 정렬한다.

선택 정렬(selection sort) 알고리즘의 예제

배열에 9, 6, 7, 3, 5가 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자.

• 1회전:

  첫 번째 자료 9를 두 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 첫 번째 위치에 옮겨 놓는다. 이 과정에서 자료를 4번 비교한다.

• 2회전:

  두 번째 자료 6을 세 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 두 번째 위치에 옮겨 놓는다. 이 과정에서 자료를 3번 비교한다.

• 3회전:

  세 번째 자료 7을 네 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 세 번째 위치에 옮겨 놓는다. 이 과정에서 자료를 2번 비교한다.

• 4회전:

  네 번째 자료 9와 마지막에 있는 7을 비교하여 서로 교환한다.

선택정렬 코드

void selectionSort(int[] arr) {
    int indexMin, temp;
    for (int i = 0; i < arr.length-1; i++) {        // 1.
        indexMin = i;
        for (int j = i + 1; j < arr.length; j++) {  // 2.
            if (arr[j] < arr[indexMin]) {           // 3.
                indexMin = j;
            }
        }
        // 4. swap(arr[indexMin], arr[i])
        temp = arr[indexMin];
        arr[indexMin] = arr[i];
        arr[i] = temp;
  }
  System.out.println(Arrays.toString(arr));
}

시간복잡도

데이터의 개수가 n개라고 했을 때,

첫 번째 회전에서의 비교횟수 : 1 ~ (n-1) => n-1

두 번째 회전에서의 비교횟수 : 2 ~ (n-1) => n-2

...

(n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2

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