Algorithm - 선택 정렬 (Selection Sort)

선택 정렬이란?

선택 정렬은 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식이다.

선택 정렬의 과정

1. 주어진 리스트 중 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다
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));
}

1. 우선, 위치(index)를 선택해준다.
2. i+1번째 원소부터 선택한 위치(index)의 값과 비교를 시작한다.
3. 오름차순이므로 현재 선택한 자리에 있는 값보다 순회하고 있는 값이 작다면, 위치(index)를 갱신해준다.
4. '2'번 반복문이 끝난 뒤에는 indexMin에 '1'번에서 선택한 위치(index)에 들어가야하는 값의 위치(index)를 갖고 있으므로 서로 교환(swap)해준다.

선택 정렬의 특징

• 정렬의 대상이 되는 데이터 외에 추가 데이터 공간을 필요로 하지 않기 때문에 제자리 정렬임
• 동일한 값을 가지는 원소들의 본래 순서가 보장되지 않기 때문에 불안정 정렬임

선택 정렬의 장단점

• 장점
  • 자료 이동 횟수가 미리 결정됨
  • 구현이 단순함
  • 비교 횟수는 많으나 실제 교환 횟수는 적음
  • 내림차순으로 정렬되어 있는 요소를 오름차순으로 재정렬할 때 효율이 좋음
• 단점
  • 안정성을 만족하지 않음
  • 값이 같은 레코드가 있는 경우 상대적인 위치가 변경될 수 있음
  • 이미 정렬된 상태에서 소수의 자료가 추가된 후 재정렬하면 비효율적임

시간 복잡도 & 공간 복잡도

n개의 주어진 배열을 정렬하는 데에 O(n^2)만큼의 시간이 걸리고 최선, 평균 최악의 경우 모두 동일한 시간 복잡도를 갖는다. 외부의 루프를 (n - 1)번 도는 동안 각 자리에 와야하는 최댓값을 구하기 위하여 n - 1, n - 2, ..., 1번 비교 연산을 수행하기 때문이다.
공간 복잡도는 주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(n)이다.