Wednesday, September 17, 2014

Quick Sort Implementation [Java]

Quicksort makes O(n log n) comparisions to sort n items. In the worst case, it makes O(n^2) comparisions. Quicksort is often faster in practice than other O(n log n) algorithms. Qucicksort is a comparison sort.

Quicksort is NOT a stable sort.
Quicksort can be implemented with an in-place partitioning algorithm, so the entire sort can be done with only O(log n) additional space used by the stack during recursion.

This video has a really nice explanation of the algorithm:

https://www.youtube.com/watch?v=COk73cpQbFQ

Code:

import java.util.Arrays;

public class QuickSort {

    public static void quickSort(int array[]) {
        quickSorter(array, 0, array.length - 1);
    }

    public static void quickSorter(int array[], int lo, int hi) {
        if (lo > hi) return;

        int partition = partition(array, lo, hi);
        quickSorter(array, lo, partition - 1);
        quickSorter(array, partition + 1, hi);
    }

    private static int partition(int array[], int lo, int hi) {
        int partitionIndex = lo;

        for (int i = lo; i <= hi; ++i) {
            if (array[i] < array[hi]) {
                int temp = array[partitionIndex];
                array[partitionIndex] = array[i];
                array[i] = temp;
                partitionIndex++;
            }
        }
        int temp = array[partitionIndex];
        array[partitionIndex] = array[hi];
        array[hi] = temp;
        return partitionIndex;
    }

    public static void main(String[] args) {
        int[] array = new int[]{3, 4, 3, 2, 1, 3, 44, 21, 3, 2, 33, 12, 123};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }
}

Output:

[1, 2, 2, 3, 3, 3, 3, 4, 12, 21, 33, 44, 123]

No comments:

Post a Comment