Java Sorting Algorithms: Quick Sort



Welcome back to this overview about the Java world! Today, we are going to talk about a renowned sorting algorithm: the Quick Sort.

The Quick Sort is not very suitable for educational purposes because its implementation may not be trivial, but at the performance level it offers some advantages that are not indifferent, unlike the previously trated Bubble Sort.

Let's try to understand better what is Quick Sort.

First of all, let's see an image that gives us an idea of how the algorithm works.

QuickSortScheme

Foundamental features and description

The Quick Sort is one of the most used algorithms, expecially when huge amounts of data have to be treated. Just like some other algorithms, it is part of the Divide and Conquer family.

It means that the processing is not done on the entire data collection, but it is recursively done on finite subsets of the collection. This feature makes the sorting operations lighter from the moment that the values that have to be compared are two at most.

Let's remember that the Quick Sort is a stable and in-place algorithm. Generally no algorithm is stable, but it can be made stable using indexes as meter of comparison.

These are the main steps of the algorithm.

If the collection is composed of zero or one element, then it is sorted. Otherwise the following steps are performed:

  1. A pivot is chosen;
  2. The elements of the array are divided into two parts: the one of the elements before the pivot and the one of the elements after the pivot;
  3. The elements are sorted recursively repeating the 1 and 2 steps;

Implementation

import java.util.*;
public class QuickSort 
{ 
/* 
This function takes the last element as pivot,
place the pivot element in its right position
in the sorted array. It also puts every element smaller than the pivot 
on the left and every element bigger than the pivot on the right.
*/
private static int partition(int arr[], int low, int high) 
{ 
int pivot = arr[high]; 
int index = (low-1); // index of the smaller element. -1 at the beginning
for (int j=low; j<high; j++) 
{ 
// if the current element is smaller than pivot
if (arr[j] < pivot) 
{ 
index++; 
// swap arr[index] and arr[j] 
int temp = arr[index]; 
arr[index] = arr[j]; 
arr[j] = temp; 
} 
} 
// swap arr[index+1] and arr[high] (or pivot) 
int temp = arr[index+1]; 
arr[index+1] = arr[high]; 
arr[high] = temp; 
return index+1; 
} 
/* The main function that implements QuickSort() 
arr[] --> array to be sorted, 
low --> starting index, 
high --> ending index */
public static void sort(int arr[], int low, int high) 
{ 
if (low < high) 
{ 
/* pi is the partitioning index, arr[pi] is now in the right place */
int pi = partition(arr, low, high); 
// Recursively order the elements before
// partition and after partition 
sort(arr, low, pi-1); 
sort(arr, pi+1, high); 
} 
} 
// Driver program.
public static void main(String args[]) 
{ 
int arr[] = {10, 7, 8, 9, 1, 5}; 
int n = arr.length; 
QuickSort.sort(arr, 0, n-1); 
System.out.println("sorted array"); 
System.out.println(Arrays.toString(arr)); 
} 
} 

Let's understand the code

The most important element is the choice of the pivot. The ideal pivot should be the medium element of the collection but it is too difficult to find in an unsorted collection. The choices can be different. The first element, the last element, the middle element or a random element can be chosen as pivot.

The main method is partition that takes as parameters the collection to sort, that is an array of integer numbers, and the two extremes of the array, low and high.

In this method every swapping operation is done. This is the method that implements the majority of the algorithm.

The method's body contains simply some swapping operations done only under certain conditions. The very easy principle is the one that exchanging two sorted elements is useless, so the current element j is compared to the pivot.

The indexes have the following meanings:

  • index stands for the minimum element that has been examined;
  • j is the current element;

The sort method is the wrapper for partition. The control on low and high is performed in order to verify that they "make sense" and that situations where low=2 and high=1 don't occurr since inconsistent situations can happen.

The partition index is calculated.

At the end we have the main method, where the array to sort is created. Then the sort method is called on the array with 0 and n-1 as indexes (where n is the array's length).

Must be precised that I chose to make the sort method static. I decided to implement it as a static method because I imagined the code presented above as a part of a bigger class that implements more than one algorithm. Since sort is static, partition must be static.

A non-static method could have been implemented and the effect would have been the same.

Clearly, just like the majority of the situations that happen in Computer Science, there are many different variations of the implementation of the Quick Sort. Every variant has the same final result. The implementation details change.

Hints about complexity

The time taken from the Quick Sort can be expressed as:

T(n) = T(k) + T(n-k-1) + theta(n)

The first two terms represent the two recursive calls and k stands for the element "smaller" than the pivot. The effective time depends on the pivot choice. Let's look at some particular cases:

Worst case: 

T(n) = T(n-1) + theta(n)

It happens when the smallest or the biggest element is chosen as pivot.

The complexity can be written as theta(n2). Notice the exponential growth.

Best case:

T(n) = 2T(n/2) + theta(n)

The complexity can be written as  theta(nLogn).

Average case:

T(n) = T(n/9) + T(9n/10) + theta(n)

In order to make an accurate analysis of the complexity in the average case we should calculate every possible permutation of the elements of the collection and it is not easy. We can have an idea of the complexity considering the case where partition puts O(n/9) elements in a subset and O(9n/10) in the other subset.

The complexity can be written as   theta(nLogn) also in this case.

Curiosity: what is three-way-quick-sort?

Il three-way-quick-sort è una versione del Quick Sort dove la collezione da ordinare viene divisa così come segue:

The three-way-quick-sort is a version of the Quick Sort where the array to sort is divided as shown below: 

  • array[low...i] is the subset of the elements smaller than the pivot;
  • array[i...j-1] is the subset of the element equals to the pivot;
  • array[j...high] is the subset of the element bigger than the pivot;

E' evidente che questa versione sia conveniente solo quando ci sono diversi elementi ridondanti nella collezione. In caso contrario sarebbe priva di senso.

Clearly this version has to be used only if there are many redundant element in the collection. In the other case it would not make any sense.

 
by Alessio Mungelli Date: 14-12-2019 java jdk source code explanation tutorial educational quick sort sortingmethod developing developers hits : 5861  
 
Alessio Mungelli

Alessio Mungelli

Computer Science student at UniTo (University of Turin), Network specializtion, blogger and writer. I am a kind of expert in Java desktop developement with interests in AI and web developement. Unix lover (but not Windows hater). I am interested in Linux scripting. I am very inquisitive and I love learning new stuffs.

 
 
 

Related Posts

Difference between arrow and normal functions in JavaScript

In this tutorial we are going to see how arrow functions differ from normal JavaScript functions. We will also see when you should use one and when you should use…

JavaScript Arrow functions: What they are and how to use them

In this article we are going to see what they are and how to use JavaScript Arrow Functions, a new feature introduced with the ES6 standard (ECMAScript 6). What are Arrow…

How to insert an element into an array with JavaScript

In this brief tutorial you will learn how to insert one or more elements into an array with JavaScript. For this we will use the splice function. The splice function will not…

What is the difference between primitives types and objects in JavaScript?

In this short tutorial we are going to look at the differences between primitive types and objects in JavaScript. To start with, we're going to look at what primitive types…

How to get DOM elements with JavaScript

When you access any element of the DOM, it is usual to save it in a variable. This is something that at first might seem very simple, but if you…

How to reverse an array in JavaScript

In this tutorial we are going to see how you can change the order of the elements of an array so that they are inverted. You could use a loop…

How synchronize the scroll of two divs with JavaScript

In case you have two divs of different sizes you may sometimes want to scroll both at the same time but at different speeds depending on their size. For example,…

How to use the codePointAt method in JavaScript

The JavaScript codePointAt method has more or less the same function as the charCodeAt method, used to get the 16-bit Unicode representation of the character at a certain position in…

How to check if a value is a number in JavaScript

In this short tutorial we are going to look at the various methods that exist to find out if a value is a number in JavaScript.   1. Using the isNaN() function   One…

How to use the charCodeAt method in JavaScript

The charCodeAt method is accepted by strings in JavaScript, returning the 16-bit Unicode code of the character at the position we pass as a parameter to the method. The charCodeAt method…

How to use the charAt method in JavaScript

The charAt method is accepted by strings in JavaScript, returning the position of the character passed as a parameter within the string. If the string contains multiple occurrences of the character…

Strings in JavaScript: What they are and how to use them

In this tutorial we are going to explain what strings are and how they are used in JavaScript. The tutorial is intended for people who are learning to program in…

We use our own and third-party cookies to improve our services, compile statistical information and analyze your browsing habits. This allows us to personalize the content we offer and to show you advertisements related to your preferences. By clicking "Accept all" you agree to the storage of cookies on your device to improve website navigation, analyse traffic and assist our marketing activities. You can also select "System Cookies Only" to accept only the cookies required for the website to function, or you can select the cookies you wish to activate by clicking on "settings".

Accept All Only sistem cookies Configuration