Quick Sort Variations (3-Way Quick Sort) 🎯

Welcome back to CodeYourCraft! Today, we're diving deep into the world of Quick Sort, one of the most efficient sorting algorithms. But we're not stopping there, we'll explore a variation called 3-Way Quick Sort, which is even more efficient for large datasets. Let's get started! 🎉

What is Quick Sort? 📝

Quick Sort is a divide-and-conquer algorithm. 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, equal to, or greater than the pivot.

python

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

When Quick Sort Fails 💡

Quick Sort is efficient, but it can sometimes lead to a worst-case time complexity of O(n^2) when the input array is already sorted or reverse sorted. This is because the pivot doesn't effectively partition the array, causing recursion to continue unnecessarily.

Enter 3-Way Quick Sort 💡

3-Way Quick Sort is a modification of Quick Sort that addresses the inefficiency of the original algorithm. Instead of just two partitions (less than and greater than the pivot), it creates three partitions:

Elements less than the pivot
Elements equal to the pivot
Elements greater than the pivot

This improves the efficiency of the algorithm, especially for large datasets.

Implementing 3-Way Quick Sort 📝

Here's a Python implementation of 3-Way Quick Sort:

python

def three_way_quick_sort(arr):
    def partition(low, high, pivot):
        i = low - 1
        j = high + 1
        while True:
            i += 1
            while arr[i] < pivot:
                if i == high:
                    break
            j -= 1
            while arr[j] > pivot:
                if j == low:
                    break
            if i >= j:
                return j
            arr[i], arr[j] = arr[j], arr[i]

    def sort_small(low, high):
        if high - low <= 20:
            insertion_sort(low, high)
            return
        pivot = arr[low + (high - low) // 2]
        i = partition(low, high, pivot)
        sort_small(low, i)
        sort_small(i + 1, high)

    sort_small(0, len(arr) - 1)

Advantages of 3-Way Quick Sort 💡

Improved efficiency over Quick Sort, especially for large datasets
Reduced chance of the worst-case time complexity of O(n^2)
Ideal for sorting large datasets in real-world applications

Quiz Time! 🎯

That's all for today! We hope you enjoyed learning about 3-Way Quick Sort. Stay tuned for more lessons on Data Structures and Algorithms here at CodeYourCraft. Happy coding! 🚀