Bubble Sorting Algorithm

Question

I made a simple Python program which takes a list of unique numbers and orders them from smallest to greatest. The algorithm (which is actually quite similar to bubble sort) works like this:

• Take the first number
  • If it is larger than the next number, switch them
  • If it is smaller than the next number, do nothing
• Continue to next number until the algorithm has done this to everything in the list
• Check if the list is in the correct order
  • If not, repeat the process
  • If it is, print out the list in order and time taken in seconds

import random
import time
import sys

sys.setrecursionlimit(10000)
value_list = []
# Create values
len_of_list = random.randint(8500, 10000)
for number in range(0, len_of_list):
    value_list.append(number)
random.shuffle(value_list)


def timeit(func):
    def wrapper(*args, **kwargs):
        start = time.time()
        result = func(*args, **kwargs)
        print "The function {.__name__} took {:.15f} seconds to finish.".format(func, time.time() - start)
        return result
    return wrapper


def custom_sort():
    for index in range(0, len_of_list):
        if (index + 1) == len_of_list:
            if not check_results():
                custom_sort()
            elif check_results():
                print value_list
        else:
            if value_list[index] > value_list[index + 1]:
                smaller_val = value_list[index + 1]
                value_list[index + 1] = value_list[index]
                value_list[index] = smaller_val
            elif value_list[index] < value_list[index + 1]:
                continue


def check_results():
    for index in range(0, len_of_list):
        if (index + 1) == len_of_list:
            return True
        else:
            if value_list[index] < value_list[index + 1]:
                continue
            elif value_list[index] > value_list[index + 1]:
                return False


@timeit
def run():
    custom_sort()

run()

I have made a function called run() specifically so that @timeit only prints out one line stating how long it took to finish. custom_sort() sorts the numbers in the list for the first four bullets. check_results() checks if the list is in order like in the last three bullets. sys.setrecursionlimit(10000) is used so that I don't get a recursion error since the list can hold up to 10000 numbers.

Example output (due to reports of crashing, I will replace most of the values with ... , I hope you understand what the result should be):

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, ... 9669, 9670, 9671, 9672, 9673, 9674, 9675, 9676, 9677, 9678, 9679, 9680]
The function run took 24.037000179290771 seconds to finish.

Is there a way to shorten my code and make my algorithm faster? The slowest it has been is about 36 seconds to sort the maximum amount of numbers (10000).

Answer 1

There are several quick improvements that can halve the time.

There is a redundant check where you first check a > b and then check b < a. Ignoring that the "continue" statement makes any check redundant since if it doesn't match you'll fall past and continue anyway, it's also redundant because you're checking for the negative of a previous check. Well, an almost negative, you don't explicitly deal with a == b but I'm guessing you want to continue there not swap them, both are a valid result but swapping identical values is a waste.

Also a bunch of the time is taken filling the array. Rather than looping over a long array and calling append on each item, you can just set

value_list = range(len_of_list)

The other major optimisation is to not use recursion, the reason this improves performance here is because your comparison for finishing is a long operation that you have inside the loop, by making the function looping / iterative it is easy to move that outside the inner loop saving a large amount of time.

Also you have some funny logic around the last element, just looping (0, n-1) fixes that.

The last element MUST be in order after the first iteration, it gets pushed back every single time, so instead of looping (0, n - 1) you can actually loop (0, n - i - 1) where i is the iteration number.

You can remove the check_results call entirely and consider what it means to be "in order". Being in order means that no swaps have happened. That means that instead of looping over everything you can just track whether you've swapped anything. If you haven't then congratulations, everything is in order.

This saves a large amount of time since your "check_results" loops over the array doing comparisons which you were doing inside another loop (well, recursed call).

Below is my modification of your code to include the changes I have described. I have changed some variable names to more clearly show their new meaning.

import random
import time
import sys

value_list = []
# Create values
len_of_list = random.randint(8500, 10000)
value_list = range(len_of_list)
random.shuffle(value_list)

def timeit(func):
    def wrapper(*args, **kwargs):
        start = time.time()
        result = func(*args, **kwargs)
        print "The function {.__name__} took {:.15f} seconds to finish.".format(func, time.time() - start)
        return result
    return wrapper

def custom_sort():
    has_swapped = True
    iteration = 0
    while has_swapped:
        has_swapped = False
        for index in range(len_of_list - iteration - 1):
                next_value = value_list[index + 1]
                if value_list[index] > next_value:
                    has_swapped = True
                    value_list[index + 1] = value_list[index]
                    value_list[index] = next_value
        iteration += 1
        if not has_swapped:
           print value_list


@timeit
def run():
    custom_sort()

run()

For reference, your code on my system executed in around 25-28 seconds depending on the random array length, my modified version executes in 12-14 seconds. I am sure there are further optimisations I have missed.

Answer 2

Consider removing check results from the code entirely. If no switches are made then the result is complete. Stopping at each iteration to check is taking n time. I would swap that portion of code to a counter that resets on each iteration to count the number of swaps made if swaps == 0 then no swaps were made and it should be in order. The extra "useless" run of the algorithm acts as the check but is only done once unnecessarily.