Quicksort in Java

by

Quicksort is an optimized sorting algorithm. It makes use of divide and conquer logic to sort the series. Let us understand:

How Quicksort works (Easy Explanation) :

  1. In quicksort when we are given an array to sort elements then we choose the last element as the pivot element.
  2. Now this pivot element is arranged in such a way that it is placed at its position as it would in case of sorted array.
  3. Also after arranging pivot element all the elements to its left should be smaller than pivot element and all the elements to its right should be greater than pivot element.
  4. Now we have pivot element in its sorted position. So we pass elements to the left of pivot element again to Step 1 to sort the pivot element among them. Similarly array elements to the right are sent to Step 1. This process goes on until we have only single element available and no more pivot element can be chosen.

The array obtained at the end will be sorted.

Take a look at below image to get more clarity on steps:-

Let us take take a look at code:

public class Tech4Humans {
	public static void main(String args[]) 
	{
		int[] arr = { 90, 10, 50, 5, 40 };
		quicksort(arr, 0, arr.length - 1);
		
		System.out.print("Sorted array: ");
		for (int k=0; k < arr.length; k++) {
			System.out.print(arr[k] + " ");
		}
	}

	private static void quicksort(int[] arr, int first, int last) 
	{
		if (first < last) 
		{
			// q is the index where the pivot element is placed after sorting
			int q = partition(arr, first, last);
			quicksort(arr, first, q - 1);
			quicksort(arr, q + 1, last);
		}
	}

	// partition() function is used to place pivot element at its sorted position. partition() function also 
	// places elements smaller than pivot element to left of it and
	// elements greater than pivot element to right of pivot element.
	private static int partition(int[] arr, int first, int last) 
	{
		int x = arr[last];
		int i = first - 1;
		for (int j = first; j < last; j++) 
		{
			if (arr[j] < x)
			{
				i = i + 1;
				int temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
		int temp = arr[i + 1];
		arr[i + 1] = arr[last];
		arr[last] = temp;
		return (i + 1);
	}
}

Output

Sorted array: 5 10 40 50 90

In the above code observe that :

  • quicksort() function is being called recursively to divide the array around pivot element.
  • ‘q‘ is the array index where the pivot element is placed after sorting. It is returned by partition().
  • partition() function is used to place pivot element at its sorted position. partition() function also places elements smaller than pivot element to left of it and elements greater than pivot element to right of pivot element.

Leave a Comment