[Algorithm] Quick Sort (Merge Sort 비교)

이전 포스트에서 합병 정렬에 대해서 알아보았다.

이번에는 퀵 정렬을 알아보면서 합병 정렬과 차이점을 알아보자.

합병 정렬에대한 설명은 생략한다.

💡 퀵 정렬 Quick Sort

하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법

🔑 단계

분할(Divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다.

정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.

결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다. 순환 호출이 한번 진행될 때마다 최소한 하나의 원소(피벗)는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

💎 소스

public class Main {
  public static void main(String[] args) {

// list 초기화 (10만 개의 양수)
    int[] list = new int[100000];
    Random random = new Random();
    for (int i = 0; i < list.length; i++) {
      list[i] = Math.abs(random.nextInt()); // 음수가 아닌 값 생성
    }
    quickSortTest(list);

  }

  private static void quickSortTest(int[] list) {
    SimpleDateFormat sdf1 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:ms");
    QuickSort quickSort = new QuickSort();

    Date now = new Date();
    String start = sdf1.format(now);

    quickSort.quickSort(list);

    Date now2 = new Date();
    String end = sdf1.format(now2);

    System.out.println("시작시간 quickSort : " + start);
    System.out.println("종료시간 quickSort : " + end);
    System.out.println("quickSort 걸린 시간 : " + (now2.getTime() - now.getTime()) / 1000.0 + "초");
    System.out.println();
  }
}

class QuickSort {
  public void quickSort(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
  }

  private void quickSort(int[] arr, int start, int end) {
    int part2 = partition(arr, start, end);
    if (start < part2 - 1) {
      quickSort(arr, start, part2 - 1);
    }
    if (part2 < end) {
      quickSort(arr, part2, end);
    }
  }

  private int partition(int[] arr, int start, int end) {
    int pivot = arr[(start + end) / 2];
    while (start <= end) {
      while (arr[start] < pivot) start++;
      while (arr[end] > pivot) end--;

      if (start <= end) {
        swap(arr, start, end);
        start++;
        end--;
      }
    }
    return start;
  }

  private void swap(int[] arr, int start, int end) {
    int temp = arr[start];
    arr[start] = arr[end];
    arr[end] = temp;
  }

}

결과

비교

quickSort, mergerSort, 자바 기본 Sort 이 세가지를 가지고 비교하고자 아래처럼 소스를 작성하였다.

이번에 자바 기본 Sort가 퀵 정렬이라는 것을 알게 되어 그냥 같이 테스트를 진행해 보았다.

💎 소스

public class Main {
public static void main(String[] args) {
    int size = 100000;

    int[] list = new int[size];
    Random random = new Random();
    for (int i = 0; i < list.length; i++) {
      list[i] = Math.abs(random.nextInt());
    }

    quickSortTest(list);

    int[] list2 = new int[size];
    Random random2 = new Random();
    for (int i = 0; i < list.length; i++) {
      list2[i] = Math.abs(random2.nextInt());
    }

    ArraySortTest(list2);

    int[] list3 = new int[size];
    Random random3 = new Random();
    for (int i = 0; i < list3.length; i++) {
      list3[i] = Math.abs(random3.nextInt());
    }

    mergeSortTest(list3);
  }

  private static void quickSortTest(int[] list) {
    SimpleDateFormat sdf1 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:ms");
    QuickSort quickSort = new QuickSort();

    Date now = new Date();
    String start = sdf1.format(now);

    quickSort.quickSort(list);

    Date now2 = new Date();
    String end = sdf1.format(now2);

    System.out.println("시작시간 quickSort : " + start);
    System.out.println("종료시간 quickSort : " + end);
    System.out.println("quickSort 걸린 시간 : " + (now2.getTime() - now.getTime()) / 1000.0 + "초");
    System.out.println();
  }

  private static void mergeSortTest(int[] list) {
    SimpleDateFormat sdf1 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:ms");
    MergeSort mergeSort = new MergeSort();

    Date now = new Date();
    String start = sdf1.format(now);

    mergeSort.solution(list);

    Date now2 = new Date();
    String end = sdf1.format(now2);

    System.out.println("mergeSort 시작시간 : " + start);
    System.out.println("mergeSort 종료시간 : " + end);
    System.out.println("mergeSort 걸린 시간 : " + (now2.getTime() - now.getTime()) / 1000.0 + "초");
    System.out.println();
  }

  private static void ArraySortTest(int[] list) {
    SimpleDateFormat sdf1 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:ms");

    Date now = new Date();
    String start = sdf1.format(now);

    Arrays.sort(list);

    Date now2 = new Date();
    String end = sdf1.format(now2);

    System.out.println("ArraySort 시작시간 : " + start);
    System.out.println("ArraySort 종료시간 : " + end);
    System.out.println("ArraySort 걸린 시간 : " + (now2.getTime() - now.getTime()) / 1000.0 + "초");
    System.out.println();
  }
}


class MergeSort {
  public int[] solution(int[] numList) {

    int size = numList.length - 1;
    mergeSort(numList, 0, size);
    return numList;
  }

  void mergeSort(int[] numList, int left, int right) {

    int mid = 0;

    if (left < right) {
      // (left+right)/2 오버플로우 해결하기 위한 방법
      mid = left + (right - left) / 2;
      mergeSort(numList, left, mid);
      mergeSort(numList, mid + 1, right);
      merge(numList, left, mid, right);
    }
  }

  void merge(int[] list, int left, int mid, int right) {
    int[] sorted = new int[list.length];
    int i, j, k, l;
    i = left;
    j = mid + 1;
    k = left;

    /* 분할 정렬된 list의 합병 */
    while (i <= mid && j <= right) {
      if (list[i] <= list[j])
        sorted[k++] = list[i++];
      else
        sorted[k++] = list[j++];
    }

    // 남아 있는 값들을 일괄 복사
    if (i > mid) {
      for (l = j; l <= right; l++)
        sorted[k++] = list[l];
    }
    // 남아 있는 값들을 일괄 복사
    else {
      for (l = i; l <= mid; l++)
        sorted[k++] = list[l];
    }

    // 배열 sorted[](임시 배열)의 리스트를 배열 list[]로 재복사
    for (l = left; l <= right; l++)
      System.arraycopy(sorted, left, list, left, right - left + 1);
  }
}


class QuickSort {
  public void quickSort(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
  }

  private void quickSort(int[] arr, int start, int end) {
    int part2 = partition(arr, start, end);
    if (start < part2 - 1) {
      quickSort(arr, start, part2 - 1);
    }
    if (part2 < end) {
      quickSort(arr, part2, end);
    }
  }

  private int partition(int[] arr, int start, int end) {
    int pivot = arr[(start + end) / 2];
    while (start <= end) {
      while (arr[start] < pivot) start++;
      while (arr[end] > pivot) end--;

      if (start <= end) {
        swap(arr, start, end);
        start++;
        end--;
      }
    }
    return start;
  }

  private void swap(int[] arr, int start, int end) {
    int temp = arr[start];
    arr[start] = arr[end];
    arr[end] = temp;
  }

}

결과

---

마무리

처음 합병정렬과 퀵 정렬의 차이는 그렇게 크지 않을 것으로 예상을 하고 안정적인 합병정렬을 사용하려고 생각을 하고 있었다. 하지만 직접 비교해 본 결과 일반적으로 퀵 정렬이 더 빠를 것을 확인했다. 상황에 따라서 다르게 정렬을 해야 한다는 것은 맞지만 솔직히 아직까지는 상황에 따라 어떤 정렬이 적합한지 판단을 하기엔 모자란다고 생각이 든다. 10만 건, 100만 건 데이터가 더 많아졌을 때는 병합 정렬과 퀵 정렬의 차이는 더욱더 커지는 것을 확인할 수 있었다. 이처럼 퀵 정렬이 굉장히 빠른 속도를 보여주고 있어 앞으로 퀵 정렬을 자주 사용할 것 같다. 자바 기본 Sort 함수는 퀵 정렬 기반이므로 직접 퀵 정렬 알고리즘을 구현해서 사용하지 않고 자바 기본 Sort로 사용하면 편리할 것 같다.

---

출처 : https://www.youtube.com/watch?v=7BDzle2n47c - [자료구조 알고리즘] 퀵정렬(Quicksort)에 대해 알아보고 자바로 구현하기 - 엔지니어 대한민국

출처 : https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html - [알고리즘] 퀵 정렬(quick sort)이란