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

선택 정렬 (Selection Sort)

최소 또는 최대 값을 찾아서 가장 앞 또는 뒤와 교환하며 정렬하는 방식

시간복잡도 : (n-1) + (n-2) + ... + 2 + 1 -> n(n-1)/2 즉, O(n^2)

공간복잡도 : O(n)

장점

• 구현이 간단하고 이해하기 쉽다.
  • 기본적인 비교와 교환 과정으로 이루어져 있어서 이해하기 쉽고 구현하기도 간단하다.
    
    
• 추가적인 메모리 공간을 사용하지 않는다.
  • 버블 정렬과 동일하게 주어진 배열 안에서 비교와 교환을 수행하므로, 정렬을위한 추가적인 메모리 공간이 필요하지 않다.
    
    

단점

• 성능이 비효율적이다.
  • 비교와 교환을 인접한 두 원소에 대해 반복적으로 수행하기 때문에 성능이 비효율적이다.
  • 배열의 킉가 커질수록 비교과 교환의 횟수가 증가하여 실행 시간이 길어진다.
• 불안정한 정렬 알고리즘이다. (Unstable Sort)
  • 선택 정렬은 값이 같은 두 요소의 순서를 보존하지 않는다. 따라서 정렬 후에 값이 같은 요소들의 상대적인 순서가 변경될 수 있다.
    
    
• 최적의 경우에도 연산이 많이 필요하다.
  • 버블 정렬과 마찬가지로 이미 정렬되어 있는 경우에도 모든 비교와 교환을 수행한다. 따라서 최선의 경우에도 비교횟수를 줄일 수 있는 최적화가 존재하지 않는다.

선택 정렬 구현

public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        // 최솟값의 인덱스
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // 최솟값과 현재 위치의 원소 교환
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}