[Java] 퀵 정렬 구현

퀵 정렬을 자바로 구현하는 두 가지 방법

pivot을 중간에 놓았을 때

import java.util.Arrays;

// 피봇을 중간에 놓고하는 코드

public class QuickSort {
    public void sort(int[] data, int l, int r) {

        int left = l;
        int right = r;
        int pivot = data[(l + r) / 2];

        do {
            while (data[left] < pivot)
                left++;
            while (data[right] > pivot)
                right--;
            if (left <= right) {
                int temp = data[left];
                data[left] = data[right];
                data[right] = temp;
                left++;
                right--;
            }

        } while (left <= right);
        if (l < right)
            sort(data, l, right);
        if (r > left)
            sort(data, left, r);

    }

    public static void main(String[] args) {
        int[] data = { 1, 88, 4, 9, 5, 6};

        System.out.println("원본: "+Arrays.toString(data));
        QuickSort app = new QuickSort();

        app.sort(data, 0, data.length - 1);
        System.out.println("정렬: " + Arrays.toString(data));
    }
}

pivot을 맨 앞에 놓았을 때

import java.util.Arrays;

public class QuickSort2 {
    public static void main(String[] args) {
        int[] data = { 55, 1, 99, 23, 10, 5};
        //int[] data = { 5, 3, 8, 4, 9, 1, 6, 2, 7,10 };
        //int[] data = { 6,23,1,65,78,3,21,10,9 };

        QuickSort2 app = new QuickSort2();
        System.out.println("원본: "+Arrays.toString(data));
        app.sort(data, 0, data.length - 1);
        System.out.println("정렬: " + Arrays.toString(data));
    }

    private void sort(int[] data, int left, int right) {
        int lowIdx = left + 1;
        int highIdx = right;
        int pivot = data[left];
        if(left < right) {
            while (lowIdx <= highIdx) {
                while (lowIdx <= right && data[lowIdx] <= pivot) { // pivot보다 큰 수가 나올 때 까지 lowIdx 늘리기
                    lowIdx++;
                }

                while (left + 1 <= highIdx && pivot <= data[highIdx]) { // pivot보다 작은 수가 나올 때 까지 highIdx 늘리기
                    highIdx--;
                }

                if (lowIdx <= highIdx) {
                    int temp = data[lowIdx];
                    data[lowIdx] = data[highIdx];
                    data[highIdx] = temp;
                } else {
                    data[left] = data[highIdx];
                    data[highIdx] = pivot;
                }
            }
            System.out.println("과정: " + Arrays.toString(data));

            sort(data, left, highIdx - 1);
            sort(data, highIdx + 1, right);
        }
    }
}