Clasificación de burbujas, clasificación de combinación y clasificación rápida en Python

 

La clasificación de datos es probablemente la tarea más común que deberá realizar en sus programas. Como usuario de muchas aplicaciones en línea diferentes, está ordenando datos todos los días. Cada sitio web de compras le permite ordenar los datos. Por ejemplo, puede ordenar por precio más bajo, precio más alto, número de opiniones de clientes, puntuación media de opiniones, etc. No importa si es Amazon, Target, Barnes n Noble o la tienda de Lego. Es bastante fácil de hacer, todo lo que tenemos que hacer cuando el usuario es hacer clic en un enlace y nuestros datos se ordenan. El problema de clasificación se ha resuelto y todos los lenguajes de programación modernos tienen lógica de clasificación ya incorporada y son muy eficientes, por lo que no necesitará implementar su propio algoritmo de clasificación. Ayuda a comprender la teoría y la aplicación de algunas técnicas de clasificación comunes, y eso es lo que examinaremos ahora.

---

Ordenamiento de burbuja

La clasificación de burbujas es el primer algoritmo de clasificación sobre el que aprender. Es probable que no lo use en la naturaleza, ya que no es muy eficiente. Sin embargo, es fácil de entender y es una buena primera rutina de clasificación para aprender. Una clasificación de burbujas comienza comparando los dos primeros elementos entre sí para ver cuál es más grande. Si el primer elemento es más grande que el segundo, los dos elementos se intercambian. A continuación, la clasificación de burbujas avanza y realiza la misma operación en los dos elementos siguientes. Esto continúa hasta que se hayan inspeccionado todos los elementos de la matriz y el valor más grande se haya movido completamente hacia la derecha (parte superior) de la matriz. Luego, el algoritmo repite todo el proceso trabajando en todos los elementos excepto el anterior al último elemento y luego el anterior y así sucesivamente hasta que la matriz esté completamente ordenada.

Esta visualización es el primer paso del siguiente ejemplo de código.

• Más fácil de entender e implementar
• Rendimiento no muy bueno: O (n2)
• Otros algoritmos de clasificación son de mayor rendimiento
• Un buen primer algoritmo de clasificación para aprender

Código Python de clasificación de burbujas

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

def bubbleSort(data_to_sort):     for i in range(len(data_to_sort) - 1, 0, -1):         for j in range(i):             if data_to_sort[j] > data_to_sort[j + 1]:                 temp = data_to_sort[j]                 data_to_sort[j] = data_to_sort[j + 1]                 data_to_sort[j + 1] = temp           print(f'Iteration: {abs(i - len(data_to_sort))}', data_to_sort)     list_to_sort = [90, 50, 10, 20, 70, 60, 40, 30, 80] print('Original List: ', list_to_sort) bubbleSort(list_to_sort) print('Sorted List: ', list_to_sort)

Lista original: [90, 50, 10, 20, 70, 60, 40, 30, 80]
Iteración: 1 [50, 10, 20, 70, 60, 40, 30, 80, 90]
Iteración: 2 [10, 20, 50, 60, 40, 30, 70, 80, 90]
Iteración: 3 [10, 20, 50, 40, 30, 60, 70, 80, 90]
Iteración: 4 [10, 20, 40, 30, 50, 60, 70, 80, 90]
Iteración: 5 [10, 20, 30, 40, 50, 60, 70, 80, 90]
Iteración: 6 [10, 20, 30, 40, 50, 60, 70, 80, 90]
Iteración: 7 [10, 20, 30, 40, 50, 60, 70, 80, 90]
Iteración: 8 [10, 20, 30, 40, 50, 60, 70, 80, 90]
Lista ordenada: [10, 20, 30, 40, 50, 60, 70, 80, 90]

• Programa Python para Bubble Sort  (stechies)
• Programa Python para Bubble Sort  (tutorialgateway)
• Cómo se implementa la técnica de clasificación de burbujas en Python  (codespeedy)
• Algoritmo de clasificación de burbujas en Python  (programación en Python )
• Clasificación de burbujas de Python  (el programador loco)
• Ordenar una lista usando la clasificación de burbujas en Python  (codedope)

---

Combinar ordenar

La ordenación por fusión es un algoritmo de división y conquista que divide una matriz en piezas más pequeñas para operar. La ordenación por combinación tiene un mejor rendimiento que la ordenación por burbujas. La forma en que funciona es dividir sucesivamente una matriz hasta que solo haya matrices individuales de un elemento cada una. En ese punto, el algoritmo comienza a fusionar estas matrices de nuevo entre sí hasta que la matriz original se reconstruye completamente ordenada.

• Divide y conquistaras
• Rompe la matriz en piezas individuales
• Utiliza la recursividad para operar sobre los datos
• Fusiona las piezas de nuevo en la matriz en forma ordenada
• Tiene buen rendimiento en grandes cantidades de datos

Combinar código Python de ordenación

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

def mergesort(data_to_sort):     if len(data_to_sort) > 1:         mid = len(data_to_sort) // 2         leftarray = data_to_sort[:mid]         rightarray = data_to_sort[mid:]           mergesort(leftarray)         mergesort(rightarray)           i, j, k = 0, 0, 0           while i < len(leftarray) and j < len(rightarray):             if leftarray[i] < rightarray[j]:                 data_to_sort[k] = leftarray[i]                 i += 1             else:                 data_to_sort[k] = rightarray[j]                 j += 1             k += 1           while i < len(leftarray):             data_to_sort[k] = leftarray[i]             i += 1             k += 1           while j < len(rightarray):             data_to_sort[k] = rightarray[j]             j += 1             k += 1     list_to_sort = [90, 50, 10, 20, 70, 60, 40, 30, 80] print('Original List: ', list_to_sort) mergesort(list_to_sort) print('Sorted List: ', list_to_sort)

Lista original: [90, 50, 10, 20, 70, 60, 40, 30, 80]
Lista ordenada: [10, 20, 30, 40, 50, 60, 70, 80, 90]

• Tutorial de Merge Sort Python: una forma eficiente de ordenar  (simplifiedpython)
• Cómo ordenar elementos usando Merge sort en python  (spiderlabweb)
• Merge Sort: un tutorial rápido y una guía de implementación  (pythoncentral)
• Fusionar ordenación con implementación de código Python  (teachyourselfpython)
• Programa Python para fusionar dos listas y ordenarlas  (codevscolor)

---

Ordenación rápida

Quicksort también es un algoritmo de divide y vencerás que utiliza la recursividad para realizar su trabajo y, a menudo, tiene un mejor rendimiento que Merge Sort. Quicksort completa la clasificación de datos en su lugar en la matriz existente. La característica principal de Quicksort es la selección de un punto de pivote. El punto de pivote se usa para comenzar a particionar la matriz. El propósito del proceso de partición es mover los elementos que están en el lado incorrecto del valor de pivote y determinar el punto en el que dividir la matriz. En la clasificación rápida, hay un índice inferior y un índice superior. Comienza incrementando el índice inferior, siempre que sea menor que el índice superior, y hasta que encuentre un valor mayor que el valor pivote. Luego, el índice superior se disminuye hasta que encuentra un valor que es menor que el valor de pivote siempre que el índice superior sea mayor que el índice inferior. Cuando esos dos índices se cruzan, la matriz se divide. El valor de pivote se intercambia con el índice superior de modo que el lado izquierdo contiene valores debajo del pivote y el lado derecho contiene valores por encima del pivote. Este proceso continúa hasta que las matrices ya no se pueden dividir. Toda la lógica de clasificación se realiza en el paso de partición de clasificación rápida y los datos se clasifican en su lugar.

Código Python de clasificación rápida

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

def quickSort(data_to_sort, first, last):     if first < last:         pivotindex = partition(data_to_sort, first, last)         quickSort(data_to_sort, first, pivotindex - 1)         quickSort(data_to_sort, pivotindex + 1, last)     def partition(values, first, last):     pivotvalue = values[first]     lower = first + 1     upper = last     done = False     while not done:         while lower <= upper and values[lower] <= pivotvalue:             lower += 1         while values[upper] >= pivotvalue and upper >= lower:             upper -= 1         if upper < lower:             done = True         else:             temp = values[lower]             values[lower] = values[upper]             values[upper] = temp     temp = values[first]     values[first] = values[upper]     values[upper] = temp     return upper     list_to_sort = [90, 50, 10, 20, 70, 60, 40, 30, 80] print('Original List: ', list_to_sort) quickSort(list_to_sort, 0, len(list_to_sort) - 1) print('Sorted List: ', list_to_sort)

Lista original: [90, 50, 10, 20, 70, 60, 40, 30, 80]
Lista ordenada: [10, 20, 30, 40, 50, 60, 70, 80, 90]

• Cómo implementar QuickSort en Python  (educativo)
• La implementación de  ordenación rápida más corta en Python (finxter)
• Ejemplo de implementación de clasificación rápida en Python  (codezup)
• Algoritmo de clasificación rápida  ( bit de entrevista)
• QuickSort en Python  (coderwall)
• Clasificación rápida con Python  (stackoverflow)

Clasificación de burbujas, clasificación de combinación y clasificación rápida en el resumen de Python

Hay muchos algoritmos para ordenar datos. Echamos un vistazo a tres de los más comunes implementados en Python. Esos son el tipo de burbuja, el tipo de combinación y el tipo rápido. Cada uno tiene una complejidad algorítmica asociada a ellos y diversos grados de rendimiento y facilidad de uso.