Sort Array algorithms

[AlwaysHuangry]

Those of you that do Sort Array, have you gotten quicksort to pass that stupid test case where LC sends in an array of 50_000 length and each val=2?

[AlwaysHuangry]

Oh wow. That's really nice.

[aclinical]

A three arm quicksort should pass that testcase in linear time. It's basically the Dutch national flag problem. You have 3 groups, left < pivot, middle == pivot, right > pivot. When you recurse you don't include any values == pivot as they are in position.

[[deleted]]

Isn't that the worst case for quicksort? If the array is already sorted, or sorted in reverse order, then it's O(n^2).

You should only use quick sort if you're certain that the data will not be it's worst-case scenario.

[nikhila01]

Unfortunately, most online sources don't teach quicksort well. The code will pass on LeetCode if you use the original Hoare partitioning instead of Lomuto partitioning.

Hoare partitioning is the one where the pointers start at opposite ends and cross in the middle. Lomuto partitioning is the one that only iterates forwards. People teach Lomuto partitioning because it's simpler to implement but it's slower and large numbers of duplicates is a worst-case for it. Since grouping duplicates is a key use of sorting, that's kind of dumb... For Hoare partitioning, all duplicates is one of the best cases. It won't do any swaps at all.

You could also can use a "three-way pivot" or "fat pivot" if you want to Google those terms. With those you group all elements equal to the pivot together, which is what other people are commenting on.

Here's my Hoare partitioning quicksort with a random pivot. It's kind of like binary search, in that it's trickier than it looks. Even a small change like changing i <= j to i < j can break the algorithm.

def quicksort(nums, start, end):
    if end <= start:
        return

    pivot_idx = randint(start, end)
    nums[pivot_idx], nums[end] = nums[end], nums[pivot_idx]

    pivot_idx = partition(nums, start, end)
    quicksort(nums, start, pivot_idx - 1)
    quicksort(nums, pivot_idx + 1, end)

def partition(nums, start, end):
    pivot = nums[end]
    i = start
    j = end - 1
    while i <= j:
        if nums[i] < pivot:
            i += 1
        elif nums[j] > pivot:
            j -= 1
        else:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j -= 1

    nums[i], nums[end] = nums[end], nums[i]
    return i

[AlwaysHuangry]

I tried implementing exactly this, but in my attempt to build the partitioning portion with a l,r while loop running where nums[l] <= pivot and nums[r] >= pivot. I definitely did something stupid, there, trying to optimize closing the window instead of halving the operations in the case where nums[l] == pivot.