PcoWSkbVqDnWTu_dm2ix
We use cookies on this site to enhance your user experience

Insertion sort

Insertion sort

Jul 03 2018, 9:52 AM PST 5 min

The Insertion Sort is a data sorting algorithm. The insertion sort is a fairly simple sorting algorithm. It has a complexity of O(n+d) where d is the number of out-of-order elements, which makes it more efficient than its Articles/Selection Sort counterpart.

Procedure

Separate current element from list. Go down the list from that position until you either hit the beginning or find a value smaller. Insert the element in that spot. Repeat for all positions

Example Code

--Sorting table tab
--loop through every position in the table except the last one
for i = 1, #tab - 1 do
    --store the value of the current element, and remove it from the table
    local value = table.remove(tab, i)
    
    --loop-control variable
    local t = i
    repeat
        t = t - 1
        --if it is less than 1, it is the smallest if it is less than that position, t+1
    until t < 1 or tab[t] <= value
    table.insert(tab, t + 1, value)
end