Lindor's sorting algorithm programming contest

[Lindor 376]

Current definition of in-place not strong enough for me.. Some sorting algorithms getting way better reputation than their actual capabilities *cough*mergesort*cough*

I want a sorting algorithm with my own, stronger version of in-place that doesn't take the least amount of time but the least amount of steps. What's a step you ask? And what I mean with stronger version of in-place? Well, let's take a look at the rules:

Programming rules:

• Must be programmed in lua (sry, don't speak any other programming language (yet))
  • Here is a very nice guide to give foundation in lua scripting which I actually just found a couple hours ago:
• the first line of the program must be local steps = 0
• If arr is the array to-be-sorted and a, c, arr[a], arr[c] are any two key-value-pairs, you can do anything you want with a and b, but only so many things with arr[a] and arr[c]:
  • do steps = steps + 1 end if arr[a] < arr[c] then ... end
  • do steps = steps + 1 end if arr[a] > arr[c] then ... end
  • do steps = steps + 1 end if arr[a] <= arr[c] then ... end
  • do steps = steps + 1 end if arr[a] >= arr[c] then ... end
  • do steps = steps + 1 end if arr[a] == arr[c] then ... end
  • do steps = steps + 1 end if arr[a] ~= arr[c] then ... end
  • do arr[a], arr = arr, arr[a] end
• do steps = steps + 1 end has to be executed before each value comparison. Why before and not after? Well, break and return, those might skip a step increase if it's executed after a comparison.
• Key comparisons don't count as step.
• you cannot "rotate" more than two values, e.g. do arr[a], arr[c], arr[d] = arr[c], arr[a], arr[d] end would disqualify as this is technically two steps taken at once
• Can't do anything else with the values
  • no copying to another array, being it direct or indirect
  • no arithmetics
  • no do arr[a] = nil end
  • generally no do arr[a] = b end and also no do b=arr[a] end no matter what b is
• You can't do anything with the steps other than the step increase prior to each comparison
• Don't care if it's stable or not and don't care for amount of time it takes, only number of comparisons count

Submitting rules:

• The amount of steps it took the algorithm determines its worth, if two algorithms compete on the same array, the one with less steps wins
• I don't have the time to test all your algorithms. So to compete, post your lua code, at least one result for the amount of steps it took on an array with >=10000 elements and, if possible, the array. Here are some possible things to test:
  • Worst case Average case
  • Best case
  • already sorted array
  • backwards sorted array
  • nearly sorted array, but not quite
  • completely shuffled array
• What interests me most is Worst case
• All the authors of the algorithms have to be named, taking inspiration is ok but pls no steal.

This is just for fun and I don't really have a time limit for for how long I want to run the competition. I'm gonna post an example right after this. Let's see if you can beat me

 

Edited January 24, 2022 by Lindor
Reason: changed all [b] to [c] because it was screwing up the formatting

[Lindor 376]

Algorithm:

local steps = 0

function copy(a)
    if type(a) ~= "table" then
        do return a end
    end
    local b = {}
    for k, v in pairs(a) do
        b[copy(k)] = copy(v)
    end
    do return b end
end

function sorted(arr, a, b)
    for k = a, b - 1 do
        do steps = steps + 1 end
        if arr[k] > arr[k + 1] then
            do return false end
        end
    end
    do return true end
end

function recursion(arr, a, b)
    if a >= b then
        do return end
    end
    if sorted(arr, a, b) == true then
        do return end
    end
    local k = 0
    while a+k < b-k do
        do steps = steps + 1 end
        if arr[a+k] > arr[b-k] then
            do arr[a+k], arr[b-k] = arr[b-k], arr[a+k] end
        end
        if a+k+1 > b-k-1 then
            do break end
        end
        do k = k + 1 end
    end
    do recursion(arr, a, a+k) end
    do recursion(arr, b-k, b) end
end

function Chanukkasort(arr)
    local x = copy(arr)
    while sorted(x, 1, #x) == false do
        do recursion(x, 1, #x) end
    end
    do return x end
end

Best case: already sorted or backwards sorted, takes floor(#arr/2)+#arr-1 steps

Worst case is completely shuffled array.

Example for worst case Array:

local lol = {}
for I = 1, 10000 do
    lol[I] = math.sin(I)
end

Amount of steps (comparisons) needed for this array: 873491

[chattius 2,291]

When I was at university professors said a good sorting algorithm is one which does the least forward and backward winding of the extern storage tapes, cut in pieces and rule

I think python is using timsort. Timsort is quite fast if you for example have 4 sorted telefon books merged in a single array and want to sort the array into one bigger telefon book. It detects somehow that there are 4 already sorted parts and makes use of it. math.sin(I) must be nasty because it can't have many already sorted parts

[Lindor 376]

Yeah, that was the idea behind using math.sin(I)

Sorting algorithms fascinated me ever since, even before I started programming.

Timsort is pretty cool, for years experts thought introsort would be fastest on real life average scenario and then wabaam here comes timsort
Timsort uses mergesort though, and the thing about mergesort is it's hefty amount of memory usage. If you try to melt two telefone books together by comparing them from smallest to largerst, you can't just shuffle elements around. If there's a smaller element on the right book, you'd need to shift the whole left book by one to the left in order to make room for the element which would blow up runtime to O(n^2).

But I've read somehere that there should be clever implementations out there somewhere for mergesort to work completely in-place and without any memory usage. That's why I was provoking a little bit, was kinda hoping to see one

[chattius 2,291]

The sorting (better reordering) I have to do most often is from finite elements. Calculating the behaviour of produced tools is done by laying a 3d mesh over the tool,

 

 

The resulting matrix has only entries at neighbour points. So a 10000*10000 matrix would take a long time to calculate. But each line has only very few elements. But if they are at bad places it doesn't matter that the most of the matrix are 0's- The 0's are filled up while calculating. The idea is to sort the matrix so that most elements are close to the diagonal.

 

example from:

https://www.iue.tuwien.ac.at/phd/bauer/node55.html

 

[gogoblender 2,931]

heh, waaaaaaay too over me head guys.. just gonna enjoy a very dark 5 49 am in the morning wake up with coffee while reading your math (  ) posts

 

gogo