Geekpedia Tutorials Home

Building a C# Chat Client and Server

Building a C# Chat Client and ServerA step by step tutorial teaching you how to create your own chat client and chat server easily in C#, for local networks or the Internet.

in C# Programming Tutorials

Getting Hard Drive Information

Getting Hard Drive InformationA C# tutorial showing you how to make use of WMI to extract information on disk drives, such as model, capacity, sectors and serial number.

in C# Programming Tutorials

UPS Shipping Calculator

UPS Shipping CalculatorThis tutorial will teach you how to calculate the shipping cost based on the weight, height, length and depth of the box, the distance and the UPS service type.

in PHP Programming Tutorials

Create Your Own Rich Text Editor

Create Your Own Rich Text EditorCreating a Rich Text Editor using JavaScript is easier to do than you might think, thanks to the support of modern browsers; this tutorial will walk you through it.

in JavaScript Programming Tutorials
Search
Tutorials
Programming Tutorials
IT Jobs
From CareerBuilder
Geekpedia » Java Tutorials » Quicksort in Java

Quicksort in Java

A quick intro to the Quicksort algorithm in Java, showing an efficient (if not optimal) way to sort.

 On Monday, July 7th 2008 at 07:28 PM
By Jesse Bonzo (View Profile)
****-   (Rated 4 with 7 votes)
Contextual Ads
More Java Resources
Advertisement

In my opinion, Quicksort is the best algorithm for sorting, when it is implemented correctly. It is the default sorting algorithm in Java itself. Of course, writing it in Java is probably not the best, but it is important to know how it works in case you need to write some variation of it for some other purpose.
The main idea is this, pick a pivot item (preferably the average of the data in the array), place all items less than and equal to the pivot item in the front of the array, all the items greater than the pivot in the back of the array and replace the pivot in the middle of the array, then recursively sort the front and back halves. The best way to do this is with a partition function that swaps values around within the array to save space. This is that function:

  1. private int partition(T[] array, int lo, int hi, int pivotIndex)
  2. {
  3.    T pivotValue = array[ pivotIndex ];
  4.  
  5.    swap(array, pivotIndex, hi); //send pivot item to the back
  6.  
  7.    int index = lo; //keep track of where the front ends
  8.  
  9.    for (int i = lo; i < hi; i++) //check from the front to the back
  10.    {
  11.       //swap if the current value is less than the pivot
  12.       if ( (array[i]).compareTo(pivotValue) <= 0 )
  13.       {
  14.          swap(array, i, index);
  15.          index++;
  16.       }
  17.    }
  18.  
  19.    swap(array, hi, index); //put pivot item in the middle
  20.  
  21.    return index;
  22. }

This code is a little tricky to understand at first, but go through it slowly. First, we swap the pivot with the last element in the segment of the array being partitioned. Second, we set the marker index to be the front of the segment. Then the array is scanned, checking each element to see if it is less than or equal to the pivot item. If it is, the it is swapped to the front, which is where index points to and index is incremented. At the end of all that, index points to where the pivot should be replaced. If no elements were found to be less than the pivot, then the pivot should be the first element, and like wise, if all the elements were found to be less than the pivot, the pivot should be the last element. The pivot's index is returned so that it can be used in the recursive sort step. Also, the pivot is now in it's final place and does not need to be moved anymore.

  1. private T[] quicksort(T[] array, int lo, int hi)
  2. {
  3.    if (hi > lo)
  4.    {
  5.       int partitionPivotIndex = lo;
  6.  
  7.       int newPivotIndex = partition(array, lo, hi, partitionPivotIndex);
  8.  
  9.       quicksort(array, lo, newPivotIndex-1);
  10.       quicksort(array, newPivotIndex+1, hi);
  11.    }
  12.    return (T[]) array;
  13. }

This is the actual sorting function that is called recursively. See that since the newPivotIndex points to where the pivot was, and it needs to stay there, the function is only called on the segments from lo to newPivotIndex-1 and newPivotIndex+1 to hi.
There is a problem with this code however. What happens if the array is already sorted? Go through this step by step and watch what happens. The lowest element in the segment is picked as the pivot every time. This makes the first half be just the pivot, and nothing happens with <code>quicksort(array, lo, newPivotIndex-1);</code> and the entire array minus the pivot is passed into

  1. quicksort(array, newPivotIndex+1, hi);
It's selection sort! That's no good, we want to beat the O(n^2) time complexity of selection sort. Granted, this problem only occurs if the array is sorted or close to sorted, but that can happen pretty often. There are some complicated way of picking a better pivot, but I'll just use a random number to prevent the lowest number from being picked every time.
  1. private T[] quicksort(T[] array, int lo, int hi)
  2. {
  3.    if (hi > lo)
  4.    {
  5.       int partitionPivotIndex = (int)(Math.random()*(hi-lo) + lo);
  6.       int newPivotIndex = partition(array, lo, hi, partitionPivotIndex);
  7.       quicksort(array, lo, newPivotIndex-1);
  8.       quicksort(array, newPivotIndex+1, hi);
  9.    }
  10.    return (T[]) array;
  11. }
With a random number, there is no guarantee that it still won't "go quadratic", but the chances are greatly reduced since the expected value of the random number is the average of hi and lo, and the expected value of the number at that index in an already (or close to) sorted array is the average of that array. If the average value of the array is picked as the pivot, then about half of the array is passed into each recursive call. If half of the array is passed into each call then the time complexity of the algorithm becomes O(nlogn) since the partition portion takes O(n) time and half of the array is recursed on with O(logn) time, which is much better for large values of n. So putting it all together...
  1. public class QuickSort<T extends Comparable<T>>
  2. {
  3.    public void sort(T[] array)
  4.    {
  5.       array = quicksort(array, 0, array.length-1);
  6.    }
  7.  
  8.    private T[] quicksort(T[] array, int lo, int hi)
  9.    {
  10.       if (hi > lo)
  11.       {
  12.          int partitionPivotIndex = (int)(Math.random()*(hi-lo) + lo);
  13.          int newPivotIndex = partition(array, lo, hi, partitionPivotIndex);
  14.          quicksort(array, lo, newPivotIndex-1);
  15.          quicksort(array, newPivotIndex+1, hi);
  16.       }
  17.       return (T[]) array;
  18.    }
  19.  
  20.    private int partition(T[] array, int lo, int hi, int pivotIndex)
  21.    {
  22.       T pivotValue = array[ pivotIndex ];
  23.  
  24.       swap(array, pivotIndex, hi); //send to the back
  25.  
  26.       int index = lo;
  27.  
  28.       for (int i = lo; i < hi; i++)
  29.       {
  30.          if ( (array[i]).compareTo(pivotValue) <= 0 )
  31.          {
  32.             swap(array, i, index);
  33.             index++;
  34.          }
  35.      }
  36.  
  37.       swap(array, hi, index);
  38.  
  39.       return index;
  40.    }
  41.  
  42.    private void swap(T[] array, int i, int j)
  43.    {
  44.       T temp = array[i];
  45.       array[i] = array[j];
  46.       array[j] = temp;
  47.    }
  48.  
  49. }
Digg Digg It!     Del.icio.us Del.icio.us     Reddit Reddit     StumbleUpon StumbleIt     Newsvine Newsvine     Furl Furl     BlinkList BlinkList

Rate Rate this tutorial
Comment Current Comments
by Carlo dela Cruz on Wednesday, August 20th 2008 at 12:11 AM

Nice your providing real life solutions to real life entities and problems! Thank you very much!

by Your Wife on Saturday, September 27th 2008 at 11:16 AM

Since you're so smart, I bet you're super hot. :)

by Handsome on Tuesday, October 14th 2008 at 04:43 PM

we cant read the code

by me on Friday, January 23rd 2009 at 02:15 AM

yung steps po

by Sindre M on Sunday, April 12th 2009 at 07:19 PM

Fantastic! Thank you very much, this helped me a bunch with my assignment here. I still have no clue how to implement this using threads, however, but I guess I'll manage, once I get to know it better. Once again, thank you. ;)

by Clearer on Tuesday, August 25th 2009 at 04:58 AM

Inplace mergesort is a lot better (faster) and so is randomized quicksort (at least it's never a lot slower) -- in fact, quick sort is not that quick at all. Heapsort and smoothsort can be faster too.

Most of the time you will want to sort your list with inplace mergesort and then move on to something that take advantage of the fact that your list is already partially sorted (like insertion sort or smoothsort) after that.

by A on Sunday, January 10th 2010 at 06:11 PM

Nice code but he is not the inventer of the QuickSort. That guy is Antony Hoare.

by jacob on Friday, March 12th 2010 at 01:33 AM

wala

by jacob on Friday, March 12th 2010 at 01:33 AM

wala

by ljg on Wednesday, May 5th 2010 at 10:56 AM

;khn


Comment Comment on this tutorial
Name: Email:
Message:
Comment Related Tutorials

Selection Sort Algorithm in Java

On Wednesday, April 16th 2008 at 09:54 PM by Louis Fernandez in Java

Bubble Sort Algorithm in Java

On Sunday, March 2nd 2008 at 08:37 PM by Louis Fernandez in Java

Introduction to Arrays in Java

On Saturday, March 1st 2008 at 09:56 PM by Louis Fernandez in Java


Comment Related Source Code
There is no related source code.

Jobs Java Job Search
My skills include:
Enter a City:

Select a State:
Advanced Search >>
Sponsors
Discover Geekpedia
News News
Tutorials Tutorials
Source Code Source Code
Pictures Pictures
Videos Videos
Reviews Reviews
Special Report Special Reports
Bargains Bargains
Resources Resources
Icons Icons
Newsgroups Newsgroups
Knowledge Base Knowledge Base
Books Books
Magazines Magazines
Books Downloads
Jobs Jobs
Forums Forums
Search Search

Other Resources