Comparing efficiency

2 comments

Hopefully you saw in the last section that timing an algorithm is a good way to test efficiency. The results showed bubble sort to be quite inefficient, insertion a bit more so, but merge sort took the top prize. In most cases, merge sort will sort a list much quicker than the other two. The only exception is when a list is already sorted or nearly sorted, in which case insertion would be the quickest, but even bubble sort would work faster than the merge sort algorithm. Both bubble and insertion sort have in-built ways to reduce their comparisons if a list is already sorted, unlike merge sort which will perform the same operations regardless of the state of the list.

Computer scientists and mathematicians have developed a way of describing the efficiency of an algorithm. This is called Big O notation. This is a fairly advanced topic, so I won’t go into too much depth, but the algorithms can be described as follows:

Bubble sort’s efficiency is О(n2)
Insertion sort’s efficiency is also О(n2)
Merge sort’s efficiency is O(n log n)

What does this mean?

For bubble and insertion sort, the time taken to complete a sort is proportional to the square of the size of the list. That means doubling the size of a list will cause the number of operations that need to be performed to quadruple. This is called quadratic time.

For merge sort, the O(n log n) means that it runs in what is called linearithmic time. You can see from the graph below that, although the number of operations does increase as the size of the list to be sorted increases, the rate of increase is significantly smaller than for quadratic time.

Case study: Timsort

Python has built a built-in function for sorting lists. This example program uses the Python sorted function to create a sorted list from an unsorted list of randomly generated data.

#!/bin/python

import random

data = []

for x in range (0, 100):

data.append(random.randint(0, 100))

print(data)

print(sorted(data))

Sample output:

[92, 79, 31, 28, 72, 94, 23, 40, 82, 79, 51, 19, 20, 86, 23, 64, 100, 8, 53, 13, 28, 5, 40, 48, 26, 95, 89, 88, 26, 58, 5, 17, 80, 83, 50, 32, 22, 53, 5, 9, 41, 23, 57, 42, 3, 66, 30, 38, 28, 1, 21, 86, 29, 30, 70, 2, 97, 56, 84, 20, 67, 61, 46, 33, 6, 91, 37, 48, 14, 95, 48, 53, 62, 56, 9, 60, 68, 36, 68, 50, 57, 13, 40, 4, 46, 25, 76, 58, 56, 17, 60, 24, 80, 81, 45, 92, 95, 62, 13, 99]

[1, 2, 3, 4, 5, 5, 5, 6, 8, 9, 9, 13, 13, 13, 14, 17, 17, 19, 20, 20, 21, 22, 23, 23, 23, 24, 25, 26, 26, 28, 28, 28, 29, 30, 30, 31, 32, 33, 36, 37, 38, 40, 40, 40, 41, 42, 45, 46, 46, 48, 48, 48, 50, 50, 51, 53, 53, 53, 56, 56, 56, 57, 57, 58, 58, 60, 60, 61, 62, 62, 64, 66, 67, 68, 68, 70, 72, 76, 79, 79, 80, 80, 81, 82, 83, 84, 86, 86, 88, 89, 91, 92, 92, 94, 95, 95, 95, 97, 99, 100]

For sorted, Python uses an algorithm called Timsort, which was developed by Tim Peters, based on techniques by Peter McIlroy. The algorithm is designed to work well on a variety of input data because it is used in many different situations. It uses a combination of merge sort and another algorithm called insertion sort, and adapts its choice of algorithm based on properties of the input data.

Which sort is best?

You might be wondering why you, or your learners, should care about how a sort works if there’s already a function in Python (and other languages) for sorting. This is one area where you can make the distinction between simply programming and thinking more like a computer scientist.

Often when programming, you will know you need to sort something, but are not very concerned with how it’s done. All you need is a general-purpose “good enough” solution. However, as you’ve discovered with the merge, insertion, and bubble sorts, different algorithms are better suited to different datasets and scenarios. Computer scientists concern themselves with selecting (or creating) the right algorithm to suit the data being processed.

Challenge

Can you add a Timsort function to your earlier program comparing the completion times of algorithms?

<- previous

next ->