[Algorithm] 선택 정렬 Selection Sort

정의

선택 정렬은 버블 정렬과 비슷한 알고리즘이지만, 지정된 순서에 원소를 넣을 곳이 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다.
간단하게 말하자면 특정 자리에 올 원소를 선택해서 바꾸는 것이다.
 

과정

1. 배열에서 가장 최소값을 찾는다.
2. 맨 첫번째 원소와 교체
3. 그 다음 위치에도 1번과 2번을 반복해서 교체
 

코드 및 풀이

public class Main {
  public static void main(String[] args) {
    int[] arr = { 64, 32, 15, 23, 33, 10 };

    selectionSort(arr);

    System.out.println("Sorted array:");

    for (int num : arr) {
      System.out.println(num + " ");
    }
  }

  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[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;

      
    }
  }
}

• 내부 for 문에서 최소값을 찾기 위한 비교만 하고, 원소 교환은 외부 for 문에서 진행을 하여서 교환 연산의 수를 줄인다.

 

시간복잡도

• 최선, 평균 및 최악의 경우
  • 외부 for문에서 n-1번 수행
  • 내부 for문에서 n-1, n-2 ~ 1번 실행
  • 따라서 n-1 + n-2 + ... + 1 = N(N-1) / 2 = O(N^2)
• 선택 정렬은 비교 정렬 알고리즘이기 때문에 최선의 경우에도 모든 배열을 방문한다. 그러므로, 최선, 평균 및 최악의 경우에 동일한 O(N^2)의 복잡도를 가진다.

공간복잡도

• 추가적인 공간을 요구하지 않는 정렬
  
  • 입력받은 배열에서 정렬이 수행된다.
• 그러므로 O(1)

장점

1. 구현이 간단하고 이해하기 쉽다.
2. 추가 메모리 공간을 요구하지 않는다.

단점

1. 시간 복잡도가 O(N^2) 이기에 대규모 데이터에 대해 비효율적이다.
2. 배열의 상태와 관계없이 항상 동일한 수행 시간을 가진다.
3. 불안정 정렬이다.