¿Qué es ordenar?

Ordenar se refiere al proceso de organizar los datos en un orden específico, normalmente ascendente o descendente, en función de una relación lineal entre los elementos de datos.

¿Por qué necesitamos ordenar?

La clasificación es crucial cuando se trabaja con datos estructurados porque permite una recuperación eficiente de los datos, simplifica el análisis de los datos y mejora la gestión general de los datos.

Algoritmos de clasificación

Esta publicación cubre los siguientes algoritmos de clasificación: clasificación por burbujas, clasificación por selección, clasificación por inserción, clasificación por combinación y clasificación rápida.

Ordenar burbujas

Bubble Sort recorre repetidamente la matriz, comparando elementos adyacentes e intercambiándolos si están en el orden incorrecto. Este proceso continúa hasta que se ordena la matriz, con los elementos más grandes "burbujeando" hasta el final.

Algoritmo

Paso 1: Comenzar
Paso 2: i = 0
Paso 3: si i Paso 4: j = 0
Paso 5: si j Paso 6: si matriz[j] > matriz[j 1], vaya al Paso 7; de lo contrario, vaya al Paso 8
Paso 7: Intercambiar matriz[j] y matriz[j 1]
Paso 8: incremento j; ir al paso 5
Paso 9: incremento i; ir al paso 3
Paso 10: Finalizar

Código

def bubble_sort(arr):
    print("Array Before Sorting: ", end='')
    print(arr)
    for i in range(len(arr)):
        for j in range(len(arr)-i-1):
            if arr[j] > arr[j 1]:
                arr[j], arr[j 1] = arr[j 1], arr[j]

    print("Array After Sorting: ", end='')
    print(arr)

# Main
bubble_sort([7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6])

Complejidad del tiempo

Mejor caso: O(n)
Caso promedio: O(n^2)
Peor caso: O(n^2)

Orden de selección

La ordenación por selección encuentra el valor más pequeño en la parte no ordenada de la matriz y lo coloca al principio de esa parte.

Algoritmo

Paso 1: comenzar
Paso 2: i = 0
Paso 3: si i Paso 4: valor_mínimo = i; j = yo 1
Paso 5: si j Paso 6: si matriz[valor_mínimo] > matriz[j], vaya al Paso 7; de lo contrario, vaya al Paso 8
Paso 7: valor_mínimo = j
Paso 8: incremento j; ir al paso 5
Paso 9: intercambiar matriz[valor_mínimo] y matriz[i]
Paso 10: incremento i; ir al paso 3
Paso 11: Fin

Código

def selection_sort(arr):
    print("Array Before Sorting: ", end='')
    print(arr)
    for i in range(len(arr) - 1):
        min_val = i
        for j in range(i   1, len(arr)):
            if arr[j] 




  
  
  Complejidad del tiempo


Mejor caso: O(n^2)

Caso promedio: O(n^2)

Peor caso: O(n^2) 


  
  
  Orden de inserción


La ordenación por inserción construye la matriz ordenada un elemento a la vez tomando cada elemento de la parte no ordenada e insertándolo en la posición correcta en la parte ordenada.


  
  
  Algoritmo


Paso 1: Comenzar

Paso 2: i = 1

Paso 3: si i 
Paso 4: clave = arr[i]

Paso 5: j = i - 1

Paso 6: si j >= 0 y arr[j] > tecla, vaya al Paso 7; de lo contrario, vaya al paso 10

Paso 7: arreglo[j 1] = arreglo[j]

Paso 8: disminuya j en 1

Paso 9: vaya al Paso 6

Paso 10: arr[j 1] = clave

Paso 11: incrementa i en 1; ir al paso 3

Paso 12: Finalizar


  
  
  Código




def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        while j >= 0 and arr[j] > key:
            arr[j   1] = arr[j]
            j -= 1

        arr[j   1] = key

# Main
arr = [7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6]
print("Array Before Sorting:", arr)
insertion_sort(arr)
print("Array After Sorting:", arr)





  
  
  Complejidad del tiempo


Mejor caso: O(n)

Caso promedio: O(n^2)

Peor caso: O(n^2) 


  
  
  Combinar ordenar


Merge Sort es un algoritmo de divide y vencerás que divide recursivamente la matriz en submatrices más pequeñas, las clasifica y luego las vuelve a fusionar.


  
  
  Algoritmo


Algoritmo de ordenación por fusión


Paso 1: comenzar

Paso 2: Si longitud (matriz) 
Paso 3: punto_medio = longitud (matriz) // 2

Paso 4: mitad_izquierda = matriz[:punto_medio]

Paso 5: mitad_derecha = matriz[punto_medio:]

Paso 6: sorted_left = merge_sort(left_half)

Paso 7: sorted_right = merge_sort(right_half)

Paso 8: devolver la combinación (sorted_left, sorted_right)

Paso 9: Finalizar

Función de fusión


Paso 1: comenzar

Paso 2: sorted_merge = []

Paso 3: l = 0, r = 0

Paso 4: si l 
Paso 5: si izquierda[l] 
Paso 6: agregue left[l] a sorted_merge; incrementar l en 1

Paso 7: agregue right[r] a sorted_merge; incrementar r en 1

Paso 8: vaya al Paso 4

Paso 9: si l 
Paso 10: agregue left[l] a sorted_merge; incrementar l en 1 

Paso 11: vaya al Paso 9

Paso 12: si r 
Paso 13: agregue right[r] a sorted_merge; incrementar r en 1

Paso 14: vaya al Paso 12

Paso 15: Devolver sorted_merge

Paso 16: Finalizar


  
  
  Código




def merge(left, right):
    sorted_merge = []
    l = r = 0
    while l 




  
  
  Complejidad del tiempo


Mejor caso: O(n log n)

Caso promedio: O(n log n)

Peor caso: O(n log n) 


  
  
  Ordenación rápida


Quick Sort es un algoritmo de clasificación eficiente e in situ que utiliza un enfoque de divide y vencerás. Selecciona un elemento pivote y divide la matriz alrededor del pivote de modo que los elementos menores que el pivote estén a su izquierda y los elementos mayores que el pivote estén a su derecha. Luego, este proceso se aplica de forma recursiva a las submatrices.


  
  
  Algoritmo


Clasificación rápida


Paso 1: comenzar

Paso 2: Si es bajo 
Paso 3: pivot_index = partición(arr, bajo, alto)

Paso 4: clasificación rápida (arr, bajo, índice_pivote - 1)

Paso 5: clasificación rápida (arr, pivot_index 1, alto)

Paso 6: Finalizar 

Función de partición


Paso 1: comenzar

Paso 2: pivote = arr[alto]

Paso 3: izquierda = baja, derecha = alta - 1

Paso 4: si izquierda 
Paso 5: si arr[izquierda] > pivote y arr[derecha] 
Paso 6: si arr[left] 
Paso 7: si arr[right] >= pivote, disminuya hacia la derecha

Paso 8: vaya al Paso 4

Paso 9: intercambie arr[izquierda] y arr[alto]

Paso 10: regresar a la izquierda

Paso 11: Finalizar 


  
  
  Código




def partition(arr, low, high):
    pivot = arr[high]
    left = low
    right = high - 1
    while left  pivot and arr[right] = pivot:
            right -= 1
    arr[left], arr[high] = arr[high], arr[left]
    return left

def quicksort(arr, low, high):
    if low 




  
  
  Complejidad del tiempo


Mejor caso: O(n log n)

Caso promedio: O(n log n)

Peor caso: O(n^2)