Back to DSA Course

Quicksort is a sorting algorithm, which is leveraging the divide-and-conquer principle. It has an average O(n log n) complexity and it's one of the most used sorting algorithms, especially for big data volumes.

It's important to remember that Quicksort isn't a stable algorithm. A stable sorting algorithm is an algorithm where the elements with the same values appear in the same order in the sorted output as they appear in the input list.

• We choose an element from the list, called the pivot. We'll use it to divide the list into two sub-lists.
• We reorder all the elements around the pivot – the ones with smaller value are placed before it, and all the elements greater than the pivot after it. After this step, the pivot is in its final position. This is the important partition step.
• We apply the above steps recursively to both sub-lists on the left and right of the pivot.

Let's start coding for quick sort,

package com.praveen.sort;

public class QuickSort {
	public static void main(String[] args) {
		int[] num = { 90, 24, 46, 35, 32 };
		quickSort(num, 0, num.length-1);
		// After sorting
		for (int i : num) {
			System.out.print(i + " ");
		}
	}

	public static void quickSort(int arr[], int begin, int end) {
	    if (begin < end) {
	        int partitionIndex = partition(arr, begin, end);

	        quickSort(arr, begin, partitionIndex-1);
	        quickSort(arr, partitionIndex+1, end);
	    }
	}

	private static int partition(int arr[], int begin, int end) {
	    int pivot = arr[end];
	    int i = (begin-1);

	    for (int j = begin; j < end; j++) {
	        if (arr[j] <= pivot) {
	            i++;

	            int swapTemp = arr[i];
	            arr[i] = arr[j];
	            arr[j] = swapTemp;
	        }
	    }

	    int swapTemp = arr[i+1];
	    arr[i+1] = arr[end];
	    arr[end] = swapTemp;

	    return i+1;
	}
}

Output

24 32 35 46 90