Quicksort Java implementation

import java.util.Arrays;

public class QuickSort {
    int[] data;
    public void quicksort(int[] nums) {
        if (nums == null || nums.length == 0) return;
        data = nums;
        sort(0, nums.length - 1);
    }
    private void sort(int left, int right) {
        if (right <= left) return;
        int pivot = partition(left, right);
        sort(left, pivot - 1);
        sort(pivot + 1, right);
    }

    /**     * put all the numbers that are smaller than pivot to the left     * **/    int partition(int left, int right) {
        int pivot = data[right];
        int startIndex = left;
        for (int i = left; i < right; i++) {
            //all the nums on the left of startIndex are smaller than pivot
            //the number at startIndex is >= pivot            if (data[i] < pivot) {
                swap(startIndex++, i);
            }
        }
        // put the pivot to the right position
        swap(startIndex, right);
        return startIndex;
    }

    void swap(int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
    public static void main(String[] args) {
        QuickSort qs = new QuickSort();
        int[] a = {200,30, 18,16,9,5,200};
        qs.quicksort(a);
        System.out.println(Arrays.toString(a));
    }
}

Comments

Popular posts from this blog

Can I name a method with the same name of the class in Java?

What is new in Java 8