[알고리즘] 선택 정렬 (Selection Sort) - 자바 Java

[ 개념 ] 

원소를 넣을 위치는 정해져 있고, 저장된 자료로부터 어떤 원소를 넣을지를 선택하는 알고리즘
- 제자리 정렬 알고리즘의 하나로, 자리를 선택하고 그 자리에 오는 값을 찾는 알고리즘

[ 과정 설명 (오름차순) ] 

- 첫 번째 순서에서는 첫 번째 위치에 배열의 최소값을 찾아 넣어준다.
- 두 번째 순서에서는 두 번째 위치에 배열의 남은 값 중에서의 최소값을 넣어준다.

 

[ 코드 예시 (오름차순) - 자바 Java ]

public class SelectionSort {
	
  public static void main(String[] args) {
    int[] nums = {9, 5, 6, 2, 4};
    selectionSort(nums);
  }

  public static void selectionSort(int[] arr) {
    selectionSort(arr, arr.length);
  }

  private static void selectionSort(int[] arr, int arrSize) {
    for (int i = 0; i < arrSize - 1; i++) {
      int idx = i;
      for (int j = i + 1; j < arrSize; j++) {
        if(arr[j] < arr[idx]) {
          idx = j;
        }
      }
      
      swap(arr, i, idx);
    }
  }

  // 원소들의 자리를 바꿔주는 메소드 선언.
  private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }

}

[ 시간 복잡도 ] 

- 외부 루프를 N-1번 도는 동안, N-1, N-2, N-3, ..., 1번 원소들간 비교
- T(n) = (n-1) + (n-2) + (n-3) + ... + 1 = (n-1) * n / 2

- O(n) = n^2