クイックソートQuick Sort

自分で書いたコードを記録してください.2つのpartitionの方法をそれぞれ記録した.

public class QuickSort {

    public static void quickSort(int[] nums, int start, int end) {

        if(start >= end) {

            return;

        }

        int pivot = partition2(nums, start, end);

        quickSort(nums, start, pivot - 1);

        quickSort(nums, pivot + 1, end);

    }



    public static int partition(int[] nums, int start, int end) {

        int pivot = start;

        for(int i = start + 1; i <= end; i++) {

            if(nums[i] <= nums[start]) {

                pivot++;

                int temp = nums[pivot];

                nums[pivot] = nums[i];

                nums[i] = temp;

            }

        }

        int temp = nums[pivot];

        nums[pivot] = nums[start];

        nums[start] = temp;

        return pivot;

    }



//    better partition method

    public static int partition2(int[] nums, int start, int end) {

        int pivot = start, i = start + 1, j = end;

        while(i < j) {

            while(i <= end && nums[i] <= nums[pivot]) {

                i++;

            }

            while(nums[j] >nums[pivot]) {

                j--;

            }

            if(i >= j) {

                break;

            }

            int temp = nums[i];

            nums[i] = nums[j];

            nums[j] = temp;

        }

        i--;

        int temp = nums[i];

        nums[i] = nums[pivot];

        nums[pivot] = temp;

        return i;

    }



    public static void main(String[] args) {

        int[] nums = new int[]{13, 6, 9, 1, 19, -21, 5};

        quickSort(nums, 0, nums.length - 1);

        System.out.println(nums);

    }

}