32. Sort by selection

With this algorithm we begin to see data sorting algorithms. These types of algorithms allow you to order a list of data from smallest to largest. Computers take their name precisely from this important function that they can perform, sorting lists of names or numbers to facilitate the creation of lists or the subsequent search for data.

Selection algorithm

The sorting algorithm consists of searching the entire list for the smallest element of all. In principle we start with the first element in the list as the smallest. Then a loop compares one by one all the elements in the list with the smallest and selects in each case the smallest of all:

lista = [6, 3, 9, 5, 7, 1, 2, 4, 10, 8]
menor = 0
for i in range(len(lista)):
    if lista[i] < lista[menor]:
        menor = i

The smallest variable will be worth 5, which is the position of the smallest element, 1.

Once we have found the position of the smallest element of all, we swap that element with the first one in the list:

temp = lista[0]
lista[0] = lista[menor]
lista[menor] = temp

Now we know that the first element of the list is already ordered as it is the smallest of all the elements in the list.

To continue, we repeat the procedure, but with all the elements in the list starting from the second position. This will ensure that we have the second element of the list sorted.

By repeating the procedure over and over again, we order all the elements in the list from the first to the penultimate. Once all the elements except one have been sorted, we know that the last element will be the largest of all and will be at the end of the list, so it will not be necessary to sort the last element.

Management program I

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

def busca_menor(lista, final):
    menor = final
    for i in range(final, len(lista)):
        if lista[i] < lista[menor]:
            menor = i
    return menor


def ordenar(lista):
    for final in range(len(lista) - 1):
        menor = busca_menor(lista, final)
        temp = lista[final]
        lista[final] = lista[menor]
        lista[menor] = temp


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]

Management program II

In this second version of the sorting program the algorithm will be altered a little. After finding the smallest element in the list, we will move all unordered elements below the smallest element to the right, leaving a gap to place it in its place.

This modified algorithm has the advantage of keeping all list elements that have not yet been moved to the beginning of the list in their original order:

def busca_menor(lista, comienzo):
    menor = comienzo
    for i in range(comienzo, len(lista)):
        if lista[i] < lista[menor]:
            menor = i
    return menor


def desplaza_derecha(lista, comienzo, final):
    temp = lista[final]
    for i in range(final, comienzo, -1):
        lista[i] = lista[i - 1]
    lista[comienzo] = temp


def ordenar(lista):
    for comienzo in range(len(lista) - 1):
        menor = busca_menor(lista, comienzo)
        desplaza_derecha(lista, comienzo, menor)


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

1. Rewrite the sorting program I 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.

2. Rewrite the sort II program so that it starts sorting the elements from the right, starting by sorting the largest of all the elements, which should be moved to the end of the list.

3. Write a program based on selection sort that shifts all zeros in a list to the left. The rest of the elements in the list must maintain the order they had at the beginning:

   lista = [1, 0, 5, 3, 0, 0, 6, 2]
   separar_ceros(lista)
   print(lista)
   

   Exit:

   [0, 0, 0, 1, 5, 3, 6, 2]
   

   The program will be based on the management program II. You must select the zeros one by one and move the zeros to the far left. If at any time it does not find a zero in the list, then the program will terminate.

4. Write a selection 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']