Quick Sort

PermalinkQuick Sort: Sorting with Partitioning

Table of contents Introduction: What is Quick Sort? How Quick Sort Works: Step-by-Step Example: Quick Sort in Java: Time Complexity of Quick Sort: Space Complexity of Quick Sort: Advantages and Disadvantages:

Advantages:

Disadvantages: Conclusion:

Quick Sort Explained: A Fast and Efficient Sorting Algorithm

Introduction: Sorting is a fundamental operation in computer science, and the choice of sorting algorithm can significantly impact performance. Quick Sort is another powerful and widely used sorting algorithm that employs the divide-and-conquer strategy. In this post, we'll explore how Quick Sort works, analyze its time and space complexity, and provide a Java implementation.

What is Quick Sort? Quick Sort is a divide-and-conquer algorithm that picks an element as a pivot and partitions the given array around the picked pivot.¹ The key idea is to place the pivot element in its correct sorted position and then recursively sort the subarrays before and after the pivot.

How Quick Sort Works:

1. Choose a Pivot: Select a pivot element from the array. There are various strategies for pivot selection (e.g., first element, last element, median).

2. Partition: Rearrange the array so that all elements smaller than the pivot are placed before it, and all elements greater than the pivot are placed after it. Elements equal to the pivot can go either way.

3. Recursion: Recursively apply the above steps to the subarrays before and after the pivot.

Step-by-Step Example: Consider the array: [5, 1, 4, 2, 8]

Let's choose the first element (5) as the pivot.

1. Partition: After partitioning, the array might look like this: [2, 1, 4, 5, 8]. Notice that all elements smaller than 5 are before it, and all larger elements are after. 5 is now in its sorted position.

2. Recursion:

   • Recursively sort the left subarray: [2, 1, 4]

   • Recursively sort the right subarray: [8] (already sorted)

The partitioning process continues recursively until the entire array is sorted.

Quick Sort in Java:

Java

package Sorting;

import java.util.Arrays;

public class QuickSort {

    public static void swap(int nums[],int i,int j)
    {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    public static int partition(int nums[],int low,int high)
    {
        int i=low;
        int j=high;
        int pivot = nums[low];

        while(i<j)
        {
            while(nums[i]<=pivot && i<=high-1)
            {
                i++;
            }
            while(nums[j]>pivot && j>=low+1)
            {
                j--;
            }
            if(i<j)
            {
            swap(nums,i,j);
            }
        }

        swap(nums,low,j);//Pivot found
        return j;
    }

    public static void quickSortHelper(int nums[],int low,int high)
    {
        if(low<high)
        {
            int pIndex = partition(nums,low,high);
            quickSortHelper(nums,low,pIndex-1);
            quickSortHelper(nums,pIndex+1,high);
        }
    }

    public static int[] quickSort(int nums[])
    {
        int n = nums.length;
        quickSortHelper(nums,0,n-1);
        return nums;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        int nums[] = { 37,25,14,7, 15, 10, 12, 4 ,5};
        System.out.println(Arrays.toString(quickSort(nums)));

    }

}

Time Complexity of Quick Sort:

• Best Case: O(n log n) - Occurs when the pivot selection consistently divides the array into roughly equal halves.

• Average Case: O(n log n) - Also occurs when the pivot selection is reasonably good.

• Worst Case: O(n^2) - Occurs when the pivot selection is consistently poor (e.g., always the smallest or largest element), leading to highly unbalanced partitions.

Space Complexity of Quick Sort: Quick Sort is typically an in-place algorithm, meaning it requires minimal extra space. The space complexity is O(log n) in the average case due to the recursive calls. In the worst case, it can be O(n) due to deep recursion.

Advantages and Disadvantages:

Advantages:

• Efficient: O(n log n) average and best-case time complexity makes it very fast for most datasets.

• In-place: Requires minimal extra memory (typically O(log n)).

• Generally Faster: Often performs faster than Merge Sort in practice due to lower constant factors.

Disadvantages:

• Worst-Case Performance: O(n^2) worst-case time complexity can be a concern. Careful pivot selection can mitigate this risk.

• Not Stable: Quick Sort is not a stable sort, meaning it may not preserve the relative order of equal elements.

Conclusion: Quick Sort is a highly efficient and widely used sorting algorithm. Its average-case performance is excellent, and it's often the preferred choice for many applications. While the worst-case scenario is a consideration, proper pivot selection strategies can significantly reduce the likelihood of it occurring. Understanding Quick Sort is a must for any programmer working with sorting algorithms.