알고리즘) Quick/Merge Sort (퀵/병합 정렬)

Quick Sort (퀵 정렬)

기준값(pivot)을 잡고, pivot보다 작은수는 좌partition으로 큰수는 우partition으로 보낸다.
다시 좌/우partition에서 각각 pivot을 설정하고 좌/우partition으로 나눈다.
이러한 과정 반복

• divide & conquer
• pivot을 설정하는 방법이 다양하고, 이에 따라 성능이 결정된다. (pivot을 좌우끝값 또는 중앙값으로 등등..)
• 평균 시간 복잡도 : O(nlog2n)
• 최악 시간 복잡도 : O(n2)
• 구현방법이 제각각, 다양하다

import java.lang.Math;
import java.util.Scanner;;

public class Test {

    public static void printArray(int[] arr) {
        for(int i=0; i<arr.length; i++) {
            System.out.printf("%2d ", arr[i]);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; i++) {
            arr[i] = (int) (Math.random() * 100);
        }
        System.out.print("before Sort: ");
        printArray(arr);

        quickSort(arr, 0, n-1);

        System.out.print("after Sort: ");
        printArray(arr);
    }

    public static void quickSort(int[] arr, int left, int right){
        int L = left;
        int R = right;
        int pivot = arr[(left+right)/2];

        do {
            while(arr[L] < pivot) L++;
            while(arr[R] > pivot) R--;
            if(L <= R){
                int temp = arr[L];
                arr[L] = arr[R];
                arr[R] = temp;
                L++;
                R--;
                printArray(arr);
            }
        } while (L <= R);

        if(left < R) quickSort(arr, left, R);
        if(right > L) quickSort(arr, L, right);
    }


}

public static void quickSort(int arr[], int left, int right) {
        int pivot, left_temp, right_temp;
        left_temp = left;
        right_temp = right;
        pivot = arr[left];
        while (left < right) {
            while (arr[right] >= pivot && (left < right)) {
                right--;
            }
            if (left != right) {
                arr[left] = arr[right];
            }
            while (arr[left] <= pivot && (left < right)) {
                left++;
            }
            if (left != right) {
                arr[right] = arr[left];
                right--;
            }
        }
        arr[left] = pivot;
        pivot = left;
        left = left_temp;
        right = right_temp;
        printArray(arr);
        if (left < pivot) quickSort(arr, left, pivot - 1);
        if (right > pivot) quickSort(arr, pivot + 1, right);
    }

---

Merge Sort (병합 정렬)

Divide & Conquer 개념을 이용.
분할후 합치며 정렬시킨다.
(합칠땐 정렬된 상태이므로 두 요소의 맨앞 자리 값들을 비교하면됨)
=> Two Pointer 알고리즘으로 병합

• 시간 복잡도 : O(nlog2n)

public static void mergeSort(int arr[], int left, int right) {
        if (left>=right) return;
        int M = (left+right)/2;

        mergeSort(arr, left, M);
        mergeSort(arr, M+1, right);

        ArrayList<Integer> tmp = new ArrayList<>();

        for(int L=left, R=M+1 ; L < M+1 || R < right+1 ; ) {
            if( (L < M+1 && R < right+1 && arr[L]<arr[R]) || R == right+1 )
                tmp.add(arr[L++]);
            else
                tmp.add(arr[R++]);
        }

        for(int i=left ; i<=right ; i++) {
            arr[i] = tmp.get(i-left);
        }
        printArray(arr);
    }