Sorting arrays
Bubble sort
Each pass through the data consists of making a set of comparisons between two data items. You always start with the items in position 0 and 1, then 1 and 2, then 2 and 3 etc. Each time, you compare the items and swap them if necessary.
After you have made a pass through all of the data, the biggest piece of data will be in the correct place. It has 'bubbled up' to the surface, so to speak, which is where this algorithm gets its name.
This can be implemented in Python as:
def bubbleSort(array): for passes in range(len(array) - 1, 0, -1): #counts down through the array, from the length of the array to 0 in decrements of -1 for i in range(passes): #loop for each pass if array[i] > array[i + 1]: #compares the element to the element beside it. if it is larger... temp = array[i] #element is placed in a holding variable array[i] = array[i + 1] #elements are swapped array[i + 1] = temp return array testdata = [54, 26, 93, 17, 77, 31, 44, 55, 20] print(bubbleSort(testdata))Output:
[17, 20, 26, 31, 44, 54, 55, 77, 93]To sort an array of n items, a maximum number of n - 1 passes are made through the array. To make the algorithm more efficient, a flag can be initialised at the beginning of each pass to set a value(True) if a swap is made. If no swap is made, the array is sorted.
Insertion sort
Insertion sort draws its inspiration from how humans sort cards in their hand when playing a card game. Consider a hand of cards which are not in order.
One approach to ordering the cards is to hold them in one hand and removing a single card with the other hand. That card can then be inserted into the correct position. This simple procedure is repeated until the hand is sorted.
This insertion sort process can be implemented in Python as:
def insertionSort(array): for j in range(1, len(array)): key = array[j] i = j - 1 while i > 0 and array[i] > key: array[i + 1] = array[i] i = i - 1 array[i + 1] = key return array testdata = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(insertionSort(testdata))This will output the same sorted result but, with a small data set as in this example, an insertion sort is likely to return the result more quickly.
