## Quicksort in Java

QuickSort is one of best sorting algorithms. While the worst case scenario is O(n^2), the average case is O(nlgn). Additionally, it is possible to implement in highly optimized way as well do several of its parts in parallel.

package com.labeltop.sort; public class QuickSort { public void sort(Comparable[] c) { quicksort(c, 0, c.length-1); } private void quicksort(Comparable[] comparables, int start, int end) { // get a pivot point int pivot = start + ((int) (Math.random() * (end - start))); Comparable cPivot = comparables[pivot]; // where to start on either side of pivot int left = start; int right = end; // loop till they overlap while (left <= right) { // find first on left that is bigger than pivot while (cPivot.compareTo(comparables[left]) > 0) { // more towards pivot left++; } // find first on right that is less than pivot while (cPivot.compareTo(comparables[right]) < 0) { // more towards pivot right--; } // exchange them if (left <= right) { Comparable temp = comparables[left]; comparables[left] = comparables[right]; comparables[right] = temp; //go to next ones towards the pivot left++; right--; } } //recurse on left if (right > start) { quicksort(comparables, start, right); } //recurse on right if (left < end) { quicksort(comparables, left, end); } } }

Advertisements

Categories: Java, Java Misc, Java Sorting

Comments (0)
Trackbacks (0)
Leave a comment
Trackback