개발자로 살아남기

기수 정렬 (Radix Sort)

기수 정렬 (Radix Sort)

• 비교 연산이 없는 정렬 알고리즘
• 적용할 수 있는 범위가 제한적임
   - 정수, 알파벳, 특수문자 등의 아스키로 표현할 수 있는 것들
   - 소수는 불가능
• 기수 (Radix)를 이용한 정렬
   - 2진수의 경우 : 0, 1   /   10진수의 경우 : 0 ~ 9   /   알파벳 소문자의 경우 : a ~ z (0 ~ 25)
• 기수만큼의 추가 저장 공간이 필요함
   - 저장 공간을 버킷 (Bucket) 이라고 부름
• Queue를 이용한 정렬 알고리즘
• LSD (Least Significant Digit) 정렬 방법과 MSD (Most Significant Digit) 정렬 방법이 있음
   - LSD : 덜 중요한 첫번째 자리수부터 정렬 (즉, 가장 작은 자리수)
      ex) 1234 일 경우 4부터 정렬
   - MSD : 가장 중요한 마지막 자리수부터 정렬 (즉, 가장 큰 자리수)
      ex) 1234 일 경우 1부터 정렬
      MSD의 경우 구현의 난이도가 높으며 중간에 데이터를 확인해야 하는 단점이 있음
• 안정 정렬 (Stable Sort)
   - 동일한 데이터의 순서가 정렬 후에도 변함이 없음
  ex) 5(A), 5(B), 3, 2, 1 => 1, 2, 3, 5(A), 5(B)
• 비 제자리 정렬 (out of place)
   - 정렬 시 추가적인 저장공간(버킷)이 필요하므로 제자리 정렬이 아님

기수정렬 방법

1. 기수만큼 큐(Queue)를 이용해 저장공간 (Bucket)을 생성한다.
2. 데이터의 1의 자리를 기준으로 버킷에 넣는다.
3. 버킷에 저장된 데이터를 순서대로 꺼내 기존 데이터에 덮어쓴다.
4. 데이터의 10의 자리를 기준으로 버킷에 넣는다.
5. 마지막 자리수까지 정렬의 기준이 될 자리수를 늘리며 정렬한다.
   
   

   

성능

• 비교연산이 아닌 데이터 삽입과 추출의 빈도수로 성능을 평가함
• 길이가 가장 긴 자리수를 k, 데이터 개수를 n 이라고 했을 때, k 자리수 까지의 반복과 데이터 n개를 반복해서 정렬하므로 k * n 이 된다.
• 최악의 경우 : O(kn)
• 최선의 경우 : O(kn)

구현

• LSD로 구현
  [RadixBasic.java]
  

  package Sort.Radix;
  
  import java.util.LinkedList;
  import java.util.Queue;
  
  public class RadixBasic {
      // 10진수 기준으로 구현
      private static int BUCKET_NUM = 10;
  
      public static void sort(int[] arr) {
          // 10진수 버킷 생성
          Queue<Integer>[] bucket = new LinkedList[BUCKET_NUM];
          for(int i=0; i<BUCKET_NUM; i++) {
              bucket[i] = new LinkedList<>();
          }
  
          int maxLen = maxDigitCount(arr);
          // 각 자리수의 숫자 저장
          int digitNumber = 0;
          // 배열에 다시 저장할 때 필요한 변수
          int arrIndex = 0;
  
          // 자리수만큼 반복
          for(int i=0; i<maxLen; i++) {
              // 데이터의 개수만큼 반복
              for(int j=0; j<arr.length; j++) {
                  digitNumber = getDigit(arr[j], i);
  
                  bucket[digitNumber].add(arr[j]);
              }
  
              // 버킷에 들어간 데이터를 순서대로 꺼내 배열에 덮어씌움
              for(int j=0; j<BUCKET_NUM; j++) {
                  while (!bucket[j].isEmpty()) {
                      arr[arrIndex++] = bucket[j].remove();
                  }
              }
              arrIndex = 0;
          }
      }
  
      // 숫자의 자리수 반환
      // getDigit(123, 0) => 3
      // getDigit(123, 1) => 2
      // getDigit(123, 2) => 1
      private static int getDigit(int num, int index) {
          return (int)Math.floor(Math.abs(num) / Math.pow(10, index)) % 10;
      }
  
      // 숫자의 자리수 구하기
      // digitCount(10) => 2
      // digitCount(1) => 1
      // digitCount(1000) => 4
      private static int digitCount(int num) {
          if (num == 0) {
              return 1;
          }
  
          // log10을 하면 자리수가 나옴
          // log10(10) => 1
          // log10(100) -> log10(10^2) => 2
          return (int)Math.floor(Math.log10(Math.abs(num))) + 1;
      }
  
      // 데이터들 중 가장 큰 자리수 반환
      private static int maxDigitCount(int[] arr) {
          int max = 0;
  
          for(int i=0; i<arr.length; i++) {
              max = Math.max(max, digitCount(arr[i]));
          }
  
          return max;
      }
  }​

• 테스트
  [RadixBasicMain.java]
  

  package Sort.Radix;
  
  public class RadixBasicMain {
      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();
  
          System.out.println("정렬 후 데이터 (오름차순)");
          int[] radixSortTestArray = arr.clone();
          RadixBasic.sort(radixSortTestArray);
          for(int i : radixSortTestArray) {
              System.out.print(i + " ");
          }
          System.out.println();
  
      }
  }​

• 결과
  

  

참고

윤성우의 열혈 자료구조

https://ko.wikipedia.org/wiki/%EA%B8%B0%EC%88%98_%EC%A0%95%EB%A0%AC

https://www.geeksforgeeks.org/radix-sort/

퀵정렬 (Quick Sort)

퀵정렬 (Quick Sort)

• 분할정복 (divide and conquer) 알고리즘 중 하나
• 피벗(pivot)이라는 것을 이용해 정렬
  피벗 : 데이터 리스트에서 하나를 고르는 것
• 불안정 정렬 (unstable sort)
   - 같은 데이터끼리의 순서가 보장되지 않음
  ex) 5(A), 5(B), 3, 2, 1 => 1, 2, 3, 5(B), 5(A)
• nlog2(n) 알고리즘들 중 평균적으로 가장 빠름
• 제자리 정렬 (in-place sort)
   - 데이터 크기만큼의 저장공간을 제외하고 추가적인 공간이 필요하지 않음

퀵정렬 방법

1. 데이터들 중 하나를 골라 피벗으로 설정
2. 데이터 리스트의 앞과 뒤에서 탐색하며 피벗보다 작은 값들은 앞에 오고 피벗보다 큰 값들은 뒤로 가도록 분할
3. 분할된 리스트에 1, 2 과정을 반복
4. 1, 2 과정을 반복할 때마다 최소 하나 이상 정렬이 됨
    - 피벗값 기준으로 왼쪽은 작은값, 오른쪽은 큰 값이기 때문

성능

• 시간복잡도
  최악의 경우 : O(n^2)
  최선의 경우 : O(nlog2(n))
  평균의 경우 : O(nlog2(n))
  
  
• 피벗 데이터가 자신의 위치를 찾아가기 위해서는 데이터 개수 (n) 만큼의 비교연산이 필요
  
  
• 피벗값이 항상 리스트의 가운데에 있다고 가정할 때, 데이터들은 절반씩 나누어짐
  

  

  초기상태	1 덩어리	분할 0번
  17을 둘로 나누면	2 덩어리	분할 1번
  8을 둘로 나누면	4 덩어리	분할 2번

  위와 같은 과정을 거치게 되면 최종적으로 분할횟수 = log2(데이터 개수) 가 된다.
  
  
• 리스트가 이미 정렬되어 있고 피벗값이 항상 데이터들 중 가장 작은 값일 때, 데이터들은 n, n-1, n-2, ... 로 나누어짐
   - 피벗값이 리스트 내 데이터들 중 항상 작으므로 피벗과 이미 정렬된 데이터를 제외하고 모두 비교해야 하므로
  분할횟수 = 데이터 개수가 된다.
  
  
• 그러나, 퀵정렬의 경우 최악의 경우를 빅-오로 사용하지 않음
   - 중간에 가까운 피벗을 선택함으로써 최선의 경우에 가까운 성능을 평균적으로 보이기 때문

구현

• 기본 구현
  [QuickBasic.java]
  

  package Sort.Quick;
  
  public class QuickBasic {
      public static void sort(int[] arr) {
          quickSort(arr, 0, arr.length - 1);
      }
  
      private static void quickSort(int[] arr, int start, int end) {
          // end가 start보다 크다는 것은 더 나눌 데이터가 남아있다는 것이 됨
          if (start <= end) {
              // 피벗 대상이 될 인덱스 반환
              int pivotIndex = partition(arr, start, end);
  
              // 피벗 기준으로 왼쪽 데이터 분할
              quickSort(arr, start, pivotIndex - 1);
              // 피벗 기준으로 오른쪽 데이터 분할
              quickSort(arr, pivotIndex + 1, end);
          }
      }
  
      private static int partition(int[] arr, int start, int end) {
          // 배열의 처음, 중간, 끝의 데이터를 정렬해 크기가 중간인 데이터를 배열의 첫번째로 옮기는 과정
          medianOfThree(arr, start, end);
  
          // 피벗값을 제외하고 탐색해야 하므로 + 1
          int leftIndex = start + 1;
          int rightIndex = end;
          int pivotData = arr[start];
  
          // 탐색 인덱스들이 서로 지나치지 않았다면 반복
          // 지나쳤다면 해당 피벗을 이용한 탐색이 끝났으므로 반복문 종료
          while(leftIndex <= rightIndex) {
              // 피벗 데이터보다 큰 값이 나올때까지 탐색
              // leftIndex를 비교하는 부분이 앞으로 와야 함. 피벗값과 데이터가 같을 때 인덱스를 벗어날 수 있음. (ex. 4 4 1 2 2)
              while(leftIndex <= end && arr[leftIndex] <= pivotData) {
                  leftIndex++;
              }
  
              // 피벗 데이터보다 작은 값이 나올때까지 탐색
              // 피벗 데이터는 탐색에서 제외해야 함
              // rightIndex를 비교하는 부분이 앞으로 와야 함. 피벗값과 데이터가 같을 때 인덱스를 벗어날 수 있음.
              while(rightIndex >= start + 1 && arr[rightIndex] >= pivotData) {
                  rightIndex--;
              }
  
              // 서로의 인덱스가 지나치지 않았을 때 교환
              if (leftIndex <= rightIndex) {
                  swap(arr, leftIndex, rightIndex);
              }
          }
  
          // 피벗값과 rightIndex가 가리키는 값과 교환
          // rightIndex는 피벗값보다 작은 값을 탐색하는데, 서로 인덱스가 지나쳐 탐색이 끝나게 되면
          // 피벗보다 큰 값과 작은값이 결정되는 경계를 rightIndex가 가리키고 있기 때문에 교환해야 함
          swap(arr, start, rightIndex);
          return rightIndex;
      }
  
      // 처음, 중간, 끝의 데이터를 비교해 중간의 값을 피벗으로 정하고 연산을 쉽게 하기 위해
      // 해당 피벗값을 가장 왼쪽 값과 교환
      private static void medianOfThree(int[] arr, int start, int end) {
          int[] index = {start, (start + end) / 2, end};
  
          if (arr[index[0]] > arr[index[1]]) {
              swap(index, 0, 1);
          }
  
          if (arr[index[1]] > arr[index[2]]) {
              swap(index, 1, 2);
          }
  
          if (arr[index[0]] > arr[index[1]]) {
              swap(index, 0, 1);
          }
  
          swap(arr, start, index[1]);
      }
  
      private static void swap(int[] arr, int idx1, int idx2) {
          int tmp = arr[idx1];
          arr[idx1] = arr[idx2];
          arr[idx2] = tmp;
      }
  }​

• 테스트
  [QuickBasicMain.java]
  

  package Sort.Quick;
  
  public class QuickBasicMain {
      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);
          }
  
  //        int[] arr = {4, 4, 1, 2, 2};
  
          System.out.println("정렬 전 데이터");
          for(int i : arr) {
              System.out.print(i + " ");
          }
          System.out.println();
  
          System.out.println("정렬 후 데이터 (오름차순)");
          int[] quickSortTestArray = arr.clone();
          QuickBasic.sort(quickSortTestArray);
          for(int i : quickSortTestArray) {
              System.out.print(i + " ");
          }
          System.out.println();
      }
  }​

• 결과
  

  

참고
윤성우의 열혈 자료구조

위키

힙 정렬 (Heap Sort)

힙 정렬 (Heap Sort)

• 최대힙 트리나 최소힙 트리를 구성해 정렬하는 방법
• 내림차순 정렬은 최대힙으로 구성
• 오름차순 정렬은 최소힙으로 구성
• 힙 관련 내용 참고 (https://banjjak1.tistory.com/45)

힙 정렬 방법

• 내림차순일 경우 데이터를 최대힙으로 구성하고 오름차순일 경우 최소힙으로 구성
• 최대힙의 경우 루트노드는 해당 트리에서 항상 최대값을 가지고 있으므로 힙 구성 후 삭제를 반복하면 다음 최대값이 루트노드가 되어 결국 내림차순 정렬이 됨

성능

• 시간복잡도
  최악의 경우 : n log2(n)
  최선의 경우 : n log2(n)
   : 데이터 저장 및 삭제의 시간복잡도 log2(n)
   : 정렬할 데이터가 n개인 경우 n개의 데이터를 저장 및 삭제해야 하므로 n
  
  
• 데이터 저장 및 삭제의 시간복잡도
   - 트리의 높이가 하나씩 증가할 때마다 데이터의 수는 증가 전 높이의 데이터 수보다 최대 2배 증가한다.
  

  

  그러나 데이터를 추가 및 삭제할 때는 부모노드와 같을 비교하기 때문에 데이터의 수는 2배 증가하지만 비교횟수는 1회 증가되는 것으로 이를 일반화하면 대략적으로 비교횟수 = log2(데이터 개수)이 된다.

구현

• 기본 구현
  [HeapBasic.java]
  

  package Sort.Heap;
  
  import java.util.Collections;
  import java.util.PriorityQueue;
  
  public class HeapBasic {
      public static void sort(int[] arr, boolean isDescending) {
          PriorityQueue<Integer> pq = null;
          pq = init(isDescending);
          add(pq, arr);
  
          for(int i=0; i<arr.length; i++) {
              arr[i] = pq.remove();
          }
      }
  
      private static PriorityQueue init(boolean isDescending) {
          PriorityQueue pq = null;
          // 내림차순일 경우 최대힙으로 구성
          if (isDescending) {
              pq = new PriorityQueue<>(Collections.reverseOrder());
          }
          // 오름차순일 경우 최소힙으로 구성
          else {
              pq = new PriorityQueue<>();
          }
  
          return pq;
      }
  
      private static void add(PriorityQueue pq, int[] arr) {
          for(int i=0; i<arr.length; i++) {
              pq.add(arr[i]);
          }
      }
  
      private static int delete(PriorityQueue pq) {
          return (int)pq.remove();
      }
  }​

  
  
  
• 테스트
  [HeapBasicMain.java]
  

  package Sort.Heap;
  
  public class HeapBasicMain {
      private static final int MAX_COUNT = 10;
  
      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();
  
          System.out.println("정렬 후 데이터 (오름차순)");
          int[] ascHeapSortTestArray = arr.clone();
          HeapBasic.sort(ascHeapSortTestArray, false);
          for(int i : ascHeapSortTestArray) {
              System.out.print(i + " ");
          }
          System.out.println();
  
          System.out.println("정렬 후 데이터 (내림차순)");
          int[] descHeapSortTestArray = arr.clone();
          HeapBasic.sort(descHeapSortTestArray, true);
          for(int i : descHeapSortTestArray) {
              System.out.print(i + " ");
          }
          System.out.println();
      }
  }​

• 결과
  

  

합병(병합) 정렬 (Merge Sort)

합병(병합) 정렬 (Merge Sort)

• 안정 정렬 (stable sort)
   - 정렬 후에도 같은 값들끼리의 순서가 보장됨을 의미함
  ex) 5, 4, 3(A), 2, 3(B), 1
        1, 2, 3(A), 3(B), 4, 5
• 분할정복 (divide and conquer) 알고리즘 중 하나
• 정렬 시 데이터 크기만큼의 추가 공간이 필요하므로 제자리 정렬 (in-place sort)가 될 수 없음

합병 정렬 방법

1. 분할 (divide) : 데이터 리스트에서 데이터가 하나씩 정렬될 때까지 리스트를 절반씩 나눈다.
2. 정복 (conquer) : 나눈 데이터들끼리 재귀적으로 정렬을 진행한다.
3. 결합 (combine) : 정렬된 데이터들을 하나로 합친다.

성능

• 시간복잡도
  최악의 경우 : O(n log2(n))
  최선의 경우 : O(n log2(n))
  

  

• 분할
  데이터의 개수가 8개라고 했을 때 3번의 분할과정을 통해 8 -> 4 -> 2 -> 1 (2^3 -> 2^2 -> 2^1 -> 2^0) 순으로 줄어들게 된다. 따라서 분할과정은 3 = log2(8)이 되므로 결국 분할횟수 = log2(데이터 개수) 가 된다.
• 정복 및 결합
  데이터 8개를 2개씩 결합하면 총 4개의 덩어리가 나오게 되며 데이터마다 비교하게 되면 최대 2번 비교하게 된다. 따라서 데이터 2개와 4개의 덩어리를 곱하면 최대 8번의 비교 횟수가 나온다. 다시 데이터 4개와 2개의 덩어리를 곱하면 8번이 되므로 각 병합의 단계마다 최대 데이터 개수만큼 비교하게 되어 병합 횟수 = 데이터 개수가 된다.

구현

• 기본 구현
  [MergeBasic.java]
  

  package Sort.Merge;
  
  public class MergeBasic {
      public static void sort(int[] arr, int left, int right) {
          mergeSort(arr, left, right);
      }
  
      private static void mergeSort(int[] arr, int left, int right) {
          int mid = 0;
          if (left < right) {
              mid = (left + right) / 2; // 데이터 리스트의 중앙 인덱스를 구함
              mergeSort(arr, left, mid); // 중앙을 기준으로 왼쪽 데이터들을 분할한다.
              mergeSort(arr, mid + 1, right); // 중앙을 기준으로 오른쪽 데이터들을 분할한다.
              merge(arr, left, mid, right); // 정복 및 결합 과정을 진행한다.
          }
      }
  
      private static void merge(int[] arr, int left, int mid, int right) {
          // 분할된 왼쪽 리스트들의 시작점 변수
          int leftIndex = left;
          // 분할된 오른쪽 리스트들의 시작점 변수
          int rightIndex = mid + 1;
          // 정렬된 데이터가 저장될 인덱스
          int sortedIndex = left;
          // 정렬된 데이터를 임시로 저장할 곳
          int[] tmpSortedArray = new int[right + 1];
  
          // 분할된 왼쪽 리스트의 인덱스가 mid까지 온 경우 왼쪽 정렬 완료
          // 분할된 오른쪽 리스트의 인덱스가 right까지 온 경우 오른쪽 정렬 완료
          // 즉, 왼쪽 또는 오른쪽 둘 중 하나라도 정렬이 완료된 경우 반복문을 빠져나감
          while(leftIndex <= mid && rightIndex <= right) {
              // 오름차순 조건문
              if (arr[leftIndex] <= arr[rightIndex]) {
                  tmpSortedArray[sortedIndex++] = arr[leftIndex++];
              }
              else {
                  tmpSortedArray[sortedIndex++] = arr[rightIndex++];
              }
          }
  
          // 왼쪽이 다 정렬된 경우 오른쪽 데이터들의 남은 부분들을 다 옮겨야 함
          if (leftIndex > mid) {
              for(int i=rightIndex; i<=right; i++) {
                  tmpSortedArray[sortedIndex++] = arr[i];
              }
          }
          else {
              for(int i=leftIndex; i<=mid; i++) {
                  tmpSortedArray[sortedIndex++] = arr[i];
              }
          }
  
          // 원래 배열에 정렬된 데이터로 덮어씌움
          for(int i=left; i<=right; i++) {
              arr[i] = tmpSortedArray[i];
          }
      }
  }

• 테스트
  [MergeBasicMain.java]
  

  package Sort.Merge;
  
  public class MergeBasicMain {
      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();
  
          System.out.println("정렬 후 데이터 (오름차순)");
          int[] ascSortedArrayTest = arr.clone();
          MergeBasic.sort(ascSortedArrayTest, 0, ascSortedArrayTest.length - 1);
          for(int i : ascSortedArrayTest) {
              System.out.print(i + " ");
          }
          System.out.println();
      }
  }​

• 결과
  

  

참고

https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

https://namu.wiki/w/%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

윤성우의 열혈 자료구조

삽입 정렬 (Insertion Sort)

삽입 정렬 (Insertion Sort)

• 구현이 간단함
• 안정 정렬 (stable sort)
   - 정렬 후에도 같은 값들 끼리의 순서가 보장됨을 의미함
  ex) 5, 3(A), 2, 4, 3(B), 1 => 1, 2, 3(A), 3(B), 4, 5
• 제자리 정렬 (in-place sort)
   - 데이터에 필요한 공간을 제외하고 추가적인 공간이 필요없음을 의미
• 선택 정렬, 버블 정렬보다 비교적 빠르지만 마찬가지로 배열이 클수록 효율이 떨어짐
• 선택 정렬과 비슷하지만 선택 정렬은 배열의 모든 값을 탐색해 최소값을 구한 후 정렬하는 방식이지만
  삽입 정렬은 데이터의 앞쪽을 탐색하며 자신의 위치를 찾아 정렬함

삽입 정렬 방법

• 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성시킴
  

  

• 자신의 위치를 찾는 방법은 arr[i - 1] <= X < arr[i] 가 만족하는 위치가 있다면 해당 위치에 X값을 삽입함
• 삽입될 위치의 뒤 인덱스들을 하나씩 뒤로 미뤄 X가 들어갈 공간을 만들어줌

성능

• 시간복잡도
  최악의 경우 : O(n^2)
   - 배열의 데이터가 모두 역순일 때 (5, 4, 3, 2, 1)
   - 5, 4, 3, 2, 1의 예시에서보면 4와 5를 비교, 3과 4, 5비교, 2와 3, 4, 5 순으로 비교하게 되는데 비교횟수를 수식으로 나타내면 1 + 2 + 3 + 4 + ... + (n-1) 이 되므로 1/2n(n-1) 이 되어 n^2이 된다.
  
  최선의 경우 : O(n)
   - 배열의 데이터가 모두 정렬되어 있을 때 (1, 2, 3, 4, 5)
   - 삽입 정렬은 앞쪽부터 정렬되기 때문에 정렬하려는 값 X가 바로 앞 데이터보다 클 경우 모든 앞쪽 데이터들을 확인할 필요가 없으므로 다음 데이터로 넘어가서 다시 비교하게 된다. 따라서, 이미 정렬이 된 상태인 경우 n번만 반복한 후 종료된다.

구현 

• 기본 구현
  [InsertionBasic.java]
  

  package Sort.Insertion;
  
  public class InsertionBasic {
      public static void sort(int[] arr, boolean isDescending) {
          // 현재값을 저장하기 위한 변수
          int tmp = 0;
          // 비교 대상의 인덱스 변수
          int compareIndex = 0;
  
          for(int i=1; i<arr.length; i++) {
              // 현재값 저장
              tmp = arr[i];
              // 현재값 바로 앞 인덱스값 저장
              compareIndex = i - 1;
  
              // 앞쪽 데이터들이 현재값보다 작을때까지 반복
              // 앞쪽 데이터들을 뒤로 당기는 과정
              while(compareIndex >= 0 && !isSortTwoElements(arr[compareIndex], tmp, isDescending)) {
                  arr[compareIndex + 1] = arr[compareIndex];
                  compareIndex--;
              }
  
              // 빈 공간에 데이터 저장
              arr[compareIndex + 1] = 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;
              }
          }
      }
  }​

  
  
  
• 테스트
  

  package Sort.Insertion;
  
  public class InsertionBasicMain {
      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[] ascInsertionTestArray = arr.clone();
          System.out.println("정렬 후 데이터 (오름차순)");
          InsertionBasic.sort(ascInsertionTestArray, false);
          for(int i : ascInsertionTestArray) {
              System.out.print(i + " ");
          }
          System.out.println();
  
          int[] descInsertionTestArray = arr.clone();
          System.out.println("정렬 후 데이터 (내림차순)");
          InsertionBasic.sort(descInsertionTestArray, true);
          for(int i : descInsertionTestArray) {
              System.out.print(i + " ");
          }
          System.out.println();
      }
  }​

• 결과
  

  

  
  

  ---

  
  
  
• 클래스 정렬을 위한 구현
  [InsertionAdvanced.java]
  

  package Sort.Insertion;
  
  import java.util.Comparator;
  
  public class InsertionAdvanced {
      public static <T> void sort(T[] arr) {
          T tmp = null;
          int compareIndex = 0;
  
          for(int i=1; i<arr.length; i++) {
              tmp = arr[i];
              compareIndex = i - 1;
  
              while(compareIndex >= 0 && ((Comparable<? super T>)arr[compareIndex]).compareTo(tmp) > 0) {
                  arr[compareIndex + 1] = arr[compareIndex];
                  compareIndex--;
              }
  
              arr[compareIndex + 1] = tmp;
          }
      }
  
      public static <T> void sort(T[] arr, Comparator<? super T> comp) {
          T tmp = null;
          int compareIndex = 0;
  
          for(int i=1; i<arr.length; i++) {
              tmp = arr[i];
              compareIndex = i - 1;
  
              while (compareIndex >= 0 && comp.compare(arr[compareIndex], tmp) > 0) {
                  arr[compareIndex + 1] = arr[compareIndex];
                  compareIndex--;
              }
  
              arr[compareIndex + 1] = tmp;
          }
      }
  }​

• 테스트
  

  package Sort.Insertion;
  
  import Sort.Selection.SelectionAdvanced;
  
  import java.util.Comparator;
  
  public class InsertionAdvancedMain {
      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();
  
          Integer[] ascInsertionTestArray = arr.clone();
          System.out.println("정렬 후 데이터 (오름차순)");
          InsertionAdvanced.sort(ascInsertionTestArray);
          for(int i : ascInsertionTestArray) {
              System.out.print(i + " ");
          }
          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("클래스 정렬 후 데이터 (나이 내림차순)");
          InsertionAdvanced.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]);
          }
      }
  }​

• 결과
  

  

선택 정렬 (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]);
          }
      }
  }​

  
  
  
• 결과
  

  

버블 정렬 (Bubble Sort)

버블 정렬 (Bubble Sort)

• 가장 단순한 정렬 알고리즘
• 인접한 요소와 정렬 기준(오름차순, 내림차순)대로 교환
• 안정 정렬 (stable sort)
   : 정렬 후에도 같은 값들 끼리의 순서가 보장됨을 의미
• 제자리 정렬 (in-place sort)
   : 데이터에 필요한 공간을 제외하고 추가적인 공간이 필요없음을 의미
• 정렬한 데이터의 개수가 적을때는 나쁘지 않은 속도를 보임

버블 정렬 방법 (오름차순 기준)

• 첫 번째 사이클이 끝나면 맨 마지막 값이 정렬되고, 두 번째 사이클이 끝나면 뒤에서 두 번째의 값이 정렬된다. 이같은 과정을 계속 반복하면 최종적으로 정렬이 된다. 

버블 정렬의 성능

• 시간복잡도
  최악의 경우 : O(n^2)
  최선의 경우 : O(n)
  
  
• 최악의 경우 : 모든 데이터가 역순인 경우 (5, 4, 3, 2, 1)
  5를 정렬하기 위해서는 n-1번 비교 및 교환해야하고, 4를 정렬하기 위해서는 n-2번 비교 및 교환해야 한다.
  즉, 5를 정렬할 때 4번, 4를 정렬할 때 3번, 3을 정렬할 때 2번, 1과 2를 정렬할 때 1번의 비교 및 교환을 거치게 되므로 비교 횟수는 4 + 3 + 2 + 1회가 된다. 
  따라서, 데이터가 n개일 때 총 비교횟수는 (n-1) + (n-2) + (n-3) + ... + 2 + 1 이 되므로 등차수열의 합에 따라 1/2n(n-1)이 되며 빅-오는 최고차항을 가지기 때문에 O(n^2)이 된다.
  
  
• 최선의 경우 : 모든 데이터가 이미 정렬된 경우 (1, 2, 3, 4, 5)
  한 번도 교환이 이루어지지 않았다면 이미 정렬된 상태이므로 n번 비교 후 반환되어 O(n) 이 된다.
  
  

기본 구현

• 기본 int형 배열 정렬 구현
  [BubbleBasic.java]
  

  package Sort.Bubble;
  
  /**
   * 단순히 int형 배열만 오름차순 또는 내림차순으로 정렬하는 경우
   */
  public class BubbleBasic {
      private boolean isDescending = false;
  
      /**
       * @param arr int형 배열
       * @param isDescending 내림차순 및 오름차순 선택
       */
      public static void sort(int[] arr, boolean isDescending) {
          // 이미 정렬이 되어있는지 확인하기 위한 변수
          boolean isAlreadySorted = true;
          int n = arr.length;
  
          // 정렬할 값을 선택하는 반복문
          for(int i=0; i<n-1; i++) {
              // 정렬할 값과 나머지 값들을 비교하기 위한 반복문
              // 이미 정렬이 완료된 데이터는 비교대상에서 제외해야 하므로 n-i-1
              for(int j=0; j<n-i-1; j++) {
                  // 정렬되지 않았다면
                  if (!isSortTwoElements(arr[j], arr[j + 1], isDescending)) {
                      // 데이터를 교환한다.
                      swap(arr, j, j + 1);
                      // 스왑을 했다면 초기 배열 상태가 정렬되지 않았다는 것이므로 false로 변경
                      isAlreadySorted = false;
                  }
              }
  
              // 한 번도 교환이 발생하지 않았다면 이미 정렬된 데이터이므로 반복문을 빠져나온다.
              if (isAlreadySorted) {
                  break;
              }
          }
      }
  
      /**
       *
       * @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;
              }
          }
      }
  }​

• BubbleBasic.java 테스트 및 실행시간 측정
  

  package Sort.Bubble;
  
  public class BubbleBasicMain {
      private static final int MAX_COUNT = 10;
  
      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);
          }
  
          // 배열은 참조형 이므로 arr을 넘길 경우 arr값이 변경되기 때문에 복사본을 생성한 후 테스트
          int[] ascArrTest = arr.clone();
          System.out.println("정렬 전 데이터");
          for(int i : ascArrTest) {
              System.out.println(i);
          }
          System.out.println();
  
          BubbleBasic.sort(ascArrTest, false);
          System.out.println("오름차순 정렬 후 데이터");
          for(int i : ascArrTest) {
              System.out.println(i);
          }
          System.out.println();
  
          int[] descArrTest = arr.clone();
          BubbleBasic.sort(descArrTest, true);
          System.out.println("내림차순 정렬 후 데이터");
          for(int i : descArrTest) {
              System.out.println(i);
          }
  
          // 시간복잡도 측정 (오름차순 기준)
          long start = 0;
          long end = 0;
  
          int[] bestTimeComplexityArray = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
          start = System.nanoTime();
          BubbleBasic.sort(bestTimeComplexityArray, false);
          end = System.nanoTime();
          System.out.println("최선의 경우 오름차순 시간 : " + (end - start) + "ns");
  
          int[] worstTimeComplexityArray = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
          start = System.nanoTime();
          BubbleBasic.sort(worstTimeComplexityArray, false);
          end = System.nanoTime();
          System.out.println("최악의 경우 오름차순 시간 : " + (end - start) + "ns");
      }
  }​

  
  
  
• 결과
  

  정렬 전 데이터 2 6 1 7 7 6 0 6 1 0 오름차순 정렬 후 데이터 0 0 1 1 2 6 6 6 7 7 내림차순 정렬 후 데이터 7 7 6 6 6 2 1 1 0 0 최선의 경우 오름차순 시간 : 3805ns 최악의 경우 오름차순 시간 : 18532ns

클래스 비교를 위한 구현

• 클래스의 특정 값을 이용한 정렬 코드 구현
  [BubbleAdvanced.java]
  

  package Sort.Bubble;
  
  import java.util.Comparator;
  
  public class BubbleAdvanced {
      public static <T> void sort(T[] arr) {
          Comparable<? super T> comp;
          boolean isAlreadySorted = true;
          int n = arr.length;
  
          for(int i=0; i<n-1; i++) {
              for(int j=0; j<n-i-1; j++) {
                  comp = (Comparable<? super T>)arr[j];
                  if (comp.compareTo(arr[j + 1]) > 0) {
                      swap(arr, j, j + 1);
                      isAlreadySorted = false;
                  }
              }
  
              if (isAlreadySorted){
                  break;
              }
          }
      }
  
      /**
       *
       * @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;
      }
  
      public static <T> void sort(T[] arr, Comparator<? super T> comparator) {
          boolean isAlreadySorted = true;
          int n = arr.length;
  
          for(int i=0; i<n-1; i++) {
              for(int j=0; j<n-i-1; j++) {
                  if (comparator.compare(arr[j], arr[j + 1]) > 0) {
                      swap(arr, j, j + 1);
                      isAlreadySorted = false;
                  }
              }
  
              if (isAlreadySorted){
                  break;
              }
          }
      }
  }​

• BubbleAdvanced 테스트
  

  package Sort.Bubble;
  
  import java.util.Comparator;
  
  public class BubbleAdvancedMain {
      private static final int MAX_COUNT = 10;
  
      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);
          }
  
          // 배열은 참조형 이므로 arr을 넘길 경우 arr값이 변경되기 때문에 복사본을 생성한 후 테스트
          Integer[] ascArrTest = arr.clone();
          System.out.println("정렬 전 데이터");
          for (int i : ascArrTest) {
              System.out.println(i);
          }
          System.out.println();
  
          BubbleAdvanced.sort(ascArrTest);
          System.out.println("오름차순 정렬 후 데이터");
          for (int i : ascArrTest) {
              System.out.println(i);
          }
          System.out.println();
  
          Integer[] descArrTest = arr.clone();
          System.out.println("내림차순 정렬 후 데이터");
          BubbleAdvanced.sort(descArrTest, new Comparator<Integer>() {
              @Override
              public int compare(Integer o1, Integer o2) {
                  if (o1 < o2) {
                      return 1;
                  } else if (o1 == o2) {
                      return 0;
                  } else {
                      return -1;
                  }
              }
          });
          for (int i : descArrTest) {
              System.out.println(i);
          }
          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;
              }
          }
  
          System.out.println("클래스 정렬 전 데이터");
          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);
          for(Student student : students) {
              System.out.println(student.toString());
          }
          System.out.println();
  
          System.out.println("클래스 정렬 후 데이터");
          BubbleAdvanced.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(Student student : students) {
              System.out.println(student.toString());
          }
      }
  }​

• 결과
  

  정렬 전 데이터 7 0 0 9 4 4 6 0 5 0 오름차순 정렬 후 데이터 0 0 0 0 4 4 5 6 7 9 내림차순 정렬 후 데이터 9 7 6 5 4 4 0 0 0 0 클래스 정렬 전 데이터 name='아이언맨', age=11 name='헐크', age=4 name='토르', age=15 name='블랙위도우', age=13 name='캡틴', age=4 클래스 정렬 후 데이터 name='헐크', age=4 name='캡틴', age=4 name='아이언맨', age=11 name='블랙위도우', age=13 name='토르', age=15