In this article, we will talk about how you can implement in Java one of the most famous and useful sorting techniques: Quicksort. Quicksort is the most widely used sorting algorithm. One of the main reasons is that it is faster than most common sorting algorithms. It was developed by the famous Computer Scientist Tony Hoare and it is based on the “Divide and Conquer Algorithm”.
First, we are going to explain how Quicksort works on an algorithmic level, with some simple examples. Finally, we will build our implementation in Java and discuss its performance.
1. The Quicksort Alogrithm
Quicksort works recursively in order to sort a given array. These are the three basic steps of the Quicksort algorithm:
1. Partition the array into a left sub-array and a right sub-array, in which the items in the left sub-array are smaller than the specified item and the items in the right sub-array are greater than the specified item.
2. Recursively call the Quicksort to sort the left sub-array.
3. Recursively call the Quicksort to sort the right sub-array.
The partitioning step is the key, when sorting an array with Quicksort. Quicksort itself uses a Partition algorithm to partition the given array.
The partition works by using two cursors (let say), one at each end of the array. These cursor moves towards each other. If the left cursor finds an item which is smaller than the pivot value, it ignores it and moves forward. But if, the item’s value is greater than the pivot value, it stops. Similarly for the right cursor, if an item is greater than the pivot value it ignores it and moves backwards, else the cursor stops. When both cursors stop, the items pointed by the cursors get swapped. That’s because these items are on the wrong side of the array. After the swap, both the cursors continue, and stop at the items which are on the wrong side of the array and swap them. And that’s how the algorithms goes on, until finally, all items are sorted.
The pivot value is the value which is used to partition the array into two sub-arrays. After the partition, the items in the left sub-array are smaller than the pivot value, and the items in the right sub-array are greater than the pivot value.
In the above figure, we chose 56 as a pivot value. After the partition (which of course consists of more than one sub steps), all the items on the left of the pivot are smaller, and the items on the right of it are greater than it and the pivot is at its sorted position. Also notice that, at this point, the array is not sorted of course. That was just one partitioning step.
You can choose any random value from the array as a pivot value. Later we will see that choosing a pivot value affects the performance of the algorithm. But for now, lets us take the right most item of the array as a pivot value and attempt to create the first version of our Java implementation.
QuicksortExample.java
package com.javacodegeeks.sorting.quicksort; public class QuicksortExample { private static int []a; public static void main(String[] args) { // Get a random generated array a = getArray(); // prints the given array printArray(); // sort the array sort(); System.out.println(""); //prints the sorted array printArray(); } // This method sorts an array and internally calls quickSort public static void sort(){ int left = 0; int right = a.length-1; quickSort(left, right); } // This method is used to sort the array using quicksort algorithm. // It takes the left and the right end of the array as the two cursors. private static void quickSort(int left,int right){ // If both cursor scanned the complete array quicksort exits if(left >= right) return; // For the simplicity, we took the right most item of the array as a pivot int pivot = a[right]; int partition = partition(left, right, pivot); // Recursively, calls the quicksort with the different left and right parameters of the sub-array quickSort(0, partition-1); quickSort(partition+1, right); } // This method is used to partition the given array and returns the integer which points to the sorted pivot index private static int partition(int left,int right,int pivot){ int leftCursor = left-1; int rightCursor = right; while(leftCursor < rightCursor){ while(a[++leftCursor] < pivot); while(rightCursor > 0 && a[--rightCursor] > pivot); if(leftCursor >= rightCursor){ break; }else{ swap(leftCursor, rightCursor); } } swap(leftCursor, right); return leftCursor; } // This method is used to swap the values between the two given index public static void swap(int left,int right){ int temp = a[left]; a[left] = a[right]; a[right] = temp; } public static void printArray(){ for(int i : a){ System.out.print(i+" "); } } public static int[] getArray(){ int size=10; int []array = new int[size]; int item = 0; for(int i=0;i<size;i++){ item = (int)(Math.random()*100); array[i] = item; } return array; } }
- If we run the above code, we will have the following results:
4 94 87 24 44 30 37 97 47 93 4 24 30 37 44 47 87 93 94 97
Let’s discuss how the above program works.
The quickSort()
method takes two parameters, each holding the position of the cursors at the two ends of an array or a sub-array that needs to be sorted. For example, if left = 3
, then the left cursor points to element 3 of the array. The method exits, if left
is greater than or equal to right
, which means that the array is already sorted or the length of the array is one. It also generates a pivot value, in this case the right most value of the array. The pivot value is passed to the partition method which is used to partition the given array.
The partition()
method scans the array and swaps the items which are not at their proper place. The items which are greater than the pivot value, are swapped to the right of the pivot value with the values which are smaller than the pivot value. At the end of each scan, the left cursor ends up pointing to the left element of the right sub-array. The pivot is then swapped with it, and puts it into its proper sorted place. This method returns an integer that is the position of the sorted pivot value that partitioned the given array or a sub-array.
Then, the quicksort()
method spawns the recursive call to sort the left sub-array and the right sub-array. Let’s have a deeper look into the partition method.
int leftCursor = left-1;
: This statement initializes a leftCursor
to one less than the left parameter. This is because while scanning, it first gets incremented and then used to evaluate. For example, if we are scanning the complete array and not a sub-array, the leftCursor
would be at 0-1, i.e., -1
.
int rightCursor = right;
: This statement initializes a rightCursor
to the right end of the given array, i.e., rightCursor = array.lenght-1
.
while(leftCursor < rightCursor)
: The outer while
loop runs till the leftCursor
is not at same position or a position greater than the rightCursor
. When this condition evaluates to false, it means that the cursors has scanned the complete array.
while(a[++leftCursor] < pivot);
: This inner while
loop has nothing inside its body. It’s used to move the left cursor towards right and compare the item it’s pointing with the pivot. The loop terminates if the pointed value is greater than the pivot value.
while(rightCursor > 0 && a[--rightCursor] > pivot);
: This loop does a similar work. It moves towards the left of the array and compares each item it points with the pivot. If the pointed value is smaller than the pivot value, it terminates.
When both inner while
loops terminate, both the cursors point to the items which are not at their proper place. We first check whether the cursors have crossed each other, which means they have scanned the full array. Then, it exits from the loop, else the items get swapped.
Then, the quicksort()
method is called recursively. This time with the two sub-arrays, the left one starting from partitioin-1
, and the right one starting from partition+1
. It sorts the sub-arrays, until the full array gets partitioned and sorted, which finally results in the full sorted array.
Generally, quicksort operates in O(n*log n) time. But there are some cases, when its performance degrades to O(n^2). The problem lies in the selection of the pivot. In the above example, we choose the pivot randomly (the right most item of the array). The pivot should be the median of the items to be sorted. So that, half of the items in the array should be smaller than the pivot, and the rest should be the larger than the pivot. This would result in two equally sized sub-arrays. Two equal sized sub-arrays is, the best situation for the Quicksort algorithm, where it runs at O(logn). Having one large and one small sub-array results in less efficiency.
2. Median of 3 Partitioning
The best approach to choose a pivot, is by choosing the median of the first, middle, and the last items of the array. This approach is known as the “median of three approach”.
QuicksortMedianExample.java
package com.javacodegeeks.sorting.quicksort; public class QuicksortMedianExample { private static int []a; public static void main(String[] args) { // Get a random generated array a = getArray(); // prints the given array printArray(); // sort the array sort(); System.out.println(""); //prints the sorted array printArray(); } // This method sorts an array and internally calls quickSort public static void sort(){ int left = 0; int right = a.length-1; quickSort(left, right); } // This method is used to sort the array using quicksort algorithm. // It takes left and the right end of the array as two cursors private static void quickSort(int left,int right){ // If both cursor scanned the complete array, quicksort exits if(left >= right) return; // Pivot using median of 3 approach int pivot = getMedian(left, right); int partition = partition(left, right, pivot); // Recursively, calls the quicksort with the different left and right parameters of the sub-array quickSort(0, partition-1); quickSort(partition+1, right); } // This method is used to partition the given array and returns the integer which points to the sorted pivot index private static int partition(int left,int right,int pivot){ int leftCursor = left-1; int rightCursor = right; while(leftCursor < rightCursor){ while(a[++leftCursor] < pivot); while(rightCursor > 0 && a[--rightCursor] > pivot); if(leftCursor >= rightCursor){ break; }else{ swap(leftCursor, rightCursor); } } swap(leftCursor, right); return leftCursor; } public static int getMedian(int left,int right){ int center = (left+right)/2; if(a[left] > a[center]) swap(left,center); if(a[left] > a[right]) swap(left, right); if(a[center] > a[right]) swap(center, right); swap(center, right); return a[right]; } // This method is used to swap the values between the two given index public static void swap(int left,int right){ int temp = a[left]; a[left] = a[right]; a[right] = temp; } public static void printArray(){ for(int i : a){ System.out.print(i+" "); } } public static int[] getArray(){ int size=10; int []array = new int[size]; int item = 0; for(int i=0;i<size;i++){ item = (int)(Math.random()*100); array[i] = item; } return array; } }
- If we run the above code, we will have the following results:
80 4 33 30 65 14 35 25 31 12 4 12 14 25 30 31 33 35 65 80
In the above example, we have used the median-of-3-approrach to find a “good” pivot. We used the first, the middle, and last items of the array to find the median. The median is the middle item between the orderly placed items. This approach is not only used to select the pivot, but it also put the three items in their sorted place in the array. Let’s have a look at the getMedian()
used in the above example.
getMedian(int left, int right)
: This method is used to return a median among the three items specified. The returned median is used as the pivot in quicksort. This method has two parameters, both pointing at each end of the array or the sub-array. We used the middle, left and right items to find the median. At the end, we swapped the median with the item at the rightmost position of the array. So , after the scan all these three items should be in their proper sorted places in the array. This process is repeated with all the sub-arrays having different left, right and middle positions until the full array gets sorted.
3. Quicksort with String
So far, we have seen quicksort with integer arrays. In this example, we will sort an array of Strings
using quicksort.
QuicksortStringExample.java
package com.javacodegeeks.sorting.quicksort; public class QuicksortStringExample { private static String []a; public static void main(String[] args) { // Get an String array a = new String[]{"X","E","C","A"}; // prints the given array printArray(); // sort the array sort(); System.out.println(""); //prints the sorted array printArray(); } // This method sort an array internally and internally calls quickSort public static void sort(){ int left = 0; int right = a.length-1; quickSort(left, right); } // This method is used to sort the array using quicksort algorithm. // It takes left and the right end of the array as two cursors private static void quickSort(int left,int right){ // If both cursor scanned the complete array quicksort exits if(left >= right) return; // Pivot using median of 3 approach String pivot = getMedian(left, right); int partition = partition(left, right, pivot); // Recursively, calls the quicksort with the different left and right parameters of the sub-array quickSort(0, partition-1); quickSort(partition+1, right); } // This method is used to partition the given array and returns the integer which points to the sorted pivot index private static int partition(int left,int right,String pivot){ int leftCursor = left-1; int rightCursor = right; while(leftCursor < rightCursor){ while(((Comparable<String>)a[++leftCursor]).compareTo(pivot) < 0); while(rightCursor > 0 && ((Comparable<String>)a[--rightCursor]).compareTo(pivot) > 0); if(leftCursor >= rightCursor){ break; }else{ swap(leftCursor, rightCursor); } } swap(leftCursor, right); return leftCursor; } public static String getMedian(int left,int right){ int center = (left+right)/2; if(((Comparable<String>)a[left]).compareTo(a[center]) > 0) swap(left,center); if(((Comparable<String>)a[left]).compareTo(a[right]) > 0) swap(left, right); if(((Comparable<String>)a[center]).compareTo(a[right]) > 0) swap(center, right); swap(center, right); return a[right]; } // This method is used to swap the values between the two given index public static void swap(int left,int right){ String temp = a[left]; a[left] = a[right]; a[right] = temp; } public static void printArray(){ for(String i : a){ System.out.print(i+" "); } } }
- If we run the above code, we will have the following results:
X E C A A C E X
In the above example, we have sorted an array of Strings
, using the quicksort. The String
class implements the Comparable
interface and overrides the compareTo()
method. We have used the compareTo()
method to compare the Strings. We have downcasted the String to the Comparable
type and have used the compareTo()
method to find the greater or the smaller between them.
The comparison is done using the natural ordering of the String
. The natural ordering in the String
is maintained alphabetically from “A – Z” and then from “a – z”. The rest of the code works same as shown in the previous example.
4. Quicksort Objects
In this example, we will see how to sort Objects of a class using the Quicksort. We will create a generic quicksort method which can be used to sort objects of any class. The class needs to implement the Comparable
interface and override the method compareTo
in order to use the quicksort, otherwise, it will throw a ClassCastException
.
Let’s create an Employee
class and sort employees on basis of their employeeCode
using the Quicksort.
Employee.java
package com.javacodegeeks.entity; public class Employee implements Comparable<Employee>{ private String firstName; private String lastName; private int emplyeeCode; public Employee(String fistName,String lastName,int emplyeeCode){ this.firstName = fistName; this.lastName = lastName; this.emplyeeCode = emplyeeCode; } public String getFirstName() { return firstName; } public void setFirstName(String firstName) { this.firstName = firstName; } public String getLastName() { return lastName; } public void setLastName(String lastName) { this.lastName = lastName; } public int getEmplyeeCode() { return emplyeeCode; } public void setEmplyeeCode(int emplyeeCode) { this.emplyeeCode = emplyeeCode; } public String toString(){ return "Employee Code: "+getEmplyeeCode()+", Name:"+getFirstName()+" "+getLastName(); } public int compareTo(Employee o) { Employee e = (Employee)o; if(this.emplyeeCode > e.getEmplyeeCode()) return 1; if(this.emplyeeCode < e.getEmplyeeCode()) return -1; if(this.emplyeeCode == e.getEmplyeeCode()) return 0; return 0; } }
We have created an Employee
class which implements the Comparable
interface and overrides the compareTo()
method. The comparison between the Employee
objects is defined by comparing the employeeCode
property of the Employee
objects. The comparTo()
method returns an integer, which tells whether the current employeeCode
is greater than, or smaller than or equal to the compared employeeCode
. It returns 1, if the current employeeCode
is greater than the compared employeeCode
, -1 if, the current employeeCode
is smaller than the compared employeeCode
, else it returns 0 if both are equal. Since, the employeeCode
is of type integer, we have compared it using the simple integer comparison operators.
QuicksortObjectExample.java
package com.javacodegeeks.sorting.quicksort; import com.javacodegeeks.entity.Employee; public class QuicksortObjectExample<T extends Comparable<T>> { private T []a; public static void main(String[] args) { Employee []employees = new Employee[5]; Employee employee = new Employee("John","Carter",5658); employees[0] = employee; employee = new Employee("Mary","Carter",7412); employees[1] = employee; employee = new Employee("Alex","Lumb",1158); employees[2] = employee; employee = new Employee("David","Jhonson",1254); employees[3] = employee; employee = new Employee("Shaun","Smith",4587); employees[4] = employee; QuicksortObjectExample<Employee>ex = new QuicksortObjectExample<>(); // Assigned array ex.a = employees; // prints the given array ex.printArray(); // sort the array ex.sort(); System.out.println(""); //prints the sorted array ex.printArray(); } // This method sort an array and internally calls quickSort public void sort(){ int left = 0; int right = a.length-1; quickSort(left, right); } // This method is used to sort the array using quicksort algorithm. // It takes left and the right end of the array as two cursors private void quickSort(int left,int right){ // If both cursor scanned the complete array quicksort exits if(left >= right) return; // Pivot using median of 3 approach T pivot = getMedian(left, right); int partition = partition(left, right, pivot); // Recursively, calls the quicksort with the different left and right parameters of the sub-array quickSort(0, partition-1); quickSort(partition+1, right); } // This method is used to partition the given array and returns the integer which points to the sorted pivot index private int partition(int left,int right,T pivot){ int leftCursor = left-1; int rightCursor = right; while(leftCursor < rightCursor){ while(((Comparable<T>)a[++leftCursor]).compareTo(pivot) < 0); while(rightCursor > 0 && ((Comparable<T>)a[--rightCursor]).compareTo(pivot) > 0); if(leftCursor >= rightCursor){ break; }else{ swap(leftCursor, rightCursor); } } swap(leftCursor, right); return leftCursor; } public T getMedian(int left,int right){ int center = (left+right)/2; if(((Comparable<T>)a[left]).compareTo(a[center]) > 0) swap(left,center); if(((Comparable<T>)a[left]).compareTo(a[right]) > 0) swap(left, right); if(((Comparable<T>)a[center]).compareTo(a[right]) > 0) swap(center, right); swap(center, right); return a[right]; } // This method is used to swap the values between the two given index public void swap(int left,int right){ T temp = a[left]; a[left] = a[right]; a[right] = temp; } public void printArray(){ for(T i : a){ System.out.println(i+" "); } } }
- If we run the above code, we will have the following results:
Employee Code: 5658, Name:John Carter Employee Code: 7412, Name:Mary Carter Employee Code: 1158, Name:Alex Lumb Employee Code: 1254, Name:David Jhonson Employee Code: 4587, Name:Shaun Smith Employee Code: 1158, Name:Alex Lumb Employee Code: 1254, Name:David Jhonson Employee Code: 4587, Name:Shaun Smith Employee Code: 5658, Name:John Carter Employee Code: 7412, Name:Mary Carter
In the above example, we have created a generic class which can be used to sort any objects of any type, using Quicksort. Any class T which implements the Comparable
interface can be used to sort using the above class. It performs the same functionality as shown in the previous example. The only difference is that this class is generic and it accepts any class T in its generic parameter which implements the Comparable
interface.
In the previous code, we created the Employee
class which implements Comparable
interface and provides its own rule on how to compare its objects. The above class creates an array of the Employee
class and assignes it to the array a
. We print to show the current unsorted array of objects. Then, we called the sort()
method which sorted the array of Employee
type.
Please note that the comparison of the objects of the type Employee
, is done by the rule defined in the compareTo()
method in the Employee
class i.e. on the basis of the employeeCode
property of the class.
5. Download the source code
This was an example on Quicksort algorithm in Java. You can download the source code of this example from here: QuickSortExample.zip
Related Whitepaper:Java Essential TrainingAuthor David Gassner explores Java SE (Standard Edition), the language used to build mobile apps for Android devices, enterprise server applications, and more! The course demonstrates how to install both Java and the Eclipse IDE and dives into the particulars of programming. The course also explains the fundamentals of Java, from creating simple variables, assigning values, and declaring methods to working with strings, arrays, and subclasses; reading and writing to text files; and implementing object oriented programming concepts. Exercise files are included with the course. |