Core Java

# Quicksort Java algorithm – Code Example

In this article, we will discuss the implementation of Quicksort Java algorithm. Quicksort is the most widely used sorting algorithm. Quick sort is faster than most other 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 Quick sort works on an algorithmic level, with some simple examples. Finally, we will build our implementation in Java and discuss its performance.

You can also check this tutorial in the following video:

## 1. The Quicksort Java Algorithm

Quick sort works recursively in order to sort a given array. These are the three basic steps of the Quicksort algorithm:

1. Partition the array into left and right sub-arrays, 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 cursors move towards each other. If the left cursor finds an item that 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 backward, 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 algorithm goes on until finally all items are sorted.

The pivot value is the value that 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 rightmost item of the array as a pivot value and attempt to create the first version of our Java implementation.

QuicksortExample.java

 0102030405060708091011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889 `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

If we run the above code, we will have the following results:

 12 `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 rightmost 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` will 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 in the same position or a position greater than the rightCursor. When this condition evaluates to false, it means that the cursors have 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 the 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 `partition-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, quick sort operates in O(nlog n) time. But there are some cases when its performance degrades to O(n2). The problem lies in the selection of the pivot. In the above example, we choose the pivot randomly (the rightmost item of the array). The pivot should be the median of the items to be sorted. So, half of the items in the array should be smaller than the pivot, and the rest should be larger than the pivot. This would result in two equally sized sub-arrays. This is the best situation for the Quicksort algorithm, where it runs at O(nlogn). Having one large and one small sub-array results in less efficiency.

## 2. Median of 3 Partitioning

Regarding the quicksort algorithm, 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

 001002003004005006007008009010011012013014015016017018019020021022023024025026027028029030031032033034035036037038039040041042043044045046047048049050051052053054055056057058059060061062063064065066067068069070071072073074075076077078079080081082083084085086087088089090091092093094095096097098099100101102103104105 `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

If we run the above code, we will have the following results:

 12 `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 approach 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 also to put the three items in their sorted place in the array. Let us look at `getMedian()` 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. In 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. Quick sort 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

 01020304050607080910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394 `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)a[++leftCursor]).compareTo(pivot) < ``0``);``        ``while``(rightCursor > ``0` `&& ((Comparable)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)a[left]).compareTo(a[center]) > ``0``)``            ``swap(left,center);``        ` `        ``if``(((Comparable)a[left]).compareTo(a[right]) > ``0``)``            ``swap(left, right);``        ` `        ``if``(((Comparable)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:

 12 `X E C A ``A C E X `

In the above example, we sorted an array of `Strings`, using the quicksort. The `String` class implements the `Comparable` interface and overrides the `compareTo()` method. We used the `compareTo()` method to compare the Strings. We downcasted the String to the `Comparable` type and 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 `String` is maintained alphabetically from A – Z and then from a – z. The rest of the code works the 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 that 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 the basis of their `employeeCode` using the quick sort.

Employee.java

 01020304050607080910111213141516171819202122232425262728293031323334353637383940414243444546474849 `package` `com.javacodegeeks.entity;` `public` `class` `Employee ``implements` `Comparable{` `    ``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 created an `Employee` class that implements the `Comparable` interface and overrides the `compareTo()` method. The comparison between the `Employee` objects are 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

 001002003004005006007008009010011012013014015016017018019020021022023024025026027028029030031032033034035036037038039040041042043044045046047048049050051052053054055056057058059060061062063064065066067068069070071072073074075076077078079080081082083084085086087088089090091092093094095096097098099100101102103104105106107108109110111 `package` `com.javacodegeeks.sorting.quicksort;` `import` `com.javacodegeeks.entity.Employee;` `public` `class` `QuicksortObjectExample> {` `    ``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;``        ` `        ``QuicksortObjectExampleex = ``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)a[++leftCursor]).compareTo(pivot) < ``0``);``        ``while``(rightCursor > ``0` `&& ((Comparable)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)a[left]).compareTo(a[center]) > ``0``)``            ``swap(left,center);``        ` `        ``if``(((Comparable)a[left]).compareTo(a[right]) > ``0``)``            ``swap(left, right);``        ` `        ``if``(((Comparable)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:

 0102030405060708091011 `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 that can be used to sort any objects of any type, using quick sort. Any class T which implements the `Comparable` interface can be used. 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 assigns 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.

## 4. Complexity and comparison with other sorting techniques

As we noticed earlier, the Quicksort algorithm works well when the pivot is in the middle. The best case is O(nlogn) and the worst case would be O(n2). Let us now check how it fares against the other sorting techniques. Comparison is usually done based on time and space complexity.

1. Bubble Sort: This simplest sorting technique works by iterating through the array and comparing each element. The complexity in best and worst cases is O(n2).
2. Selection Sort: In this technique, elements are selected and placed in sorted order. Similar to Bubble sort, the best and worst-case complexity is O(n2).
3. Insertion Sort: In this technique, each element of the array is inserted in the proper position. The best case would be when the array is already sorted. The best case would take O(n) and the worst case would be O(n2). This is best suitable when we have a small array to sort.
4. Quick Sort: Quick Sort, as we saw, would take O(nlogn) for the best case when the right pivot is chosen. The worst case is when the array is already sorted or reverse sorted. The complexity in such a scenario would be O(n2). This is an in-place sorting mechanism and hence is space-efficient.
5. Merge Sort: Like Quick Sort, this is also a divide and conquer recursive mechanism. The best, worst and average case for this mechanism is O(nlogn). But the sorting doesn’t happen in-place and hence is not space-efficient.
6. Heap Sort: This in-place sorting mechanism has best, worst and average complexity as O(nlogn).

This was an example on Quicksort algorithm in Java.

You can download the source code of this example from here: Quicksort Java algorithm – Code Example

Last updated on Feb. 12th, 2020

### Rohit Joshi

Rohit Joshi works as a Software Engineer in the Consumer Product Sector. He is a Sun Certified Java Programmer. He had worked in projects related to different domains. He is also involved in system analysis and system designing. He mainly works in Core Java and J2EE technologies but also have good experience in front-end technologies like Javascript and Jquery.
Subscribe
Notify of This site uses Akismet to reduce spam. Learn how your comment data is processed.

Inline Feedbacks Stylianos
4 years ago

Hey, thank you very much for your help, just some debugging for one of the parts. In the “2. Median of 3 Partitioning” approach you are making a mistake. On line 44 “quickSort(0, partition-1);” you should actually be doing “quickSort(left, partition-1);” because as it stands you are always trying to sort from the beginning of the array and makes it really really wrong. Once that is fixed it runs properly again though, so you should consider fixing it for any people looking at your code in the future. 