14

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 | 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