기본 정렬 - Selection sort(선택 정렬)

정렬 방법

전체(n개의 값)에서 가장 큰 값을 맨 오른쪽 값과 바꾸고, 그 다음엔 맨 오른쪽 칸을 제외한 나머지 값들 중 가장 큰 값을 맨 오른쪽값과 바꾸고, ... 이렇게 바꾸는 과정을 진행하다가 마지막으로 2개가 남으면 그 둘을 비교 후 정렬하면 정렬이 완료된다.

정렬 과정

 

n 크기의 임의의 배열 arr에서(이때, 코드에서 key는 min과 max로 작성하였음.)

 

<1단계> - n-1번의 비교

 

arr[0]의 인덱스 값을 key값으로 둔 후,

 

arr[key]와 arr[1] 비교 후 큰 값의 인덱스 값을 key에 넣고,

 

arr[key]와 arr[2] 비교 후 큰 값의 인덱스 값을 key에 넣고,

...

arr[key]와 arr[n-1] 비교 후 큰 값의 인덱스 값을 key에 넣는다.

 

그 후, 그 arr[key]와 arr[n-1]값을 서로 변경한다.

 

<2단계> - n-2번의 비교

 

arr[0]의 인덱스 값을 key값으로 둔 후,

 

arr[key]와 arr[1] 비교 후 큰 값의 인덱스 값을 key에 넣고,

 

arr[key]와 arr[2] 비교 후 큰 값의 인덱스 값을 key에 넣고,

...

arr[key]와 arr[n-2] 비교 후 큰 값의 인덱스 값을 key에 넣는다.

 

그 후, 그 arr[key]와 arr[n-2]값을 서로 변경한다.

 

.

.

.

 

<n-1단계> - 1번의 비교

 

arr[0]의 인덱스 값을 key값으로 둔 후,

 

arr[0]와 arr[1] 비교 후 큰 값의 인덱스 값을 key에 넣는다.

 

그 후, 그 arr[key]와 arr[1]값을 서로 변경한다.

pseudo code

selectionSort(arr[], n) {
  for last <- n downto 2 {
    arr[1,...,last] 중 가장 큰 수 arr[max]를 찾는다;
    arr[max] <-> arr[last];  // arr[max]와 arr[last] 값을 swap.
  }
}

---

코드 구현

public class Selection {

  private static int[] input = {22, 5, 34, 1, 32, 18, 2, 8}; //예시로 작성한 배열

  public static void main(String[] args) {
    selectionSortMin(input, input.length); //혹은 selectionSortMax(input, input.length);
    for (int a : input) {
      System.out.print(a + " ");
    }
  }

  private static void selectionSortMin(int[] input, int length) { //가장 작은 값부터 선택 정렬하는 방법
    int min;
    int tmp;
    for (int i = 0; i < length-1; i++) { //제일 왼쪽에 있는 값부터 비교
      min = i;
      for (int j = i+1; j < length; j++) { //오른쪽으로 비교해가면서 min 값을 변경 후 왼쪽부터 정렬해감.
        if (input[j] < input[min]) min = j;
      }
      tmp = input[i];
      input[i] = input[min];
      input[min] = tmp;
    }
  }

  private static void selectionSortMax(int[] input, int length) { //가장 큰 값부터 선택 정렬하는 방법
    int max;
    int tmp;
    for (int i = length-1; i > 0; i--) { //제일 오른쪽에 있는 값부터 비교
      max = i;
      for (int j = i-1; j >= 0; j--) { //왼쪽으로 비교해보면서 max 값을 변경 후 오른쪽부터 정렬해감.
        if (input[j] > input[max]) max = j;
      }
      tmp = input[i];
      input[i] = input[max];
      input[max] = tmp;
    }
  }
}

---

시간 복잡도

처음에 n-1번의 비교, 그 다음에 n-2번의 비교,..., 1번의 비교를 진행하므로

O( (n-1)+(n-2)+...+1 ) = O( n(n-1)/2 ) = O(n^2) 이 된다.

 

정렬이 잘 되어 있는 정도에 따라서

최악, 최선, 평균 모두 n(n-1)/2번의 비교연산을 수행하므로 시간복잡도는 모두 O(n^2)이다.