19.1. Ordenamiento por selección

Éste método de ordenamiento se basa en la siguiente idea:

Paso 1.1: Buscar el mayor de todos los elementos de la lista.

Lista = | 3 | 2 | -1 | 5 | 0 | 2 |

Encuentra el valor 5 en la posición 3.

Paso 1.2: Poner el mayor al final (intercambiar el que está en la última posición de la lista con el mayor encontrado).

Intercambia el elemento de la posición 3 con el de la posición 5. En la última posición de la lista está el mayor de todos.

Lista = | 3 | 2 | -1 | 2 | 0 | 5 |

Paso 2.1: Buscar el mayor de todos los elementos del segmento de la lista entre la primera y la anteúltima posición.

Lista = | 3 | 2 | -1 | 2 | 0 | 5 |

Encuentra el valor 3 en la posición 0.

Paso 2.2: Poner el mayor al final del segmento (intercambiar el que está en la última posición del segmento, o sea anteúltima posición de la lista, con el mayor encontrado).

Lista = | 0 | 2 | -1 | 2 | 3 | 5 |

Intercambia el elemento de la posición 0 con el valor de la posición 4. En la anteúltima y última posición de la lista están los dos mayores en su posición definitiva.

Paso n: Se termina cuando queda un único elemento sin tratar: el que está en la primera posición de la lista, y que es el menor de todos porque todos los mayores fueron reubicados.

Lista = | -1 | 0 | 2 | 2 | 3 | 5 |

La implementación en Python puede verse en el código 19.1.

La función principal, ord_seleccion es la encargada de recorrer la lista, ubicando el mayor elemento al final del segmento y luego reduciendo el segmento a analizar.

Mientras que buscar_max es una función que ya se estudió previamente, que busca el mayor elemento de la lista y devuelve su posición.

A continuación, algunas una ejecuciones de prueba de ese código:

>>> l=[3, 2, -1, 5, 0, 2]
>>> ord_seleccion(l)
DEBUG: 3 5 [3, 2, -1, 2, 0, 5]
DEBUG: 0 4 [0, 2, -1, 2, 3, 5]
DEBUG: 1 3 [0, 2, -1, 2, 3, 5]
DEBUG: 1 2 [0, -1, 2, 2, 3, 5]
DEBUG: 0 1 [-1, 0, 2, 2, 3, 5]
> >>> print l
[-1, 0, 2, 2, 3, 5]
>>> l=[]
>>> ord_seleccion(l)
>>> l=[1]
>>> ord_seleccion(l)
>>> print l
[1]
>>> l=[1,2,3,4,5]
>>> ord_seleccion(l)
DEBUG: 4 4 [1, 2, 3, 4, 5]
DEBUG: 3 3 [1, 2, 3, 4, 5]
DEBUG: 2 2 [1, 2, 3, 4, 5]
DEBUG: 1 1 [1, 2, 3, 4, 5]

Puede verse que aún cuando la lista está ordenada, se la recorre buscando los mayores elementos y ubicándolos en la misma posición en la que se encuentran.

19.1.1. Invariante en el ordenamiento por selección

Todo ordenamiento tiene un invariante que permite asegurarse de que cada paso que se toma va en la dirección de obtener una lista ordenada.

# Código 19.1: seleccion.py: Ordena una lista por selección

#/usr/bin/env python
#encoding: latin1

def ord_seleccion(lista):
    """ Ordena una lista de elementos según el método de selección.
        Pre: los elementos de la lista deben ser comparables.
        Post: la lista está ordenada. """

    # n = posicion final del segmento a tratar, comienza en len(lista)-1*
    n = len(lista)-1

    # cicla mientras haya elementos para ordenar (2 o más elementos)
    while n > 0:
        # p es la posicion del mayor valor del segmento
        p = buscar_max(lista, 0, n)

        # intercambia el valor que está en p con el valor que
        # está en la última posición del segmento
        lista[p], lista[n] = lista[n], lista[p]

        print "DEBUG: ", p, n, lista

        # reduce el segmento en 1
        n = n - 1

def buscar_max(lista, ini, fin):
    """ Devuelve la posición del máximo elemento en un segmento de
        lista de elementos comparables.
        Se trabaja sobre lista, que no debe ser vacía.
        ini es la posición inicial del segmento, debe ser válida.
        fin es la posición final del segmento, debe ser válida. """

    pos_max = ini
    for i in xrange(ini+1, fin+1):
        if lista[i] > lista[pos_max]:
            pos_max = i
    return pos_max

En el caso del ordenamiento por selección, el invariante es que los elementos desde n+1 hasta el final de la lista están ordenados y son mayores que los elementos de 0 a n, es decir que ya están en su posición definitiva.

19.1.2. ¿Cuánto cuesta ordenar por selección?

Como se puede ver en el código de la función buscar_max, para buscar el máximo ele-mento en un segmento de lista se debe recorrer todo ese segmento, por lo que en nuestro caso debemos recorrer en el primer paso N elementos, en el segundo paso N —1 elementos, en el tercer paso N — 2 elementos, etc. Cada visita a un elemento implica una cantidad constante y pequeña de comparaciones (que no depende de N). Por lo tanto tenemos que

T(N) = c * (2 + 3 + . . . + N ) = c * N * (N + 1)/2 = N^2

O sea que ordenar por selección una lista de tamaño N insume tiempo del orden de N^2. Como ya se vio, este tiempo es independiente de si la lista estaba previamente ordenda o no.

En cuanto al espacio utilizado, sólo se tiene en memoria la lista que se desea ordenar y algunas variables de tamaño 1.