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

선택 정렬

• 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘
• 최소값을 찾아 정렬하는 방식
• 평균과 최악 모두 수행 시간 복잡도는 O(n2)

Process (Ascending)

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

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

최선, 평균, 최악의 경우 시간복잡도는 O(n^2)

공간복잡도

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

장점

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

단점

• 시간복잡도가 O(n^2)으로, 비효율적
• 불안정 정렬(Unstable Sort)