Module: lib-tde.sort.quicksort

Lua implementation of quicksort

Quicksort is a divide and concur approach to sorting This is a crude implementation that provides decent sorting in most use cases However, it might not be the most optimal sorting algorithm for your case.

This module can have the comparison replaced by the user, so that you can also sort tables, numbers, strings etc

The default comparison function looks as followed:

function compare(smaller, bigger)
    return smaller < bigger
end

You can override it using

quicksort(list, func) -- where func it the new comparison function

Default usage is as followed:

local list = {10, 20, 15, 7, 12, 19}
local sorted = quicksort(list) -- looks like this: {7, 10, 12, 15, 19, 20}

Time complexity:

  • Lookup element O(n log(n) ) with worst case n²

Info:

  • Copyright: 2020 Tom Meyers
  • Author: Tom Meyers

Static module functions

lib-tde.sort.quicksort (list[, func]) -> table Sort a list of items in 0(n log(n)) time


Static module functions

lib-tde.sort.quicksort (list[, func]) -> table
Sort a list of items in 0(n log(n)) time

Parameters:

  • list table The list to be sorted
  • func function A comparison function -> takes 2 arguments should return true if the first argument is smaller (optional)

Returns:

    table A list containing the sorted elements

Usage:

  • -- This will sort the input list
     lib-tde.sort.quicksort(list)
  • -- This will sort the input list with a custom comparison function (based on the string length)
    lib-tde.sort.quicksort(list, function(smaller, bigger)
       return #smaller < #bigger
    end)
generated by LDoc 1.4.6 Build with 💜 By F0xedb Last updated 2021-05-21 03:30:15