Eccentric Developments

What is sorting

A common task in programming is sorting lists of items: taking all the elements in a list and shuffling them to be in a particular order; for example, having all the numbers sorted from smallest to biggest, or a list of names sorted alphabetically.

There are several algorithms to order information. Some are simpler than others, while others are more complex but usually faster. In this case, I'll talk about one of the most simple ones: bubble sort.

Bubble sort implementation

Bubble sort is one of the simplest ways for sorting elements. It compares each item with the next one and swaps them if the order is not the one desired.

In simple terms, it works like this:

1. Having a list of n items
2. Compare the current one with the next
3. If it is larger than the next, swap them.
4. Move to the next item
5. If you are at the end of the list, go back to the beginning
6. Go back to step 2
7. Repeat steps 2 to 6, n times

Let's implement this quickly using LUA:

numbers = {5,6,1,2,9,3,4,8,10,7}
count = #numbers

-- Bubble sort starts here
for m = 1, count do --outer loop
    for n = 1, count - 1  do --inner loop
        temp = numbers[n + 1]
        if numbers[n] > temp then
            numbers[n + 1] = numbers[n]
            numbers[n] = temp
        end
    end
end
-- Bubble sort ends here

-- Check if numbers are correctly ordered
for n = 1, count - 1 do
    if numbers[n] > numbers[n+1] then
        return "Incorrect"
    end
end
return "Correct"

What are you seeing?

After hitting the "Run" button, the number of times each line executes appears. This algorithm runs line 6 one hundred times! And all it does is order 10 numbers. Other lines of the code also show huge numbers for execution.

Can we do better?

Of course! A simple change that can improve the algorithm a little bit is to alter line 6 to read: for n = 1, count - m do, as follows:

numbers = {5,6,1,2,9,3,4,8,10,7}
count = #numbers

-- Bubble sort starts here
for m = 1, count do --outer loop
    for n = 1, count - m  do --inner loop
        temp = numbers[n + 1]
        if numbers[n] > temp then
            numbers[n + 1] = numbers[n]
            numbers[n] = temp
        end
    end
end
-- Bubble sort ends here

-- Check if numbers are correctly ordered
for n = 1, count - 1 do
    if numbers[n] > numbers[n+1] then
        return "Incorrect"
    end
end
return "Correct"

That is much better already! Instead of having line 6 execute 100 times, it is now down to 55, almost twice as fast!

After every iteration of the outer loop, the algorithm moves the largest item to the end of the list, and we do not need to look at it again because there could be no other larger than it. That means that we will be checking a smaller list on every iteration.

But still, we can make this better.

Final upgrade

There are two edge cases that bubble sort has to face: when all items are in inverse order, which is called worst-case, and the other is when all of them are in their correct order, called best-case.

Think about a best-case list of numbers: 1, 2, 3, 4. The algorithm will still do all the work even though no reordering is needed. To detect this, we add code to check if no swap happened for a particular iteration in the outer loop (line 5), which means all items in the list are in their correct position and terminate early.

numbers = {5,6,1,2,9,3,4,8,10,7}
count = #numbers

-- Bubble sort starts here
for m = 1, count do --outer loop
    change = false
    for n = 1, count - m  do --inner loop
        temp = numbers[n + 1]
        if numbers[n] > temp then
            numbers[n + 1] = numbers[n]
            numbers[n] = temp
            change = true
        end
    end
    if change == false then break end
end
-- Bubble sort ends here

-- Check if numbers are correctly ordered
for n = 1, count - 1 do
    if numbers[n] > numbers[n+1] then
        return "Incorrect"
    end
end
return "Correct"

Wait, why did that help?

In the beginning, the list of numbers is out of order. But if you look at it closely, you will notice that some parts are already ordered; for example: 1, 2 and 5, 6 are correctly sorted sublists; they are just not in their final position.

The already sorted sections in the list help with the overall sorting work because it reduces the number of operations needed to complete the job. The check for the best-case scenario will trigger and finish the algorithm early.

This change will not help when the list is in the worst-case configuration, but most other permutations will benefit even in a small way. This enhancement turns out to be very useful.

Ending notes

Bubble sort is a simple but deceptive sorting algorithm: easy to implement but inefficient. There are other more efficient algorithms, but at the expense of implementation complexity, some of which I will talk about later.