Java Program to Implement Quick Sort

Introduction

Quick Sort is a highly efficient sorting algorithm that follows the divide-and-conquer approach. It works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. This guide will walk you through writing a Java program that implements the Quick Sort algorithm.

Problem Statement

Create a Java program that:

• Prompts the user to enter the size of an array and its elements.
• Sorts the array using the Quick Sort algorithm.
• Displays the sorted array.

Example:

• Input: [10, 7, 8, 9, 1, 5]
• Output: "Sorted array: [1, 5, 7, 8, 9, 10]"

Solution Steps

1. Read the Array Size and Elements: Use the Scanner class to take the size and elements of the array as input from the user.
2. Implement Quick Sort: Use a recursive function to sort the array by partitioning it around a pivot element.
3. Display the Sorted Array: Print the sorted array.

Java Program

// Java Program to Implement Quick Sort // Author: https://www.rameshfadatare.com/ import java.util.Scanner; public class QuickSort { public static void main(String[] args) { // Step 1: Read the size and elements of the array from the user Scanner scanner = new Scanner(System.in); System.out.print("Enter the size of the array: "); int size = scanner.nextInt(); int[] array = new int[size]; System.out.println("Enter the elements of the array:"); for (int i = 0; i < size; i++) { array[i] = scanner.nextInt(); } // Step 2: Sort the array using Quick Sort quickSort(array, 0, size - 1); // Step 3: Display the sorted array System.out.println("Sorted array:"); for (int i = 0; i < size; i++) { System.out.print(array[i] + " "); } } // Method to implement Quick Sort public static void quickSort(int[] array, int low, int high) { if (low < high) { // Step 2.1: Partition the array int pi = partition(array, low, high); // Step 2.2: Recursively sort elements before and after partition quickSort(array, low, pi - 1); quickSort(array, pi + 1, high); } } // Method to partition the array public static int partition(int[] array, int low, int high) { // Step 2.1.1: Choose the pivot element int pivot = array[high]; int i = (low - 1); // Index of smaller element for (int j = low; j < high; j++) { // Step 2.1.2: If the current element is smaller than or equal to the pivot if (array[j] <= pivot) { i++; // Step 2.1.3: Swap array[i] and array[j] int temp = array[i]; array[i] = array[j]; array[j] = temp; } } // Step 2.1.4: Swap array[i + 1] and the pivot element int temp = array[i + 1]; array[i + 1] = array[high]; array[high] = temp; return i + 1; // Return the partitioning index } } 

Explanation

Step 1: Read the Array Size and Elements

• The Scanner class is used to read the size of the array and its elements. The nextInt() method captures the size and each element.

Step 2: Implement Quick Sort

• quickSort Method:

  • This is the recursive method that sorts the array. It first partitions the array around a pivot element and then recursively sorts the sub-arrays on either side of the pivot.

• partition Method:

  • This method chooses the last element of the current sub-array as the pivot.
  • It rearranges the elements in such a way that all elements smaller than the pivot come before it, and all elements greater come after it.
  • It then places the pivot in its correct position and returns the index of the pivot element.

Step 3: Display the Sorted Array

• The sorted array is printed using a for loop.

Output Example

Example 1:

Enter the size of the array: 6 Enter the elements of the array: 10 7 8 9 1 5 Sorted array: 1 5 7 8 9 10 

Example 2:

Enter the size of the array: 5 Enter the elements of the array: 64 25 12 22 11 Sorted array: 11 12 22 25 64 

Conclusion

This Java program demonstrates how to implement the Quick Sort algorithm to sort an array. Quick Sort is known for its efficiency and is widely used in various applications. The program covers key concepts such as recursion, partitioning, and array manipulation, making it a valuable exercise for those learning Java programming.