230617 Today I Learned

오늘 선택정렬에 대해 정리하고 직접 구현해보고자 한다.

선택 정렬(Selection Sort)

가장 작은 값을 찾아서 앞쪽으로 이동시키는 정렬 알고리즘
먼저 위치를 선택해서 해당 위치에 맞는 값을 찾는 방식

이미지 출처:jguuun

• (기본적으로 정렬 알고리즘은 오름차순을 가정한다)

• 과정
  주어진 배열에서 가장 작은 값을 찾는다.
  그 값을 맨 앞의 원소와 교환한다.
  맨 앞의 이미 교환한 값들은 정렬된 값으로 간주하고 넘어간다.
  전체가 다 정렬될 때까지 반복한다.

• 시간복잡도 : 첫 회차에서 n-1번, 다음 회차에서 n-2번, ... 마지막 회차에서 1번 -> n(n-1)/2로 결국 시간복잡도는 최선, 평균, 최악 모두 O(n^2)로 동일하다.

• 공간복잡도 : 주어진 배열 안에서 swap을 통해 정렬되므로 O(1)이다. (버블정렬과 같다.)

• 장점 : 구현이 간단하고 직관적이다.
  추가적인 메모리 공간이 필요없는 제자리 정렬이다.
  시간복잡도와 비교 횟수는 버블정렬과 동일하지만, 선택정렬은 한 회차에 단 한번만 swap이 이루어지므로 버블정렬보다 swap의 횟수가 적다.

• 단점 : 시간복잡도가 모든 경우에서 O(n^2)으로 비효율적이다.
  불안정(중복된 값을 입력된 순서와 상관없이 무작위로 섞는)정렬이다.

Java로 선택 정렬 구현

밖의 for문이 회차. i값으로 위치를 선택한다. 안쪽의 for문이 비교연산. i 다음값부터 배열의 끝값까지 가면서 최소값을 찾아 비교한다. 최소값이 i값이 아니면 위치를 swap한다.

  private static void selectionSort(int[] array){
    for (int i = 0; i < array.length-1; i++) {
      int minIndex = i;
      for (int j = i+1; j < array.length; j++) {
        if (array[j] < array[minIndex]){
          minIndex = j;
        }
        }
      if (minIndex != i){
        int tmp = array[i];
        array[i] = array[minIndex];
        array[minIndex] = tmp;
      }
    }
  }

이중 선택 정렬

선택정렬의 변형으로, 각 회차에서 최소값만 찾는게 아니라 최대값도 같이 찾아 맨 뒤로 옮기는 정렬알고리즘이다.

  private static void dualSelectionSort(int[] array){
    for (int i = 0, j = array.length-1; i<j; i++,j--){
      int minIndex = i;
      int maxIndex = j;
//      탐색하면서 min값과 max값 동시에 찾는다.
      for (int k = i+1; k<=j; k++){
        if (array[k]<array[minIndex]){
          minIndex = k;
        } else if (array[k]>array[maxIndex]){
          maxIndex = k;
        }
      }

      if (minIndex != i){
        int tmp = array[i];
        array[i] = array[minIndex];
        array[minIndex] = tmp;
//        maxIndex가 i였다면, swap되었기 때문에 위치 재조정
        if (maxIndex == i) maxIndex = minIndex;
      }

      if (maxIndex != j){
        int tmp = array[j];
        array[j] = array[maxIndex];
        array[maxIndex] = tmp;
//        minIndex가 j였다면, swap되었기 때문에 위치 재조정
        if (minIndex == j) minIndex = maxIndex;
      }
    }
  }

• 한 회차에 두 원소가 정렬되므로 원래의 선택정렬보다 빠르고 회차가 적다.

• 하지만 시간복잡도는 여전히 O(n^2)으로 동일하다.

최종 출력

한 회차에서 min과 max를 동시에 찾기때문에 회차가 줄었다.

  public static void main(String[] args) {
    int[] array = {1,2,7,5,4,3,9,6,8,10};
    int[] array2 = Arrays.copyOf(array, array.length);
    System.out.print("정렬 전 배열 : ");
    System.out.println(Arrays.toString(array));
    System.out.println("-----------------------------------------");
    selectionSort(array);
    System.out.print("선택정렬 후 배열 : ");
    System.out.println(Arrays.toString(array));
    System.out.println("-----------------------------------------");
    dualSelectionSort(array2);
    System.out.print("이중 선택정렬 후 배열 : ");
    System.out.println(Arrays.toString(array2));
  }