[JAVA] 선택 정렬 (Selection Sort)

선택 정렬 (Selection Sort)

---

선택 정렬 (Selection Sort)

• 제자리 정렬 (in-place sort)
   - 데이터에 필요한 공간을 제외하고 추가적인 공간이 필요없음을 의미
• 비안정 정렬 (unstable sort)
   - 정렬 후에 같은 값들의 순서가 변함
   - 아래는 같은 값을 A, B로 구분하였음
     ex) 3(A), 6, 2, 5, 4, 3(B), 1
            1, 2, 3(B), 3(A), 4, 5, 6
• 정렬할 데이터의 개수가 적을때는 나쁘지 않은 속도를 보임

선택 정렬 방법

위 그림은 아래 방법을 그림으로 표현한 것

1. 주어진 리스트 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다.
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

성능

• 시간복잡도
  최악의 경우 : O(n^2)
  최선의 경우 : O(n^2)
  
  최악과 최선 모두 n^2 의 시간복잡도를 가짐
  데이터가 삽입될 위치를 정하는 반복문과 최소값을 찾는 반복문이 이중으로 구현되어 있으므로

구현

• int형을 기본으로 구현
  [SelectionBasic.java]
  

  package Sort.Selection;
  
  public class SelectionBasic {
      public static void sort(int[] arr, boolean isDescending) {
          // 배열 중 최소값의 위치를 저장하기 위한 변수
          int minIndex = 0;
          int n = arr.length;
  
          // 데이터가 삽입될 위치를 정하는 반복문
          for(int i=0; i<n-1; i++) {
              minIndex = i;
  
              // 최소값을 찾기위한 반복문
              for(int j=i+1; j<n; j++) {
                  // minIndex의 값과 현재 j값을 비교하여 정렬을 해야하는지 확인
                  if (!isSortTwoElements(arr[minIndex], arr[j], isDescending)) {
                      // 정렬이 필요할 경우 minIndex 값을 현재 j값으로 변경
                      minIndex = j;
                  }
              }
  
              // 삽입될 위치(i)와 최소값의 위치(minIndex)를 이용해 교환 진행
              swap(arr, minIndex, i);
          }
      }
  
      /**
       *
       * @param arr 데이터 배열
       * @param idx1 교환할 인덱스
       * @param idx2 교환할 인덱스
       */
      private static void swap(int[] arr, int idx1, int idx2) {
          int tmp = arr[idx1];
          arr[idx1] = arr[idx2];
          arr[idx2] = tmp;
      }
  
      /**
       *
       * @param cmp1 비교할 값
       * @param cmp2 비교할 값
       * @param isDescending 내림차순 및 오름차순 선택
       * @return 내림차순의 경우 cmp1이 작을 경우 false, 그렇지 않으면 true
       *         오름차순의 경우 cmp1이 작을 경우 true, 그렇지 않으면 false
       */
      private static boolean isSortTwoElements(int cmp1, int cmp2, boolean isDescending) {
          // 내림차순일 경우
          if (isDescending) {
              if (cmp1 < cmp2) {
                  return false;
              }
              else {
                  return true;
              }
          }
          // 오름차순일 경우
          else {
              if (cmp1 < cmp2) {
                  return true;
              }
              else {
                  return false;
              }
          }
      }
  }​

  
  
  
• 테스트
  [SelectionBasicMain.java]
  

  package Sort.Selection;
  
  public class SelectionBasicMain {
      private static final int MAX_COUNT = 30;
  
      public static void main(String[] args) {
          int[] arr = new int[MAX_COUNT];
          for(int i=0; i<MAX_COUNT; i++) {
              // 0 ~ MAX_COUNT 범위내의 난수를 생성
              arr[i] = (int)(Math.random() * MAX_COUNT);
          }
  
          System.out.println("정렬 전 데이터");
          for(int i : arr) {
              System.out.print(i + " ");
          }
          System.out.println();
  
          int[] ascSelectionSortTestArray = arr.clone();
          System.out.println("정렬 후 데이터 (오름차순)");
          SelectionBasic.sort(ascSelectionSortTestArray, false);
          for(int i : ascSelectionSortTestArray) {
              System.out.print(i + " ");
          }
          System.out.println();
  
          int[] descSelectionSortTestArray = arr.clone();
          System.out.println("정렬 후 데이터 (내림차순)");
          SelectionBasic.sort(descSelectionSortTestArray, true);
          for(int i : descSelectionSortTestArray) {
              System.out.print(i + " ");
          }
          System.out.println();
      }
  }​

  
  
  
• 결과
  

  

  
  

  ---

• 클래스의 특정 값을 이용한 정렬
  [SelectionAdvanced.java]
  

  package Sort.Selection;
  
  import java.util.Comparator;
  
  /**
   * 클래스 내 특정 값을 이용하여 정렬하는 방법
   */
  public class SelectionAdvanced {
      public static <T> void sort(T[] arr) {
          Comparable<? super T> comp = null;
  
          int minIndex = 0;
          int n = arr.length;
  
          for(int i=0; i<n-1; i++) {
              minIndex = i;
  
              comp = (Comparable<? super T>)arr[minIndex];
              for(int j=i+1; j<n; j++) {
                  // 오름차순
                  if (comp.compareTo(arr[j]) < 0) {
                      minIndex = j;
                  }
              }
  
              swap(arr, minIndex, i);
          }
      }
  
  
      public static <T> void sort(T[] arr, Comparator<? super T> comp) {
          int minIndex = 0;
          int n = arr.length;
  
          for(int i=0; i<n-1; i++) {
              minIndex = i;
  
              for(int j=i+1; j<n; j++) {
                  if (comp.compare(arr[minIndex], arr[j]) > 0) {
                      minIndex = j;
                  }
              }
  
              swap(arr, minIndex, i);
          }
      }
  
      /**
       *
       * @param arr 데이터 배열
       * @param idx1 교환할 인덱스
       * @param idx2 교환할 인덱스
       */
      private static <T> void swap(T[] arr, int idx1, int idx2) {
          T tmp = arr[idx1];
          arr[idx1] = arr[idx2];
          arr[idx2] = tmp;
      }
  }​

  
  
  
• 테스트
  

  package Sort.Selection;
  
  import java.util.Comparator;
  
  public class SelectionAdvancedMain {
      private static final int MAX_COUNT = 30;
  
      public static void main(String[] args) {
          Integer[] arr = new Integer[MAX_COUNT];
          for(int i=0; i<MAX_COUNT; i++) {
              // 0 ~ MAX_COUNT 범위내의 난수를 생성
              arr[i] = (int)(Math.random() * MAX_COUNT);
          }
  
          System.out.println("정렬 전 데이터");
          for(int i : arr) {
              System.out.print(i + " ");
          }
          System.out.println();
          System.out.println();
  
          System.out.println("정렬 후 데이터 (오름차순)");
          SelectionAdvanced.sort(arr);
          for(int i : arr) {
              System.out.print(i + " ");
          }
          System.out.println();
          System.out.println();
          System.out.println();
  
          class Student {
              String name;
              int age;
  
              public Student(String name, int age) {
                  this.name = name;
                  this.age = age;
              }
  
              @Override
              public String toString() {
                  return "name='" + name + '\'' +
                          ", age=" + age;
              }
          }
  
          Student[] students = new Student[5];
          students[0] = new Student("아이언맨", 11);
          students[1] = new Student("헐크", 4);
          students[2] = new Student("토르", 15);
          students[3] = new Student("블랙위도우", 13);
          students[4] = new Student("캡틴", 4);
  
          System.out.println("클래스 정렬 전 데이터");
          for (int i=0; i<students.length; i ++) {
              System.out.println(students[i]);
          }
          System.out.println();
  
          System.out.println("클래스 정렬 후 데이터 (나이 내림차순)");
          SelectionAdvanced.sort(students, new Comparator<Student>() {
              @Override
              public int compare(Student o1, Student o2) {
                  if (o1.age < o2.age) {
                      return 1;
                  }
                  else if (o1.age == o2.age) {
                      return 0;
                  }
                  else {
                      return -1;
                  }
              }
          });
  
          for (int i=0; i<students.length; i ++) {
              System.out.println(students[i]);
          }
      }
  }​

  
  
  
• 결과