선택 정렬 - Selection Sort

선택정렬

선택 정렬의 흐름 ( 오름차순 정렬 기준 )

1. 기준 위치를 배열의 0번째 인덱스 부터 1씩 증가하며 N - 1번 째까지 반복
2. 기준 위치보다 인덱스가 더 큰 원소 중 가장 작은 값을 탐색 ( N - i - 1)번 반복
3. 탐색을 통해 발견 한 가장 작은 원소를 기준 위치의 원소와 교환

N = 5이고 인덱스가 0부터 시작인 배열의 선택 정렬

• 자바 코드

public class Main {
  static BufferedReader br = new BufferedReader(
    new InputStreamReader(System.in));
  static int N;
  // array : 크기가 N인 배열
  static int[] array;

  // standard : 기준 위치의 인덱스
  // findMin : 가장 작은 값을 찾기 위한 인덱스
  // Min : 가장 작은 값의 인덱스
  static void selection() {
    //1번
    for (int standard = 0; standard < N - 1; standard++) {
      int Min = standard;
      //2번
      for (int findMin = standard + 1; findMin < N; findMin++) {
        if (array[Min] > array[findMin]) {
          Min = findMin;
        }
      }
      //3번
      swap(standard, Min);
    }
  }

  static void swap(int standard, int min) {
    int temp = array[standard];
    array[standard] = array[min];
    array[min] = temp;
  }

  static void make() throws IOException {
    N = init();
    array = new int[N];
    for (int i = 0; i < N; i++) {
      array[i] = init();
    }
  }

  public static void main(String[] args) throws IOException {
    make();
    selection();
    result();
  }

  static int init() throws IOException {
    return Integer.parseInt(br.readLine());
  }

  static void result() {
    for (int num : array) {
      System.out.print(num + " ");
    }
  }
}

---

선택 정렬의 시간 복잡도

선택 정렬은 최선의 경우에도 평균적으로도 최악의 경우에도 모두 같은 시간복잡도를 가진다.

어떠한 경우의 배열이라도 수행해야하는 횟수가 정해져 있기 때문이다.

겉에 있는 반복문의 N - 1번 안에 있는 반복문이 (N - i -1)의 평균인 N / 2번 도는 2중 반복문이므로

$( N - 1 ) * ( N / 2 )$ 즉, $O(n) = N^2$이다.

최선	평균	최악	Run-time (60,000개)
$O(n) = N^2$	$O(n) = N^2$	$O(n) = N^2$	10.842 sec