In this tutorial, we'll see a simple sorting algorithm. It will take as input a sequence of numbers, and will return the same numbers in sorted order.

# Example

Lets see an example.

Suppose the input is as follows: 5 10 8 7 3 6 12 2 7

Then the desired output is: 2 3 5 6 7 7 8 10 12

# Algorithm

Here's the algorithm we'll use to perform the sorting (Python code).

# simple_sort.pydef simple_sort(array):n = len(array)for i in range(n):# compare array[i] with array[i+1], array[i+2], ... array[n-1]for j in range(i+1, n):# swap if we find a smaller valueif array[i] > array[j]:array[i], array[j] = array[j], array[i]return array

The strategy of the algorithm is that in the first iteration of the outer loop, it makes array[0] the minimum value out of all numbers. It achieves this by comparing array[0] to all the remaining elements - array[1] through array[n-1], and swapping if it finds a smaller value. Then, it repeats the same thing for position 1, by comparing to positions 2 through n-1. And so on, for each position.

# Example execution

For our sample input, the following sequence of swaps would occur.

5 10 8 7 3 6 12 2 7

**Swap 1: **

Initially, i = 0. The first swap happens when j = 4, since array[j] = 3 and array[i] = 5. This gives:

3 10 8 7 5 6 12 2 7

**Swap 2:**

The next swap happens when array[j] = 2, i.e. j = 7. This gives:

2 10 8 7 5 6 12 3 7

**Swaps 3-6:**

For i = 1, the following 4 swaps happen.

2 8 10 7 5 6 12 3 7

2 7 10 8 5 6 12 3 7

2 5 10 8 7 6 12 3 7

2 3 10 8 7 6 12 5 7

Now, the first 2 elements are sorted. We keep going, and at the end, all elements become sorted.

# Time complexity

Simple sort does the innermost loop work about n^2/2 times, where n is the length of the array. Hence, it is an O(n^2) algorithm.

Since computers can perform about 1 billion operations per second, we'd expect simple sort to be fine for input arrays with few thousand elements. Once the array size gets > 10,000, it should start to become quite slow.

# Testing Simple Sort (Hands-on)

Use the following grader to test the speed of Simple Sort.

# grader.pyfrom __future__ import print_functionimport datetimeimport randomfrom simple_sort import simple_sortnpassed, nfailed = 0, 0for itest in range(1, 13):print('Test case:', itest)nelements = random.randint(int((10**(itest/2.))/2), int(10**(itest/2.)))print('Array size:', nelements)array = [random.randint(1, 100*nelements) for _ in range(nelements)]tic = datetime.datetime.now()submission = simple_sort(array)toc = datetime.datetime.now()answer = sorted(array)correct = len(submission) == len(answer) and (submission == answer)if correct:print('PASSED (Runtime = %.2f seconds)' % (toc-tic).total_seconds())npassed += 1else:print('FAILED')nfailed += 1print(array)print(submission)print(answer)print('='*100)print('TOTAL PASSED: %d. TOTAL FAILED: %d.' % (npassed, nfailed))

Save the file above, and then run the following command:

python grader.py

and you should see the results of running the grader.

The following is the output I got:

Test case: 1Array size: 2PASSED (Runtime = 0.00 seconds)====================================================================================================Test case: 2Array size: 9PASSED (Runtime = 0.00 seconds)====================================================================================================Test case: 3Array size: 22PASSED (Runtime = 0.00 seconds)====================================================================================================Test case: 4Array size: 73PASSED (Runtime = 0.00 seconds)====================================================================================================Test case: 5Array size: 172PASSED (Runtime = 0.00 seconds)====================================================================================================Test case: 6Array size: 572PASSED (Runtime = 0.02 seconds)====================================================================================================Test case: 7Array size: 2867PASSED (Runtime = 0.39 seconds)====================================================================================================Test case: 8Array size: 7248PASSED (Runtime = 2.72 seconds)====================================================================================================Test case: 9Array size: 28978PASSED (Runtime = 46.94 seconds)====================================================================================================Test case: 10Array size: 95679PASSED (Runtime = 856.32 seconds)====================================================================================================Test case: 11Array size: 258638...

I stopped waiting at the 11th test case. For the smaller test cases, even though the run-time of the code is increasing, we don't notice anything since the time taken is so small.

But test case 7 onwards, we can clearly see that making the test case about 3-4x larger, is making the run-time about 10-15x. That is, the run-time is growing with the square of the array length *n*.

For test case 12, where the array length is about 1,000,000, simple sort will take about 10*10*850 seconds to execute = 1 day!

# Next steps

In the upcoming tutorials, we'll see O(n \log n) sorting algorithms. These algorithms will be able to sort sequences of length 1,000,000 within a few seconds, as opposed to only sequences of length 10,000.