Feedback on sorting algorithm

Help and Feedback Code Review
#1

I was trying to make a sorting algorithm. My overall goal was to make it as efficient as possible. My question is, is there any way that I can improve this code for maximum efficiency?

function sort(givenTable)
	for i = 1, #givenTable do
		local lowestValueIndex = i
		for j = i+1, #givenTable do
			if givenTable[j] < givenTable[lowestValueIndex] then
				lowestValueIndex = j
			end
		end
		givenTable[i], givenTable[lowestValueIndex] = givenTable[lowestValueIndex], givenTable[i]
	end
	return givenTable
end
5 Likes
#2

Looks like a solid SelectionSort algorithm, which on top of it looks stable to me. I don’t think you could improve your algorithm any further, however MergeSort is faster :wink:

Will explain the concept shortly:
If input array is size 1, return (Keep reading to understand why this is important). Divide array into two subarrays. Sort each of those with MergeSort recursively. You now have two sorted subarrays which you can merge back into one by iterating through both, choosing the smaller element each time and progressing on the respective subarray.

It’s important to immediately exit the function given input is size 1 to prevent a never-terminating recursion.

2 Likes
#3

It seems your algorithm is similar to selection sort, which is one of many algorithms for sorting numbers. There are a lot of sorting algorithms, all with some trade-offs. You can find some of the popular sorting algorithms here with comparisons of different algorithms found further down the page.

Some algorithms perform better than others, but to make your algorithm ‘as efficient as possible’, you will have to analyze the situation you want to use it in. Sometimes you already know a thing or two beforehand so you can take a few shortcuts. For example, will the array contain duplicates?

To answer your original question, yes there are ways to improve your code (or rather, algorithm). I would take a look at the list of algorithms I provided and see if you can find one that best fits your situation.

3 Likes
Help sorting a dictionary by value
#4

Ah I see. I’ll be sure to try it out!

1 Like
#5

I would avoid accessing the array each time and store the value as a temp variable and make the function local. Apart from that it looks good.

#6

Just wrote a HeapSort algorithm in lua for practice. Takes one array and sorts it ascendingly without using any extra arrays. Although unstable, HeapSort is one of the fastest non-randomized sorting algorithms.

function heapSort(a)
	local s, l
	s = function(o, m)
		local l, r = o * 2, o * 2 + 1 if l >= m then return end
		local c = (r >= m or a[l] > a[r]) and l or r
		if a[o] < a[c] then a[o], a[c] = a[c], a[o] s(c, m) end
	end
	l = function(o)
		local c = math.floor(o/2) if c < 1 then return end
		if a[c] < a[o] then a[o], a[c] = a[c], a[o] l(c) end
	end
	for i=1,#a do l(i) end
	for i=#a,1,-1 do a[1], a[i] = a[i], a[1] s(1, i) end
end

One last note: Lua’s table.sort uses QuickSort, which is, in average, a very tiny bit faster than HeapSort. You might just use that as well.

#7

Wow thanks! I once attempted to make a HeapSort algorithm myself too, but Messed up some loops and it ended up crashing studio…

1 Like
#9

Here is a mergesort example I wrote up just now:

local function range( list, low, high )
    local sub = {};
    for i = low, high do
        table.insert( sub, list[i] )
    end
    return sub;
end
        
local MATH_CEIL = math.ceil;

function mergeSort( list )

	-- Base Case: List with length 1 is sorted.
    local len = #list;
    if ( len == 1 ) then
        return;
    end
    
    -- Halfway point between list
    local m = MATH_CEIL( len / 2 );
    local leftTable = range( list, 1, m );
    local rightTable = range( list, m + 1, len );

    -- Recursive Step: Split table until elements reach length 1 and then sort
    -- Guarantees result is sorted for each recursion
    mergeSort( leftTable );
    mergeSort( rightTable );

    local leftTableLength = #leftTable;
    local rightTableLength = #rightTable;

    local leftIndex, rightIndex, tableIndex = 1, 1, 1;

    -- Loop Condition: Terminates when either the left or right tables run out of elements
    while ( leftIndex <= leftTableLength and rightIndex <= rightTableLength ) do
        if ( leftTable[leftIndex] < rightTable[rightIndex] ) then
            list[tableIndex] = leftTable[leftIndex];
            leftIndex = leftIndex + 1;
        else
            list[tableIndex] = rightTable[rightIndex]; 
            rightIndex = rightIndex + 1;
        end
        tableIndex = tableIndex + 1;
    end

    -- If there are left over elements in a table, fill them up
    -- Elements in remaining table are guaranteed to be already sorted
    if ( leftIndex <= leftTableLength ) then
        while ( leftIndex <= leftTableLength ) do
            list[tableIndex] = leftTable[leftIndex];
            leftIndex = leftIndex + 1;
            tableIndex = tableIndex + 1;
        end
    elseif ( rightIndex <= rightTableLength ) then
        while ( rightIndex <= rightTableLength ) do
            list[tableIndex] = rightTable[rightIndex] 
            rightIndex = rightIndex + 1;
            tableIndex = tableIndex + 1;
        end
    end
end


local t = {5,1,2,9,0};
mergeSort( t );
for i,v in pairs( t ) do
	print(v)
end
1 Like
#10

Here is a link to a website that visualizes the majority of scenarios in which certain sorting algorithms are most optimal. Selection sort is actually the slowest (in code speed) of all of the algorithms, so I would consider using another algorithm. Perhaps Merge sort or Heap sort or Insertion sort.

1 Like