33. Insertion sort¶

This sorting algorithm has the advantage that it allows the list to be modified while the sort is occurring. The unordered part of the list can grow by adding elements and the already sorted part of the list can shrink by removing elements. This makes it a flexible algorithm.

This algorithm is usually used when the number of elements to be sorted is small (less than 100 elements). For larger data sets there are faster and more efficient algorithms, such as merge sort, heap sort, or quick sort.

Algorithm explanation¶

At first let's assume that the first item in the list is already sorted, while all the others are unordered.

Next we will take the second item in the list. If this element is less than the first element in the list, we will change their positions. At this point we already have two list elements sorted.

We will continue with the third item on the list. As long as it is smaller, we will exchange it with the second and the first element of the list, until it is ordered.

The algorithm continues sorting the rest of the elements one by one until it places the last element in the list in place, at which point the list sorting is complete.

Management program¶

The complete program for sorting elements of a list according to the insertion algorithm will be as follows:

def inserta_elemento(lista, index):
    for i in range(index, 0, -1):
        if lista[i - 1] > lista[i]:
            temp = lista[i - 1]
            lista[i - 1] = lista[i]
            lista[i] = temp
        else:
            break

def ordenar(lista):
    for index in range(1, len(lista)):
        inserta_elemento(lista, index)


lista = [6, 3, 9, 5, 7, 1, 2, 4, 10, 8]
ordenar(lista)
print(lista)

Exit:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Binary insertion¶

The insertion algorithm allows an improvement that consists of searching for the correct insertion location using binary search, which was already studied in a previous unit.

The improved binary insertion algorithm is as follows:

def inserta_elemento(lista, index):
    # Busqueda binaria
    primero = 0
    ultimo = index - 1
    while primero <= ultimo:
        medio = (primero + ultimo) // 2
        if lista[index] <= lista[medio]:
            ultimo = medio - 1
        else:
            primero = medio + 1

    # Desplaza elemento a su lugar
    temp = lista[index]
    for i in range(index, primero, -1):
        lista[i] = lista[i - 1]
    lista[primero] = temp


def ordenar(lista):
    for index in range(1, len(lista)):
        inserta_elemento(lista, index)


lista = [6, 3, 9, 5, 7, 1, 2, 4, 10, 8]
ordenar(lista)
print(lista)

Exit:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Exercises¶

Write a function that sorts a list of three elements by the insertion algorithm, without using loops of any kind, just with if statements.

Call the function with the following code to verify that the order() function works correctly:

listas = [
    [1, 2, 3], [1, 3, 2],
    [2, 1, 3], [2, 3, 1],
    [3, 1, 2], [3, 2, 1]
    ]
error = False
for lista in listas:
    ordenar(lista)
    if lista != [1, 2, 3]:
        error = True
if error:
    print('Error')
else:
    print('Correcto')

Rewrite the sorting program so that it orders the elements in the opposite direction, from largest to smallest. You will need to change the names of the functions and variables to adapt to the new function they are performing.
Rewrite the sort program so that it performs list sorting in a single function, without separating the code into two different functions. Remember to change the name of the variables in the insert_item function so that they are not the same.
Write an insertion sort algorithm that sorts text strings by string length, so that the shortest words are placed at the beginning and the longest words at the end:
```
lista = ['manzana', 'uva', 'melocotón', 'sandía', 'melón']
```