11 replies to this topic

[HPWebcamAble]

Just a few sorting algoritims to make your life easier!

Things you should know first:
- Basic Lua
- Tables ( <-- Major part of this )




There are 2 types of sorting algorithms that I've provided (But many more exist)
Each has advantages and disadvantages in certain situations


I've added a special 'compare' function that lets you decided
how data is compared, it is required for all of the provided sorting
algorithms to work!

compare Function

Spoiler

Note: Strings CAN be compared with '>'
Lua uses lexicographic (Alphabetical) comparison

local function compare(data1,data2)
  return data1 > data2
end

Note 2: This compare function ONLY works with the
insertion sort, the merge sort is slightly
different, I've included the correct one in the corresponding
sections


Obviously this could be achieved without a function,
but only if the data is a string or number.

If you are storing tables, then you will need to
rewrite the 'compare' function to sort the table correctly

For example, pretend you need to display a list of several Minecraft Mods

Spoiler

mods = {
  { name = "ComputerCraft", version = "1.7", mcVersion = "1.7", author = "dan200" },
  { name = "Redpower", version = "2.0.6", mcVersion = "1.4.6", author = "Eloraam" },
  { name = "Not Enough Items", version = "1.0.5.104", mcVersion = "1.8", author = "ChickenBones" }
}

As you can see, this list could be sorted in a number of ways;
by name, by version, author, etc

So you need to customize the 'compare' function to allow you to compare tables
This implemintation accepts a table of the order priorety, in this example its sorted by
version, then name, then mcVersion, then author

local function compare(data1,data2)
  local sortOrder = {"version","name","mcVersion","author"} -- Sorts in this order, first is the top priority
  for a,b in pairs(sortOrder) do --# Iterates through sortOrder
	if data1[b] ~= data2[b] then --# Example: data1 is mods[1] and b is 'name'
	  return data1[b]>data2[b] --# REMEMBER: use the '>' sign for INSERTION sort, '<=' for MERGE sort
	end
  end
  return true --# The enteries are the same, just pretend data1 is bigger
end

How to make tables that can be sorted

Spoiler

First, tables cannot be sparse

Sparse tables:

tbl1 = {
  this = "a",
  sparse = "table"
}

tbl2 = {
  1 = "this",
  2 = "IS",
  3 = "sparse",
  5 = "see?"
}

Non-sparse tables:

tbl1 = {
  "this",
  "isn't",
  "a",
  "sparse",
  "table"
}

tbl2 = {
  1 = "this",
  2 = "also",
  3 = "isn't",
  4 = "sparse"
}

Still don't get it?

Spoiler

Google

The Sorting Algorithms

Merge Sort
Most efficient when...
You don't know if the table is sorted or not
OR
The table isn't sorted yet

Spoiler

Code

Spoiler

Function to call:
merge(tableToSort)
Returns:
A new sorted table

Note that the original table isn't changed

local function compare(data1,data2)
  return data1 <= data2 --# REMEMBER: <= is REQUIRED for MERGE SORT
end
local function lMerge2(array, p, q, r)
  local n1 = q - p + 1
  local n2 = r - q
  local i
  local j
  local left = {}
  for i = 1, n1 do
	left[i] = array[p + i - 1]
  end
  left[n1 + 1] = math.huge
  local right = {}
  for j = 1, n2 do
	right[j] = array[q + j]
  end
  right[n2 + 1] = math.huge
  i = 1
  j = 1
  for k = p, r do
	if compare(left[i],right[j]) then
	  array[k] = left[i]
	  i = i + 1
	else
	  array[k] = right[j]
	  j = j + 1
	end
  end
end
local function lMerge(array, p, r)
  p = p or 1
  r = r or #array
  if p < r then
	local q = math.floor((p + r) / 2)
	lMerge(array, p, q)
	lMerge(array, q + 1, r)
	lMerge2(array, p, q, r)
  end
end
function merge(tableToSort)
  local copyTable = {}
  for i = 1, #tableToSort do
	copyTable[i] = tableToSort[i]
  end
  lMerge(copyTable)
  return copyTable
end

Source:
http://searchcode.co.&#46;&#46;/view/17302157/

Efficency

Spoiler

When data is... | Iterations
---------------------------------+-----------
Already Sorted | n * log(n)
Completely Random | n * log(n)
Sorted in Reverse Order | n * log(n)

n = length of table to sort

How it works

Spoiler

The basic idea is to split the collection into smaller groups by halving it until the groups only have one element or no elements (which are both entirely sorted groups).
Then merge the groups back together so that their elements are in order
Source:http://rosettacode.org/wiki/Sorting_algorithms/Merge_sort

Insertion Sort
Most efficient when...
Data is sorted, but a new entry was added and needs sorting

Spoiler

Code

Spoiler

Function to call:
'insertion(tableToSort)'
Returns:
New table that is sorted

Note that the original table isn't changed

local function compare(data1,data2)
  return data1 > data2 --# REMEMBER: Use > for INSERTION SORT
end
function insertion(tToSort)
  local copyToSort = {}
  for i = 1, #tToSort do
	copyToSort[i] = tToSort[i]
  end
  local len = #copyToSort
  for j = 2, len do
	local key = copyToSort[j]
	local i = j - 1
	while i > 0 and compare(copyToSort[i],key) do
	  copyToSort[i + 1] = copyToSort[i]
	  i = i - 1
	end
	copyToSort[i + 1] = key
  end
  return copyToSort
end

Source:
https://github.com/a...sertionSort.lua

Efficency

Spoiler

When data is... | Iterations
---------------------------------+-----------
Already Sorted | n
Completely Random | n^2
Sorted in Reverse Order | n^2

n = length of table to sort

How it works

Spoiler

https://en.wikipedia.&#46;&#46;/Insertion_sort

Sorry for the long post
If this was helpful, how about a +1

If any of my info is incorrect, or you need help, leave a comment!

Spoiler

You: What about table.sort()?

Me: Shut your face

But yes you could use that instead...
http://www.lua.org/pil/19.3.html

Edited by HPWebcamAble, 27 June 2015 - 01:17 AM.

[クデル]

oooh fancyy

[HPWebcamAble]

Sandstorm, on 02 July 2015 - 09:47 AM, said:

oooh fancyy

Maybe a bit TOO fancy for a Minecraft mod, but oh well, I had fun researching and writing this.

[クデル]

HPWebcamAble, on 02 July 2015 - 06:31 PM, said:

Sandstorm, on 02 July 2015 - 09:47 AM, said:

oooh fancyy />

Maybe a bit TOO fancy for a Minecraft mod, but oh well, I had fun researching and writing this.

Doesn't matter, its awesome either way

[Konlab]

Bubblesort?

[HPWebcamAble]

Konlab, on 06 September 2015 - 06:46 PM, said:

Bubblesort?

Not that efficient, merge sort is a lot better with log(n) efficiency

I was actually going to include one like that, but I couldn't get it working, and it wasn't very efficient anyway

[Konlab]

Oh idk the efficiencies, but i did know that bubblesort is a sorting algorithm.

[HPWebcamAble]

Konlab, on 06 September 2015 - 07:04 PM, said:

Oh idk the efficiencies

Ah, these are designed for a sorting a lot of data, so efficiency is important

[Konlab]

License?
anyways +1
edit:
ik isnt the best place to put this but:
how to calculate efficiency?

Edited by Konlab, 06 September 2015 - 07:24 PM.

[HPWebcamAble]

Konlab, on 06 September 2015 - 07:22 PM, said:

License?

None. Not my all my code, I just got it working in CC. I think it was from Wikipedia or something.

Konlab, on 06 September 2015 - 07:22 PM, said:

ik isnt the best place to put this but:
how to calculate efficiency?

Its the number of passes it takes to sort the data.
Each scenario (Best case, worst case, and average) defines how the data was sorted before the algorithm was ran
(Best is already sorted, worst is sorted in REVERSE, and average is random)

Konlab, on 06 September 2015 - 07:22 PM, said:

anyways +1

Thanks

[supernicejohn]

What about counting sort? I'd like to see that implemented here too, just cause I think it's cool.

Also it's one of the fastest

[Xella]

supernicejohn, on 29 August 2017 - 07:59 AM, said:

What about counting sort? I'd like to see that implemented here too, just cause I think it's cool.

Also it's one of the fastest

It's not really worth it since there's table.sort(), but here's quicksort (fastest in most cases):

function quickSort(arrayToSort)
  local n = table.getn(arrayToSort)
  if (n <= 1) then
    return arrayToSort
  else
    local pivot = math.random(1, n)
    local pivotValue = arrayToSort[pivot].value
    local smallerArray = {}
    local equalArray = {}
    local biggerArray = {}
    for k, v in pairs(arrayToSort) do
      if (v.value < pivotValue) then
        table.insert(smallerArray, v)
      elseif (v.value == pivotValue) then
        table.insert(equalArray, v)
      else
        table.insert(biggerArray, v)
      end
    end
    local sortedSmallerArray = quickSort(smallerArray)
    local sortedBiggerArray = quickSort(biggerArray)
    local sortedArray = sortedBiggerArray
    for k, v in pairs(equalArray) do
      table.insert(sortedArray, v)
    end
    for k, v in pairs(sortedSmallerArray) do
      table.insert(sortedArray, v)
    end
    return sortedArray
  end
end

Hope this satisfies you enough