Log In  

A clone of The Sound of Sorting I made just to test and diagnose my QuickSort algorithm.
It may sound a little ridiculous on web, since the array access sounds tend to get lumped together into far fewer frames.

  • Press z to step
  • Hold z to disable step mode
  • Press x to switch sorting algorithm
  • Use up and down to control the number of entries.
  • Use left and right to control the speed.

Cart #sort_our_ship-1 | 2024-05-27 | Embed ▽ | License: CC4-BY-NC-SA
14

P#148518 2024-05-17 03:02 ( Edited 2024-05-27 01:35)

Oh, btw, here's the quicksort algorithm without all the extra baggage.

-- An implementation of QuickSort which does not allocate new tables.
-- Mutates the provided table.
function sort(arr,key)
    local function insertion_sort(min,max)
        for i = min+1,max do
            for j = i,min+1,-1 do
                local item,other = arr[j],arr[j-1]
                if other[key] <= item[key] then break end
                arr[j],arr[j-1] = other,item
            end
        end
    end

    local function quick_sort(min,max)
        -- This means there's one or none elements in the list.
        -- It literally cannot be unsorted.
        if min >= max then
            return
        end

        -- The pivot will be the median value between the first, last,
        -- and middle elements. This is done to avoid worst case scenarios
        -- where the pivot is already at the boundary between buckets.
        local pivot
        do -- The local variables here can be discarded after pivot selection.
            local pivot_i = flr((max+min)/2)
            pivot = arr[pivot_i][key]

            local first = arr[min][key]
            local last = arr[max][key]

            -- Bubble sort the first, middle, and last elements.
            if first > pivot then
                arr[min],arr[pivot_i] = arr[pivot_i],arr[min]
                first,pivot = pivot,first
            end
            if pivot > last then
                arr[pivot_i],arr[max] = arr[max],arr[pivot_i]
                pivot = last -- last is unused from here on. Doesn't need to be valid.
            end
            if first > pivot then
                arr[min],arr[pivot_i] = arr[pivot_i],arr[min]
                pivot = first -- first is unused from here on. Doesn't need to be valid.
            end
        end

        -- If there's three or fewer elements, it is already sorted.
        if max-min < 3 then return end

        local low,high = min+1,max-1
        while true do
            -- Find the first high bucket item in the low bucket,
            while low < high and arr[low][key] < pivot do
                low += 1
            end
            -- and the last low bucket item in the high bucket.
            while low < high and arr[high][key] > pivot do
                high -= 1
            end
            -- If they are the same item, we have sorted all elements into the buckets.
            if low >= high then break end

            -- Otherwise, swap the elements, so they are in the correct buckets.
            arr[low],arr[high] = arr[high],arr[low]
            -- We now know those two items are in the correct buckets, so we
            -- don't need to recheck them.
            low += 1
            high -= 1
        end

        -- Sort the low bucket and the high bucket individually.
        -- insertion_sort is better for small buckets.
        local algo = high-min < 8 and insertion_sort or quick_sort
        algo(min,high)
        algo = max-low < 8 and insertion_sort or quick_sort
        algo(low,max)
    end

    -- Sort everything
    local algo = #arr <= 8 and insertion_sort or quick_sort
    algo(1,#arr)

    -- Return the sorted array. Since this function mutates the original,
    -- this is purely for convenience.
    return arr
end

P#148519 2024-05-17 03:06

[Please log in to post a comment]