Python - Algoritmos de clasificación

La clasificación se refiere a organizar los datos en un formato particular. El algoritmo de clasificación especifica la forma de organizar los datos en un orden particular. Los órdenes más comunes están en orden numérico o lexicográfico.

La importancia de la clasificación radica en el hecho de que la búsqueda de datos se puede optimizar a un nivel muy alto, si los datos se almacenan de forma ordenada. La clasificación también se utiliza para representar datos en formatos más legibles. A continuación, vemos cinco implementaciones de clasificación en Python.

Ordenamiento de burbuja
Combinar ordenar
Tipo de inserción
Tipo de concha
Orden de selección

Ordenamiento de burbuja

Es un algoritmo basado en comparación en el que se compara cada par de elementos adyacentes y los elementos se intercambian si no están en orden.

def bubblesort(list):

# Swap the elements to arrange in order
    for iter_num in range(len(list)-1,0,-1):
        for idx in range(iter_num):
            if list[idx]>list[idx+1]:
                temp = list[idx]
                list[idx] = list[idx+1]
                list[idx+1] = temp


list = [19,2,31,45,6,11,121,27]
bubblesort(list)
print(list)

Cuando se ejecuta el código anterior, produce el siguiente resultado:

[2, 6, 11, 19, 27, 31, 45, 121]

Combinar ordenar

Merge sort primero divide la matriz en mitades iguales y luego las combina de manera ordenada.

def merge_sort(unsorted_list):
    if len(unsorted_list) <= 1:
        return unsorted_list
# Find the middle point and devide it
    middle = len(unsorted_list) // 2
    left_list = unsorted_list[:middle]
    right_list = unsorted_list[middle:]

    left_list = merge_sort(left_list)
    right_list = merge_sort(right_list)
    return list(merge(left_list, right_list))

# Merge the sorted halves

def merge(left_half,right_half):

    res = []
    while len(left_half) != 0 and len(right_half) != 0:
        if left_half[0] < right_half[0]:
            res.append(left_half[0])
            left_half.remove(left_half[0])
        else:
            res.append(right_half[0])
            right_half.remove(right_half[0])
    if len(left_half) == 0:
        res = res + right_half
    else:
        res = res + left_half
    return res

unsorted_list = [64, 34, 25, 12, 22, 11, 90]

print(merge_sort(unsorted_list))

Cuando se ejecuta el código anterior, produce el siguiente resultado:

[11, 12, 22, 25, 34, 64, 90]

Tipo de inserción

La ordenación por inserción implica encontrar el lugar correcto para un elemento dado en una lista ordenada. Entonces, al principio, comparamos los dos primeros elementos y los ordenamos comparándolos. Luego, elegimos el tercer elemento y encontramos su posición adecuada entre los dos elementos ordenados anteriores. De esta manera, vamos agregando gradualmente más elementos a la lista ya ordenada colocándolos en su posición adecuada.

def insertion_sort(InputList):
    for i in range(1, len(InputList)):
        j = i-1
        nxt_element = InputList[i]
# Compare the current element with next one
		
        while (InputList[j] > nxt_element) and (j >= 0):
            InputList[j+1] = InputList[j]
            j=j-1
        InputList[j+1] = nxt_element

list = [19,2,31,45,30,11,121,27]
insertion_sort(list)
print(list)

Cuando se ejecuta el código anterior, produce el siguiente resultado:

[2, 11, 19, 27, 30, 31, 45, 121]

Tipo de concha

Shell Sort implica clasificar los elementos que están alejados de los demás. Ordenamos una gran sublista de una lista determinada y seguimos reduciendo el tamaño de la lista hasta que todos los elementos estén ordenados. El siguiente programa encuentra la brecha equiparándola a la mitad de la longitud del tamaño de la lista y luego comienza a ordenar todos los elementos que contiene. Luego seguimos restableciendo el espacio hasta que se ordena toda la lista.

def shellSort(input_list):
    
    gap = len(input_list) // 2
    while gap > 0:

        for i in range(gap, len(input_list)):
            temp = input_list[i]
            j = i
# Sort the sub list for this gap

            while j >= gap and input_list[j - gap] > temp:
                input_list[j] = input_list[j - gap]
                j = j-gap
            input_list[j] = temp

# Reduce the gap for the next element

        gap = gap//2

list = [19,2,31,45,30,11,121,27]

shellSort(list)
print(list)

Cuando se ejecuta el código anterior, produce el siguiente resultado:

[2, 11, 19, 27, 30, 31, 45, 121]

Orden de selección

En el ordenamiento por selección comenzamos por encontrar el valor mínimo en una lista dada y lo movemos a una lista ordenada. Luego repetimos el proceso para cada uno de los elementos restantes en la lista sin clasificar. El siguiente elemento que ingresa a la lista ordenada se compara con los elementos existentes y se coloca en su posición correcta. Entonces, al final, se ordenan todos los elementos de la lista sin clasificar.

def selection_sort(input_list):

    for idx in range(len(input_list)):

        min_idx = idx
        for j in range( idx +1, len(input_list)):
            if input_list[min_idx] > input_list[j]:
                min_idx = j
# Swap the minimum value with the compared value

        input_list[idx], input_list[min_idx] = input_list[min_idx], input_list[idx]


l = [19,2,31,45,30,11,121,27]
selection_sort(l)
print(l)

Cuando se ejecuta el código anterior, produce el siguiente resultado:

[2, 11, 19, 27, 30, 31, 45, 121]

↰ Previous page Next page ↱