Home > Java, Java Misc, Java Sorting > Quicksort in Java

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
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: