Java Program to Implement Quick Sort Algorithm

Introduction

Quick Sort is a highly efficient sorting algorithm and is based on partitioning an array into smaller sub-arrays. A 'pivot' element is chosen from the array and positioning is arranged such that all elements smaller than the pivot are on the left side of the pivot and all elements larger are on the right side. The process is then repeated for the sub-arrays, which efficiently leads to the whole array being sorted. Quick Sort is particularly admired for its performance, being capable of sorting large datasets rapidly.

In this article, you will learn how to implement the Quick Sort algorithm in Java. Explore detailed examples that demonstrate how to apply Quick Sort to an array of integers. Understand key steps, such as choosing a pivot and partitioning the array, which are crucial for grasping the algorithm's mechanics.

Understanding Quick Sort

Quick Sort utilizes a divide-and-conquer approach to sorting arrays. Here’s how you achieve this in steps:

1. Select a 'pivot' element from the array.
2. Partition the array such that elements less than the pivot come before it and elements greater come after it.
3. Recursively apply the above steps to the sub-arrays formed by partitioning.

Choosing a Pivot

Choosing an effective pivot is crucial for optimizing Quick Sort's efficiency. Common strategies include:

• Choosing the first element as the pivot.
• Choosing the last element as the pivot.
• Choosing a random element as the pivot.
• Choosing the median as the pivot.

For simplicity, the examples in this article will use the last element of the array as the pivot.

Java Implementation of Quick Sort

This section demonstrates how to implement the Quick Sort algorithm in Java. The implementation is split into two main parts: the recursion logic and the partitioning logic.

The QuickSort Method

The main function that implements the Quick Sort algorithm involves a recursive method that calls itself for sub-arrays. Here's how you can code it.

1. Define the quickSort function that takes three parameters: the array, the starting index, and the ending index.

   java Copy

   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);
       }
   }
   

   This function checks if there are at least two elements to sort (i.e., begin < end). It then finds the partition index where the array needs to be divided, and recursively sorts the sub-arrays.

The Partition Logic

Partitioning is pivotal in the Quick Sort algorithm. This subroutine rearranges the array and returns the index of the pivot correctly placed.

1. Implement the partition function.

   java Copy

   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;
   }
   

   The partition method iterates over each element, checking if it should be on the left (less than pivot) or right (greater than pivot) of the pivot, effectively rearranging the elements around the pivot.

Putting it All Together

Here's a complete example combining both the Quick Sort method and the partition logic in a single Java program.

1. Complete Quick Sort program with a test case.

   java Copy

   public class QuickSortExample {
       public static void main(String args[]) {
           int arr[] = {10, 7, 8, 9, 1, 5};
           int n = arr.length;
   
           QuickSortExample qse = new QuickSortExample();
           qse.quickSort(arr, 0, n-1);
   
           System.out.println("sorted array");
           for(int i=0; i<n; i++) {
               System.out.print(arr[i] + " ");
           }
       }
   
       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);
           }
       }
   
       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;
       }
   }
   

   Run this program to sort an array and observe the effectiveness of the Quick Sort algorithm.

Conclusion

Quick Sort is a fast, recursive, divide-and-conquer approach to sorting arrays in Java which you now understand and can implement. This algorithm's efficiency lies in its ability to sort data quickly, making it suitable for large datasets. By mastering Quick Sort, you significantly enhance your ability to tackle problems requiring sorting solutions in programming competitions and real-world applications. Remember the importance of the pivot’s position and the partitioning process to make the most out of this algorithm