DSA Quicksort

Welcome to TheCodingCollege.com, your ultimate resource for coding and programming tutorials! Today, we delve into Quicksort, one of the most efficient and widely-used sorting algorithms in Data Structures and Algorithms (DSA).

What is Quicksort?

Quicksort is a divide-and-conquer algorithm that sorts an array by selecting a pivot element and partitioning the other elements into two subarrays:

1. Elements smaller than the pivot.
2. Elements larger than the pivot.

The process is then recursively applied to the subarrays.

How Does Quicksort Work?

1. Choose a Pivot: Select a pivot element from the array.
2. Partition the Array: Rearrange the array so that all elements less than the pivot are on its left, and all elements greater are on its right.
3. Recursive Sorting: Apply the same process to the subarrays.
4. Base Case: Subarrays with fewer than two elements are already sorted.

Steps in Quicksort

Let’s sort the array [10, 7, 8, 9, 1, 5] using Quicksort:

Initial Array: [10, 7, 8, 9, 1, 5].

Step 1: Choose a pivot (e.g., 5).

Partition:

• Move elements smaller than 5 to the left.
• Move elements larger than 5 to the right.
• Result: [1, 5, 10, 7, 8, 9].

Step 2: Apply Quicksort to subarrays [1] and [10, 7, 8, 9].

Step 3: Repeat until all subarrays are sorted.

Final Sorted Array: [1, 5, 7, 8, 9, 10].

Quicksort Code Implementation

Python Code:

def partition(arr, low, high):
    pivot = arr[high]  # Choose the last element as the pivot
    i = low - 1        # Index of the smaller element

    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]  # Swap

    arr[i + 1], arr[high] = arr[high], arr[i + 1]  # Place pivot in correct position
    return i + 1

def quicksort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)  # Partitioning index
        quicksort(arr, low, pi - 1)    # Sort elements before partition
        quicksort(arr, pi + 1, high)   # Sort elements after partition

# Example usage
array = [10, 7, 8, 9, 1, 5]
quicksort(array, 0, len(array) - 1)
print("Sorted Array:", array)

Output:

Sorted Array: [1, 5, 7, 8, 9, 10]

Java Code:

class QuickSort {
    static int partition(int arr[], int low, int high) {
        int pivot = arr[high];
        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }

    static void quicksort(int arr[], int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);

            quicksort(arr, low, pi - 1);
            quicksort(arr, pi + 1, high);
        }
    }

    public static void main(String args[]) {
        int arr[] = {10, 7, 8, 9, 1, 5};
        quicksort(arr, 0, arr.length - 1);
        System.out.print("Sorted Array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Time Complexity of Quicksort

Space Complexity: O(log⁡n)O(\log n) (due to recursive calls).

Advantages and Disadvantages of Quicksort

Advantages

1. Fast for Large Datasets: Average time complexity of O(nlog⁡n)O(n \log n).
2. In-Place Sorting: Requires minimal extra space.
3. Widely Used: Powers many library sorting functions.

Disadvantages

1. Worst Case: Time complexity can degrade to O(n2)O(n^2) with poor pivot choices.
2. Not Stable: Relative order of equal elements may not be preserved.

Applications of Quicksort

1. Sorting Large Datasets: Commonly used in system libraries and databases.
2. Divide-and-Conquer Approach: Ideal for problems that can be divided into smaller, independent tasks.

Comparison with Other Sorting Algorithms

Conclusion

Quicksort is a highly efficient and versatile sorting algorithm, making it a favorite among developers and researchers. While its performance depends on the pivot choice, its average-case efficiency and in-place nature make it ideal for large datasets.

Explore more sorting algorithms and DSA tutorials at TheCodingCollege.com and take your coding skills to the next level!