An answer to this question on Stack Overflow.

Question

I am currently trying to understand sorting algorithms, and have been looking at pseudocode and converting it to python (using python 3.6, IDE is Spyder 3.1.2). I've written a simple Bubble Sort:

def BubbleSort(array_to_sort):
    n = len(array_to_sort) - 1
    swapped = True
    while (swapped):
        swapped = False
        for i in range(n):
             if array_to_sort[i] > array_to_sort[i+1]:
                array_to_sort[i+1], array_to_sort[i] = array_to_sort[i], array_to_sort[i+1] 
                swapped = True
    return array_to_sort

And a simple Selection Sort:

def SelectionSort(array_to_sort):
    n = len(array_to_sort)
    for i in range(n):
        minPos = i
        for j in range(i+1, n):
            if array_to_sort[j] < array_to_sort[minPos]:
                minPos=j
            
        if minPos != i:
            array_to_sort[i], array_to_sort[minPos] = array_to_sort[minPos], array_to_sort[i] 
    return array_to_sort

And am trying to time them like so:

def main():
    array = RandomNumberArray()
    a = timeit.Timer(functools.partial(BubbleSort, array)) 
    print(a.timeit(1000))
    b = timeit.Timer(functools.partial(SelectionSort, array)) 
    print(b.timeit(1000))

RandomNumberArray just generates a list of numbers that I'd like to sort:

def RandomNumberArray():
    return random.sample(range(0, 1000), 1000)

As they have both have the same time complexity O(n²), I was expecting them to take roughly the same amount of time however I've found that my Selection Sort is performing comparatively worse to my Bubble Sort e.g. for an array with 1000 numbers over 1000 iterations -

BS results: 0.390 s

SS results: 63.618 s

And an array of 1000 numbers over 10000 iterations -

BS results: 2.074 s

SS results: 645.944 s

Is there an issue with the implementation of these algorithms or is it expected that there's such a large discrepancy? I'm aware that there are other faster sorts and in practice no one would really use a BS or SS but I'm just trying to understand why the SS appears to be so much slower than BS?

Answer

It's not a fair comparison because array gets sorted by the first call and is then passed to the second call. There are several sort algorithms for which already sorted inputs are a worst case.

Bubble sort also has O(n) best case time complexity while selection has O(n^2) best case.