퀵 정렬(Quick sort) / 병합(합병) 정렬 (Merge sort)

1. 퀵 정렬(Quick sort)

퀵 정렬 알고리즘은 분할과 재귀로 이뤄진다.

1. 배열을 분할한다. 
2. 피벗의 왼쪽과 오른쪽에 있는 하위 배열을 각각 또다른 배열로 보고, 각 하위 배열을 분할하고 각 하위 배열에 있는 피벗의 왼쪽과 오른쪽에서 더 작아진 하위 배열을 얻는다. 

 

분할 정복 방법을 통해 정렬.

배열 중 한 원소를 정한 뒤(pivot) 피벗 보다 작은 원소들, 피벗보다 큰 원소들로 나눔(분할 divide).

나눈 배열들에 대해 재귀적으로 함수 실행(피벗을 정하고 다시 그 배열에서 작은 배열로 나누고의 반복)

시간 복잡도는 최악의 경우 O(N²)이며 최선의 경우 O(NlogN)임. 다른 정렬 알고리즘에 비해 빠름.

불안정 정렬(unstable sort)이며 오히려 정렬이 되어있는 경우 더 오래걸림.

 

https://medium.com/@bill.shantang/8-classical-sorting-algorithms-d048eec3fdab

 

Java구현 코드

public class QuickSort {

    // 배열을 분할 한다.
    // 임의의 수 pivot을 설정하고, pivot 보다 작은 수는 왼쪽에, 큰 수는 오른쪽에 둔다.

    // [조건]
    // 1. LP는 pivot보다 큰 수를 만날 때 까지 오른쪽으로 옮긴다.
    // 2. RP는 pivot보다 작은 수를 만날 때 까지 왼쪽으로 옮긴다.
    // 3. 만약 LP가 RP를 만났거나 넘어선 경우라면 LP와 pivot을 교환한다.
    // 4. 아니라면 LP와 RP를 교환하고 다시 진행한다.
    private int partitioning(int[] arr, int left, int right) {
        int pivot = right;
        int pivotValue = arr[pivot];

        // 두 포인터를 사용해 배열 가장 왼쪽 값과 피벗 제외 가장 오른쪽 값을 할당한다.
        int leftPointer = left, rightPointer = pivot - 1;

        while (true) {
            // 왼쪽 포인터를 한 셀씩 오른쪽으로 옮기면서 피벗보다 크거나 같은 값에 도달하면 멈춘다.
            while (arr[leftPointer] < pivotValue) {
                leftPointer++;
            }

            // 오른쪽 포인터를 한 셀씩 왼쪽으로 옮기면서 피벗보다 작거나 같은 값에 도달하거나, 배열 맨 앞에 도달하면 멈춘다.
            while (arr[rightPointer] > pivotValue) {
                rightPointer--;
                if (0 >= rightPointer) {
                    break;
                }
            }

            if (leftPointer >= rightPointer) {
                break;
            }

            if (leftPointer < rightPointer) {
                int temp = arr[leftPointer];
                arr[leftPointer] = arr[rightPointer];
                arr[rightPointer] = temp;

                leftPointer++;
            }

        }

        // 왼쪽 포인터가 오른쪽 포인터에 도달하거나 넘어섰으면 왼쪽 포인터 값과 피벗을 교환한다.
        arr[pivot] = arr[leftPointer];
        arr[leftPointer] = pivotValue;

        return leftPointer;
    }

    void sort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }

        int pivot = partitioning(arr, left, right);

        sort(arr, left, pivot - 1);
        sort(arr, pivot + 1, right);
    }

    @Test
    void testPartitioning() {
        int[] arr = {2, 6, 8, 3, 7};
        int nextPivot = partitioning(arr, 0, arr.length - 1);

        assertThat(nextPivot).isEqualTo(3);
    }

    @Test
    void testSort() {
        int[] arr = {4, 7, 2, 1, 9};
        sort(arr, 0, arr.length - 1);

        int[] arr2 = {1, 34, 12, 65, 7, 11, 4, 22};
        sort(arr2, 0, arr2.length - 1);

        int[] arr3 = {8, 1, 3, 78, 32, 0, 33, 17, 6};
        sort(arr3, 0, arr3.length - 1);

        assertAll(() -> {
            assertThat(arr).isEqualTo(new int[]{1, 2, 4, 7, 9});
            assertThat(arr2).isEqualTo(new int[]{1, 4, 7, 11, 12, 22, 34, 65});
            assertThat(arr3).isEqualTo(new int[]{0, 1, 3, 6, 8, 17, 32, 33, 78});
        });
    }

}

 

 

 

2. 병합(합병) 정렬(Merge sort)

퀵 정렬과 마찬가지로 분할 정복 방법을 통해 정렬. 퀵 정렬과 비슷하지만 안정 정렬(stable sort)임.

요소를 쪼갠 후 정렬, 그리고 다시 정렬된 요소를 합병의 반복.

시간복잡도는 O(n log n)

 

https://medium.com/@bill.shantang/8-classical-sorting-algorithms-d048eec3fdab

 

Java구현 코드

 

static void mergeSort(int[] arr, int left, int right) {
  if(left < right) {
    int mid = (left + right) /2 ;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
  }
}

static void merge(int[] arr, int left, int mid, int right) {
  int[] L = Arrays.copyOfRange(arr, left, mid + 1);
  int[] R = Arrays.copyOfRange(arr, mid + 1, right + 1);

  int i = 0, j = 0, k = left;
  int l_length = L.length, r_length = R.length;

  while(i < l_length && j < r_length) {
    if(L[i] <= R[j]) {
    	arr[k] = L[i++];
    }else {
    	arr[k] = R[j++];
    }
    k++;
  }

  while(i < l_length) {
  	arr[k++] = L[i++];
  }
  while(j < r_length) {
  	arr[k++] = R[j++];
  }
}