Quick Sort Algorithm

Sorting is a fundamental operation in computer science, and efficient sorting algorithms are essential for a wide range of applications. One such algorithm is Quick Sort. In this article, we'll delve into Quick Sort in Java, understanding its concept, implementation, and its efficiency. We'll provide a comprehensive Java program showcasing Quick Sort, along with explanations and the output of the code.

What is Quick Sort?

Quick Sort is a popular and highly efficient sorting algorithm that falls under the category of comparison-based sorting techniques. It was developed by Tony Hoare in 1960. Quick Sort is known for its remarkable speed and ability to handle large datasets efficiently. It is an example of a divide-and-conquer algorithm.

Key Characteristics of Quick Sort

Efficiency: Quick Sort is an efficient and effective sorting algorithm with an average time complexity of O(n log n) and a worst-case time complexity of O(n^2), which can be avoided with appropriate pivot selection strategies.
In-Place Sorting: Quick Sort sorts the elements within the original array, making it an in-place sorting algorithm. It does not require additional memory for sorting.
Unstable Sorting: Like most comparison-based sorting algorithms, Quick Sort may not maintain the relative order of elements with equal keys.

How Quick Sort Works

Quick Sort operates 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.

The Quick Sort Process

Pivot Selection: Choose a 'pivot' element from the array. The choice of the pivot can affect the efficiency of the algorithm.
Partitioning: Rearrange the elements in the array so that all elements less than the pivot come before all elements greater than the pivot. The pivot itself is in its final sorted position.
Recursion: Recursively apply Quick Sort to the sub-arrays of elements less than and greater than the pivot.
Combine: The sorted sub-arrays are combined to produce the final sorted array.

Java Code

import java.util.Arrays;

public class QuickSort {
   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 elements before and after the pivot
           quickSort(array, low, pivotIndex - 1);
           quickSort(array, pivotIndex + 1, high);
       }
   }

   private static int partition(int[] array, int low, int high) {
       int pivot = array[high];
       int i = (low - 1);

       for (int j = low; j < high; j++) {
           if (array[j] < pivot) {
               i++;
               // Swap array[i] and array[j]
               int temp = array[i];
               array[i] = array[j];
               array[j] = temp;
           }
       }

       // Swap array[i+1] and array[high] (or the pivot)
       int temp = array[i + 1];
       array[i + 1] = array[high];
       array[high] = temp;

       return i + 1;
   }

   public static void main(String[] args) {
       int[] array = {12, 11, 13, 5, 6, 7};
       System.out.println("Original Array: " + Arrays.toString(array));

       quickSort(array, 0, array.length - 1);

       System.out.println("Sorted Array: " + Arrays.toString(array));
   }
}

Output


Original Array: [12, 11, 13, 5, 6, 7]
Sorted Array: [5, 6, 7, 11, 12, 13]

Explanation of the Code

The quickSort method is the main entry point for Quick Sort. It takes the array, the low index, and the high index as parameters.

In the partition method, we select the pivot (in this case, the last element) and partition the array such that elements smaller than the pivot are on the left, and elements greater than the pivot are on the right. The pivot is then placed in its final sorted position.

The quickSort method is recursively called on the sub-arrays to sort them.

Summary

Quick Sort is a highly efficient and widely used sorting algorithm due to its speed and suitability for large datasets. Understanding Quick Sort and its implementation in Java can be valuable for solving sorting problems efficiently in various applications.

Dislike

Thanks for feedback.