Quick Sort Algorithm

Quicksort is a very fast sorting algorithm, hence its name. The algorithm works recursively according to the divide and conquer principle. First, a so-called pivot element is determined from the list to be sorted. This element can be chosen arbitrarily.

The pivot element separates the list into 2 partial lists. This creates a “left” and a “right” list.

All elements smaller than the pivot element move to the left list, the larger ones to the right list. If an element has the same size as the pivot element, it is randomly distributed in one of the two lists. For this reason, Quicksort is not a stable sorting algorithm.

A new pivot element is determined from each partial list and the process is repeated.

• Divide-and-conquer approach
• complex divide-and-conquer step, simple merge step
• Sets with one or no element are sorted otherwise
  – division of the problem into two subsets, where all elements of one subset are smaller than all elements of the other subset
  – recursive call of the algorithm for both subsets
• Connection of the partial results are implicitly given, since sorting of the subsets is carried out in-place
• Splitting into subsets
  – choice of a key / pivot element
  – Elements that are smaller than the pivot element are assigned to the left subset
  – Elements that are larger than the pivot element are assigned to the right subset

Code Example

import java.util.Scanner;

class QuickSortAlgorithm {

	private static void sortingAlgorithm() {
		Scanner scan = new Scanner(System.in);
		int i = 0;

		System.out.println("How many numbers do you want to sort? ");
		int quantity = scan.nextInt();
		int array[] = new int[quantity];

		while (i < quantity) {
			System.out.println("Please enter the next number: ");
			int value = scan.nextInt();
			array[i] = value;
			i++;
		}

		scan.close();

		System.out.println("\nArray to be sorted:");
		printArray(array, quantity);
		System.out.println("\nGradual sorting:");
		sort(array);
		System.out.println("Sorted array:");
		printArray(array, quantity);
	}

	private static void sort(int[] inputArr) {
		int length;

		if (inputArr == null || inputArr.length == 0) {
			return;
		}
		length = inputArr.length;
		quickSort(inputArr, 0, length - 1);
	}

	private static void quickSort(int array[], int indexLow, int indexHigh) {
		int i = indexLow;
		int j = indexHigh;
		int pivot = array[indexLow + (indexHigh - indexLow) / 2];
		while (i <= j) {
			while (array[i] < pivot) {
				i++;
			}
			while (array[j] > pivot) {
				j--;
			}
			if (i <= j) {
				swapElements(array, i, j);
				i++;
				j--;
			}
		}
		// call quickSort() method recursively
		if (indexLow < j)
			quickSort(array, indexLow, j);
		if (i < indexHigh)
			quickSort(array, i, indexHigh);
	}

	private static void swapElements(int array[], int i, int j) {
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}

	private static void printArray(int array[], int length) {
		for (int i = 0; i < length; i++) {
			System.out.print(array[i] + " ");
		}
	}

	public static void main(String[] args) {
		sortingAlgorithm();
	}
}

Output

How many numbers do you want to sort? 
7
Please enter the next number: 
2
Please enter the next number: 
8
Please enter the next number: 
4
Please enter the next number: 
1
Please enter the next number: 
9
Please enter the next number: 
4
Please enter the next number: 
6

Array to be sorted:
2 8 4 1 9 4 6 
Gradual sorting:
Sorted array:
1 2 4 4 6 8 9

Step-by-Step Visual Walkthrough

Assume the user inputs:
[38, 27, 43, 3, 9, 82, 10]

📌 Step 1: User Input

The Scanner collects input from the user:

User enters: 38, 27, 43, 3, 9, 82, 10  
Array becomes: [38, 27, 43, 3, 9, 82, 10]

⚡ Step 2: QuickSort Begins

Initial array:

[38, 27, 43, 3, 9, 82, 10]
low = 0, high = 6 → pivot = array[3] = 3

➡ Partitioning Step:

Move i and j inward:

• array[i] = 38 > 3
• array[j] = 10 > 3
• …
• Eventually i = 0, j = 3, and array[0] and array[3] are swapped.

After swap:

[3, 27, 43, 38, 9, 82, 10]

🔁 Step 3: Recursion on Left and Right Partitions

Left partition: low=0, high=2

[3, 27, 43]
pivot = 27
→ compare and swap if needed → no changes

Right partition: low=4, high=6

[9, 82, 10]
pivot = 82
→ all values < 82 → no swaps needed

Eventually:

[3, 9, 10, 27, 38, 43, 82]

🧠 Key Concepts Visually

🔄 Partitioning

Initial:
[38, 27, 43, 3, 9, 82, 10]
         ↑pivot (3)

Swapping:
[3, 27, 43, 38, 9, 82, 10]

🧬 Recursive Breakdown

[3, 27, 43, 38, 9, 82, 10]  
↓  
→ Sort left part: [3, 27, 43]  
→ Sort right part: [38, 9, 82, 10]  
↓  
→ Sort recursively until each subarray is of size 1 or 0

✅ Final Sorted Output

[3, 9, 10, 27, 38, 43, 82]

📚 Recap of Flow

1. User inputs an array.
2. QuickSort selects a pivot (middle element).
3. Partitions array into values < pivot and > pivot.
4. Recursively applies this to left and right parts.
5. Output is sorted array.