Quick Sort in Java

Quick Sort is a highly efficient divide-and-conquer sorting algorithm. It works by selecting a “pivot” element, partitioning the array such that elements smaller than the pivot are placed to its left and elements larger are placed to its right, and then recursively sorting the subarrays.

How Quick Sort Works?

  1. Partitioning:
    • Select a pivot element from the array.
    • Reorganize the array such that:
      • All elements smaller than the pivot are on the left.
      • All elements larger than the pivot are on the right.
    • The pivot element is now in its correct position.
  2. Recursive Sorting:
    • Recursively apply the above steps to the subarrays on the left and right of the pivot.

Steps of the Quick Sort Algorithm:

Input Array: [10, 80, 30, 90, 40, 50, 70]

  1. Choose Pivot: Select the last element as the pivot (e.g., 70).
  2. Partitioning: Rearrange the array:
    • Elements < 70 on the left: [10, 30, 40, 50]
    • Pivot 70: [70]
    • Elements > 70 on the right: [80, 90].
    • The result after partition: [10, 30, 40, 50, 70, 80, 90].
  3. Recursive Steps:
    • Apply Quick Sort to [10, 30, 40, 50] and [80, 90].
  4. Base Case: Stop recursion when subarrays contain a single element.

Quick Sort Program in Java

package com.javacodepoint.sort;

public class QuickSort {

	// Partition method to rearrange the array
	public static int partition(int[] array, int low, int high) {
		int pivot = array[high]; // Pivot is the last element
		int i = low - 1; // Index of smaller element

		for (int j = low; j < high; j++) {
			// If current element is smaller than or equal to pivot
			if (array[j] <= pivot) {
				i++;
				// Swap array[i] and array[j]
				int temp = array[i];
				array[i] = array[j];
				array[j] = temp;
			}
		}

		// Swap the pivot element with the element at i + 1
		int temp = array[i + 1];
		array[i + 1] = array[high];
		array[high] = temp;

		return i + 1; // Return the pivot index
	}

	// Recursive Quick Sort method
	public static void quickSort(int[] array, int low, int high) {
		if (low < high) {
			// Partition the array and get the pivot index
			int pivotIndex = partition(array, low, high);

			// Recursively sort the left and right subarrays
			quickSort(array, low, pivotIndex - 1);
			quickSort(array, pivotIndex + 1, high);
		}
	}

	public static void main(String[] args) {
		int[] numbers = { 10, 80, 30, 90, 40, 50, 70 };

		System.out.println("Original Array:");
		for (int num : numbers) {
			System.out.print(num + " ");
		}

		// Sort the array using Quick Sort
		quickSort(numbers, 0, numbers.length - 1);

		System.out.println("\nSorted Array:");
		for (int num : numbers) {
			System.out.print(num + " ");
		}
	}
}

OUTPUT:

Explanation of Key Steps:

  1. Partitioning:
    • Rearranges the array such that the pivot is in its correct position, and smaller/larger elements are divided around it.
  2. Recursive Calls:
    • Applies Quick Sort to the left and right subarrays of the pivot.
  3. Base Case:
    • Stops recursion when the subarray size is 1 or 0 (already sorted).

Time Complexity

  1. Best Case: O(n log⁡ n) (Balanced partitions).
  2. Average Case: O(n log⁡ n) (Random partitions).
  3. Worst Case: O(n^2) (Unbalanced partitions, e.g., sorted array).

Space Complexity

  • In-place Algorithm: Uses O(log ⁡n) space for recursion stack.

Also Read: Selection Sort | Insertion Sort | Bubble Sort | Merge Sort

Java logical programs list


Java Basic Programs

Java String Programs

Java Programs based on the Collection Framework

Leave a Reply

Your email address will not be published. Required fields are marked *