Al principio de esta serie, escribí un par de artículos sobre cómo ordenar diferentes tipos de listas en Python. Por ejemplo, escribí un artículo sobre cómo ordenar una lista de cadenas. Luego, más tarde escribí un artículo sobre cómo ordenar una lista de diccionarios. En ambos artículos, utilicé algunas soluciones elegantes que la biblioteca estándar de Python permite. Por supuesto, ¿qué pasa si queremos escribir nuestro propio algoritmo de clasificación? ¡Ese es nuestro tema de hoy!

Resulta que hay muchas formas de escribir su propio algoritmo de clasificación de fuerza bruta en Python. Por ejemplo, puede intentar implementar el ordenamiento por selección, el ordenamiento por burbujas o el ordenamiento por inserción. Para divertirse, incluso puede hacer su propio bogosort. En este artículo, veremos las soluciones para los cuatro algoritmos.

Descripción del problema

Si alguna vez ha tomado un curso de algoritmos o estructuras de datos, probablemente esté familiarizado con las diferentes formas en que podemos almacenar y administrar datos en un programa. Por ejemplo, podríamos almacenar información en una lista porque queremos poder acceder a ella al azar rápidamente. Alternativamente, podríamos optar por un diccionario porque queremos una forma rápida de buscar valores.

Cualquiera que sea la estructura de datos que elijamos, hay varias formas de interactuar con ella. Por ejemplo, una pila suele tener operaciones push y pop. Mientras tanto, una lista puede tener operaciones de inserción y eliminación.

En este artículo, veremos la lista de Python que puede funcionar como muchas estructuras de datos diferentes (por ejemplo, pilas, colas, etc.). Para nuestros propósitos, lo trataremos como una matriz de números enteros:

1
2
my_list = [4, -7, 5, 4]
my_sorted_list = [-7, 4, 4, 5]

Ahora, la pregunta es: ¿qué podemos hacer con una lista de números enteros? Bueno, podríamos intentar resumirlos. Alternativamente, podríamos buscar la media, la mediana y la moda. Dicho esto, no estás aquí para hacer nada de eso. Quieres saber cómo ordenar esto.

Dicho esto, la clasificación puede significar muchas cosas diferentes según el contexto. Por supuesto, como dijo mi amigo Robert :

Clasificar significa dar la vuelta al proverbial pájaro en entropía

En otras palabras, el objetivo de la clasificación es tomar el caos de alguna lista y organizarlo en algún orden específico. Por ejemplo, si ordenamos esta lista de números enteros, podríamos organizar los valores en orden ascendente o descendente. Afortunadamente, la mayoría de los algoritmos que veremos en este artículo funcionarán para cualquier dato clasificable como cadenas y caracteres.

Específicamente, nuestro objetivo será escribir algunos algoritmos de clasificación de listas a mano. En otras palabras, no utilizaremos ninguna de las soluciones sencillas descritas en los artículos anteriores. En su lugar, escribiremos nuestros propios bucles para implementar algunos de los algoritmos comunes de bajo rendimiento, como la clasificación por burbujas, la clasificación por inserción y la clasificación por selección (es decir, O (N 2 )). Después de todo, cada uno de estos algoritmos de bajo rendimiento funciona sobre la base de la fuerza bruta: ordena un elemento por pasada.

Por ahora, no nos molestaremos en hablar sobre la notación Big O, pero si estás interesado en ese tipo de cosas, escribí un artículo al respecto hace mucho tiempo .

Soluciones

Como ya mencioné, veremos tres algoritmos típicos de clasificación de fuerza bruta: clasificación de burbujas, clasificación de inserción y clasificación de selección. Por supuesto, no nos iremos de aquí sin al menos un algoritmo de clasificación divertido (pista: es tipo bogo).

Ordenar una lista con Ordenar por burbujas

Si no está familiarizado con la ordenación de burbujas, hemos escrito sobre el algoritmo para el repositorio de programas de muestra . En resumen, la clasificación de burbujas es un algoritmo que se basa en intercambiar pares consecutivos de elementos. Como resultado, los valores grandes tienden a aparecer en la parte superior de la lista. Para ver este algoritmo en acción, vea el siguiente video:

En cualquier caso, aquí hay una implementación simple de Python de clasificación de burbujas:

1
2
3
4
5
6
7
8
my_list = [4, -7, 5, 4]
is_sorted = False
while not is_sorted:
  is_sorted = True
  for i in range(len(my_list) - 1):
    if my_list[i] > my_list[i + 1]:
      my_list[i], my_list[i + 1] = my_list[i + 1], my_list[i]
      is_sorted = False

Escribí este algoritmo basado en el pseudocódigo proporcionado en las notas de clasificación de burbujas del Dr. Shun Yan Cheung . Esencialmente, funciona intercambiando continuamente pares de elementos consecutivos que están fuera de servicio hasta que no haya más intercambios que realizar. Por ejemplo, en la primera pasada, terminamos con el siguiente cambio:

1
2
[4, -7, 5, 4]  # Initial list
[-7, 4, 4, 5]  # After the initial iteration

Curiosamente, en este caso, terminamos con una lista ordenada después de la primera pasada. Por supuesto, ese casi nunca es el caso. Por ejemplo, si cambiamos la lista de la siguiente manera:

1
[5, 4, 3, 2, 1]

Solo veremos el movimiento 5 en la primera pasada:

1
2
[5, 4, 3, 2, 1]  # Initial list
[4, 3, 2, 1, 5]  # After the first iteration

En otras palabras, terminamos con nuestra peor pesadilla: una lista en orden inverso.

En cualquier caso, la parte del código que realiza cada intercambio es el bucle interno:

1
2
3
4
for i in range(len(my_list) - 1):
  if my_list[i] > my_list[i + 1]:
    my_list[i], my_list[i + 1] = my_list[i + 1], my_list[i]
    is_sorted = False

Mientras tanto, el código que detecta si la lista está ordenada es el bucle externo:

1
2
3
is_sorted = False
while not is_sorted:
  is_sorted = True

Por supuesto, el mecanismo real que nos dice si la lista no está ordenada es la línea is_sorted = Falseen el ciclo interno. Si no se necesitan cambios para pasar la lista, la is_sortedvariable permanece verdadera. En otras palabras, ¡hemos terminado!

Como probablemente pueda imaginar, hay algunas optimizaciones menores que podemos hacer con este algoritmo. Por ejemplo, sabemos que cada pasada mueve el elemento más grande actual al final de la lista. Como resultado, podríamos reducir nuestro número de comprobaciones "reduciendo" nuestra lista en una en cada iteración. Por supuesto, dejaré ese ejercicio en tus manos.

Ordenar una lista con ordenación por inserción

Si el ordenamiento por burbujas no es su estilo, quizás le gustaría probar el ordenamiento por inserción. Una vez más, no entraré en demasiados detalles sobre este algoritmo porque hemos escrito sobre él para el repositorio de programas de muestra . Dicho esto, la idea básica detrás de la ordenación por inserción es tratar un subconjunto de la lista como ordenado y aumentar esa colección insertando elementos en ella del conjunto no ordenado, o visualmente:

En términos de implementación, podemos escribir el algoritmo de ordenación por inserción de la siguiente manera:

1
2
3
4
5
6
7
8
my_list = [4, -7, 5, 4]
for i in range(1, len(my_list)):
  to_swap = my_list[i]
  j = i - 1
  while j >= 0 and my_list[j] > to_swap:
    my_list[j + 1] = my_list[j]
    j -= 1
  my_list[j + 1] = to_swap

Una vez más, esta solución se tomó prestada del pseudocódigo en Algorithmist . Funciona comenzando en el primer índice (es decir i = 1) y comparando ese elemento con el elemento en el índice cero (es decir j < 1). Si se necesita un intercambio, los elementos se intercambian. En este caso, el segundo elemento es más pequeño que el primero, por lo que terminamos con el siguiente cambio:

1
2
[4, -7, 5, 4]  # Initial list
[-7, 4, 5, 4]  # After the first iteration

A continuación, el algoritmo se mueve al segundo índice (es decir i = 2) y comienza a trabajar hacia atrás (es decir j < 2) para encontrar dónde encaja ese elemento en los dos primeros elementos. En este caso, 5 ya es mayor que 4, por lo que no necesitamos realizar ningún intercambio:

1
2
3
[4, -7, 5, 4]  # Initial list
[-7, 4, 5, 4]  # After the first iteration
[-7, 4, 5, 4]  # After the second iteration

Finalmente, el bucle exterior se mueve al elemento final (es decir i = 3) y comienza a explorar la parte ordenada de la lista (es decir j < 3) para encontrar dónde va el elemento actual. En este caso, solo necesitamos verificar hasta el primer índice para averiguar dónde va 4. Como resultado, hemos terminado:

1
2
3
4
[4, -7, 5, 4]  # Initial list
[-7, 4, 5, 4]  # After the first iteration
[-7, 4, 5, 4]  # After the second iteration
[-7, 4, 4, 5]  # After the third iteration

Una cosa a tener en cuenta es que los intercambios ocurren cuando trabajamos hacia atrás a través de la lista ordenada. Por ejemplo, en la última iteración, descubrimos que 5 era más grande que 4. En ese momento, pudimos mover 5 a la última posición. La parte del código que maneja el intercambio es el bucle interno:

1
2
3
while j >= 0 and my_list[j] > to_swap:
  my_list[j + 1] = my_list[j]
  j -= 1

Mientras tanto, el bucle exterior rastrea el punto que divide la parte ordenada de la lista de la parte no ordenada y realiza la inserción:

1
2
3
4
5
for i in range(1, len(my_list)):
  to_swap = my_list[i]
  j = i - 1
  # Inner loop
  my_list[j + 1] = to_swap

Como probablemente pueda imaginar, hay más formas pitónicas de escribir esta solución. Por ejemplo, Haseeb Majid eligió dividir la lista por la mitad y volver a ensamblarla con el último elemento insertado en el lugar correcto. Si conoce alguna solución mejor, no dude en compartirla en los comentarios.

Ordenar una lista con orden de selección

Ahora que hemos visto el ordenamiento por inserción, no es demasiado exagerado comenzar a hablar sobre el ordenamiento por selección. Después de todo, el algoritmo es bastante similar. Sin embargo, en lugar de insertar un elemento en una sublista ordenada, buscamos el elemento más pequeño de la sublista sin clasificar y lo agregamos al final de la sublista ordenada. Para obtener más información, consulte la descripción del orden de selección en el repositorio de Programas de muestra . De lo contrario, aquí hay una buena visualización:

En términos de código real, aquí hay una posible solución en Python:

1
2
3
4
5
6
7
my_list = [4, -7, 5, 4]
for i in range(len(my_list)):
  min_index = i
  for j in range(i + 1, len(my_list)):
    if my_list[j] < my_list[min_index]:
      min_index = j
  my_list[i], my_list[min_index] = my_list[min_index], my_list[i]

Como de costumbre, basé esta solución en una solución escrita en C en la página de Wikipedia de clasificación de selección . Funciona partiendo del primer elemento de la lista (es decir i = 0) y buscando el elemento más pequeño de la lista (es decir j > 0). Después de un pase completo, sabemos que hemos encontrado el elemento más pequeño ( min_index = 1), por lo que podemos realizar nuestro intercambio. En la primera pasada, terminamos con el siguiente cambio:

1
2
[4, -7, 5, 4]  # Initial list
[-7, 4, 5, 4]  # After first iteration

Luego, movemos nuestro puntero principal (es decir i = 1) y comenzamos a buscar en la parte no ordenada de la lista (es decir j > 1) el valor más pequeño. En la segunda pasada, terminamos con el siguiente cambio:

1
2
3
[4, -7, 5, 4]  # Initial list
[-7, 4, 5, 4]  # After the first iteration
[-7, 4, 5, 4]  # After the second iteration

En este caso nada cambia porque 4 está en la posición correcta. Luego, en la siguiente iteración (es decir i = 2), buscamos en la parte sin clasificar de la lista (es decir j > 2) el valor restante más pequeño. En este caso, son los otros 4:

1
2
3
4
[4, -7, 5, 4]  # Initial list
[-7, 4, 5, 4]  # After the first iteration
[-7, 4, 5, 4]  # After the second iteration
[-7, 4, 4, 5]  # After the third iteration

En este punto, la lista está ordenada.

Naturalmente, la parte del código responsable de realizar la búsqueda es el bucle interno:

1
2
3
for j in range(i + 1, len(my_list)):
    if my_list[j] < my_list[min_index]:
      min_index = j

Mientras tanto, la porción de código responsable de rastrear el final de la lista ordenada y realizar el intercambio es el ciclo externo:

1
2
3
4
for i in range(len(my_list)):
  min_index = i
  # Inner loop
  my_list[i], my_list[min_index] = my_list[min_index], my_list[i]

Nuevamente, estoy seguro de que hay formas más inteligentes de escribir esta solución usando Python. Por ejemplo, se podría utilizar un enfoque de doble lista ( como lo hizo Haseeb ), que nos permite utilizar los minappendremovefunciones. En otras palabras, no hay bucles explícitos. Si conoce otras formas inteligentes de implementar el ordenamiento por selección, hágamelo saber en los comentarios.

Ordenar una lista con Bogosort

Ahora que hemos pasado por los tres algoritmos principales de clasificación de fuerza bruta, pensé que podríamos ver otro método de fuerza bruta: bogosort. En lugar de colocar continuamente un elemento en el lugar correcto en cada pasada, simplemente moveremos los elementos al azar hasta que clasifiquemos la lista. Así es como se vería en Python:

01
02
03
04
05
06
07
08
09
10
11
12
my_list = [4, -7, 5, 4]
 
import random
is_sorted = False
while not is_sorted:
  random.shuffle(my_list)
  last_item = my_list[0]
  is_sorted = True
  for item in my_list:
    if last_item > item:
      is_sorted = False
    last_item = item

Aquí, aprovechamos un paquete útil llamado randomque tiene una utilidad para mezclar listas. Para empezar, barajamos la lista asumiendo que la lista aún no está ordenada. Luego, verificamos si la lista está ordenada. Si es así, hemos terminado. De lo contrario, repetimos el ciclo.

Para ver esto en acción, veamos lo que podría suceder. Primero, barajaremos la lista:

1
2
[4, -7, 5, 4]  # Initial list
[5, 4, 4, -7]  # After first iteration

Como podemos ver, la lista no está ordenada. Lo confirmaremos comprobando cada par de valores en orden secuencial. Si no vemos ningún par fuera de servicio, paramos. Sin embargo, en este caso, 5 es mayor que 4, por lo que sabemos que la lista no está ordenada. Como resultado, volvemos a mezclar:

1
2
3
[4, -7, 5, 4]  # Initial list
[5, 4, 4, -7]  # After first iteration
[-7, 4, 5, 4]  # After second iteration

Como podemos imaginar, este proceso podría durar mucho tiempo. Aquí hay una secuencia real de permutaciones que obtuve cuando ejecuté la solución anterior:

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

Ahora, eso es solo por cuatro elementos. Imagínese cuánto tiempo podría llevar esto con aún más elementos. O mejor aún, no lo imagines en absoluto. Aquí hay una visualización del algoritmo que falla repetidamente para 100 elementos:

Afortunadamente, hay una pequeña mejora que se puede realizar en este algoritmo. En lugar de generar estados al azar, podríamos realizar un seguimiento de los estados que ya hemos creado y solo generar estados nuevos. De esa forma, no perderíamos el tiempo generando estados repetidos.

Desafortunadamente, la versión determinista de bogosort sigue siendo muy, muy mala. Específicamente, el algoritmo es O (N!). En nuestro caso de cuatro elementos, ¡tendríamos el peor tiempo de ejecución de comprobar 4! (24) estados. Mientras tanto, todos los algoritmos mencionados hasta ahora operan en O (N 2 ) lo que significa, en el peor de los casos, 16 comparaciones. Como probablemente pueda imaginar, esta es una mala noticia para bogosort a largo plazo:

norteComparaciones O (N 2 )Comparaciones O (N!)
4dieciséis24
525120
636720
7495040
86440320

Para divertirnos, veremos el rendimiento de estos algoritmos en la siguiente sección.

Actuación

Para probar cada solución, necesitaremos crear algunas cadenas:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
dieciséis
17
18
19
20
21
22
23
24
25
26
27
28
29
30