Bubble Sort algorithm in Lua will not work

user_13837444 0
Viewed 199

I am currently learning Lua, and I am attempting to create a bubble sort algorithm with it. However, I am unable to get this to work. Is anyone able to point out why?

Some details I can point out are that, on shorter lists such as lists 3 elements long, the algorithm does succeed in sorting it but then continues to sort it as if it was not sorted. On longer lists such as lists 5 elements long, the program does not sort it at all. I have gotten this information by making the program print the list every time two elements are swapped.

user_input = 0
list = {}

while user_input ~= "SORT" do
  print("Input number value, or input SORT to start sort")
  user_input = io.read()
  if user_input ~= "SORT" then
    table.insert(list, user_input)
  end
end

done = false
while done == false do
  done = true
  for k, v in pairs(list) do
    if k ~= 1 then
      if list[k] < list[k - 1] then
        list[k], list[k - 1] = list[k - 1], list[k]
        done = false
        for k, v in pairs(list) do
          io.write(v .. " ")
        end
        print()
      end
    end
    if k == 1 then
      if list[k] < list[table.maxn(list)] then
        list[k], list[table.maxn(list)] = list[table.maxn(list)], list[k]
        done = false
        for k, v in pairs(list) do
          io.write(v .. " ")
        end
        print()
      end
    end
  end
end

io.write("RESULT: ")
for k, v in pairs(list) do
  io.write(v .. " ")
end
print()
bubble-sort lua
3 Answers

In Lua there are 2 functions for creating iterators for tables pairs and ipairs

With pairs the order produced is indeterminate, it will returned all key, value pairs but the order can not be garenteed.

  • You can find this under next in the reference manual for Lua 5.1
  • example: {1,2,3,4,5} the output could be 5,2,4,1,3

the order of ipairs is 1 to the first nil it will not return any non-integer keys.

  • example: {1,2,3,nil,5} would give you 1,2,3

Using pairs your algorithm's output could be correct but could appear incorrect due to the ordering from pairs

You want you use ipairs to evaluate your algorithm's output, so that it will be ordered by index.

Your algorithm does not perform a bubble sort as it is now, I can include corrections for that if you want. For this initial answer I think clearing up what would create an inconsistent output should point you in the right direction.

A bubble sort should "sort" 1 index at a time, the first pass will get the last value of the array sorted. then each pass after sorts following position. for example:

  • before first pass 2,1,3,4,5,8,7,6
  • after first pass 1,2,3,4,5,7,6,8

Wikipedia has great pages for sorting algorithms with gif images that can really help understand how it should function: Bubble Sort

user_73961480

You're using pairs() instead of ipairs() plus your code has an extra maxn() routine that isn't needed.

#! /usr/bin/env lua

local user_input = 0
local list = {}

while user_input ~= 'sort' do
    print( 'Input number value, or input SORT to start sort' )
    user_input = io.read() :lower()
    --  the word 'sort' doesn't return a number, thus no final insertion
    table.insert( list, tonumber( user_input ) )
end

local found_swap = true
while found_swap do
    found_swap = false
    for i = 2, #list do
        if list[i] < list[i -1] then
            list[i], list[i -1] = list[i -1], list[i]
            found_swap = true
        end
    end
end

io.write( 'RESULT: ' )
for i, v in ipairs( list ) do
    io.write( v ..' ' )
end
print()
user_33420500

here's my implementation, a couple notes:

My version of lua (luau) supports type checking etc. so you may need to remove : table from the paramater. (If you'd like to find more out about luau - here's the link: https://roblox.github.io/luau/ - it's really cool)

local function bubbleSort(t: table)
    local function check(i, v)
        local nextNum = t[i+1]
        if nextNum and (nextNum < v) then
            t[i] = nextNum
            t[i + 1] = v

            return true
        end
    end

    local changeMade
    repeat
        changeMade = false
        for i, v in next, t do
            changeMade = check(i, v) or changeMade
        end
    until changeMade == false
end

local tableForSorting = {2,5,4} --2,4,5
bubbleSort(tableForSorting)
print(tableForSorting)

Hope this is of some help and shows how you can really slim down your codebase and it still work exactly the same! The reason yours wasn't working - as others - have mentioned is pairs() doesn't consistently order the list the same way.

In practise we use pairs() for dictionaries while we use ipairs() for arrays. You'll notice i'm using next in this example, next is exactly the same as ipairs(). Drop a question below if you have any follow up questions :)!

user_104803730
Related