Clasificación de algoritmos en Python

La clasificación se define como una disposición de los datos en un cierto orden. Las técnicas de clasificación se utilizan para organizar los datos (principalmente numéricos) en orden ascendente o descendente. Es un método utilizado para la representación de datos en un formato más comprensible. Es un área importante de las Ciencias de la Computación. Clasificar una gran cantidad de datos puede requerir una cantidad sustancial de recursos informáticos si los métodos que usamos para clasificar los datos son ineficientes. La eficiencia del algoritmo es proporcional al número de elementos que está atravesando. Para una pequeña cantidad de datos, un método de clasificación complejo puede ser más problemático de lo que vale. Por otro lado, para grandes cantidades de datos, queremos aumentar la eficiencia y la velocidad en la medida de lo posible. Ahora discutiremos las diversas técnicas de clasificación y las compararemos con respecto a su complejidad temporal.

Algunos de los ejemplos de clasificación de la vida real son:

• Directorio Telefónico:  Es un libro que contiene números telefónicos y direcciones de personas en orden alfabético.
• Diccionario: Es una gran colección de palabras junto con sus significados en orden alfabético.
• Lista de contactos: Es una lista de números de contacto de personas en orden alfabético en un teléfono móvil.

Antes de discutir los diferentes algoritmos utilizados para clasificar los datos que se nos proporcionan, debemos pensar en las operaciones que se pueden utilizar para el análisis de un proceso de clasificación. Primero, necesitamos comparar los valores para ver cuál es más pequeño y cuál es más grande para que puedan ordenarse, será necesario tener una forma organizada de comparar valores para ver si están en orden. 

Los diferentes tipos de orden son:

• Orden creciente: se dice que un conjunto de valores es de orden creciente cuando cada elemento sucesivo es mayor que su elemento anterior. Por ejemplo: 1, 2, 3, 4, 5. Aquí, la secuencia dada está en orden creciente.
• Orden Decreciente: Se dice que un conjunto de valores está en orden creciente cuando el elemento sucesivo es siempre menor que el anterior. Por ejemplo: 5, 4, 3, 2, 1. Aquí la secuencia dada está en orden decreciente.
• Orden no creciente: se dice que un conjunto de valores está en orden no creciente si cada i ^-ésimo elemento presente en la secuencia es mayor o igual que su (i-1) ^-ésimo elemento. Este orden ocurre siempre que hay números que se repiten. Por Ejemplo: 1, 2, 2, 3, 4, 5. Aquí 2 repetido dos veces.
• Orden no decreciente: se dice que un conjunto de valores está en orden no decreciente si cada i ^-ésimo elemento presente en la secuencia es menor o igual que su (i-1) ^-ésimo elemento. Este orden ocurre siempre que hay números que se repiten. Por Ejemplo: 5, 4, 3, 2, 2, 1. Aquí 2 repetido dos veces.

Técnicas de clasificación

Las diferentes implementaciones de técnicas de clasificación en Python son:

• Ordenamiento de burbuja
• Clasificación de selección
• Tipo de inserción

Ordenamiento de burbuja

Bubble Sort es un algoritmo de clasificación simple. Este algoritmo de clasificación compara repetidamente dos elementos adyacentes y los intercambia si están en el orden incorrecto. También se conoce como el tipo de hundimiento. Tiene una complejidad temporal de O(n ² ) en los escenarios promedio y peor y O(n) en el mejor escenario. La clasificación de burbujas se puede visualizar como una cola donde las personas se organizan intercambiándose entre sí para que todos puedan pararse en orden ascendente de su altura. O en otras palabras, comparamos dos elementos adyacentes y vemos si su orden es incorrecto, si el orden es incorrecto los intercambiamos. (es decir, arr[i] > arr[j] for 1 <= i < j <= s; donde s es el tamaño de la array, si la array va a estar en orden ascendente, y viceversa).

Ejemplo 

Aquí ordenamos la siguiente secuencia usando la ordenación de burbujas

Secuencia: 2, 23, 10, 1

Primera iteración

( 2, 23 , 10, 1) –> ( 2, 23 , 10, 1), Aquí se comparan los 2 primeros elementos y quedan igual porque ya están en orden ascendente.

(2, 23, 10 , 1) -> (2, 10, 23 , 1), Aquí se comparan e intercambian los elementos 2 y 3 (10 es menor que 23) según el orden ascendente.

(2, 10, 23, 1 ) -> (2, 10, 1, 23 ), Aquí se comparan e intercambian los elementos 3 y 4 (1 es menor que 23) según el orden ascendente

Al final de la primera iteración, el elemento más grande está en la posición más a la derecha que se ordena correctamente.

Segunda iteración

( 2, 10 , 1, 23) -> ( 2, 10, 1, 23), Aquí nuevamente, los 2 primeros elementos se comparan y siguen siendo los mismos porque ya están en orden ascendente.

(2, 10, 1 , 23) -> (2, 1, 10 , 23), Aquí los elementos 2 y 3 se comparan e intercambian (1 es menor que 10) en orden ascendente.

Al final de la segunda iteración, el segundo elemento más grande está en la posición adyacente al elemento más grande.

Tercera iteración

( 2, 1 , 10, 23) -> ( 1, 2 , 10, 23), Aquí los 2 primeros elementos se comparan y se intercambian en orden ascendente.

Los elementos restantes ya están ordenados en la primera y segunda Iteraciones. Después de las tres iteraciones, la array dada se ordena en orden ascendente. Entonces el resultado final es 1, 2, 10, 23.

Implementación de Bubble Sort:

# Python3 program for Bubble Sort Algorithm Implementation
def bubbleSort(arr):
     
    n = len(arr)
 
    # For loop to traverse through all
    # element in an array
    for i in range(n):
        for j in range(0, n - i - 1):
             
            # Range of the array is from 0 to n-i-1
            # Swap the elements if the element found
            #is greater than the adjacent element
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                 
# Driver code
 
# Example to test the above code
arr = [ 2, 1, 10, 23 ]
 
bubbleSort(arr)
 
print("Sorted array is:")
for i in range(len(arr)):
    print("%d" % arr[i])

Producción:

La array ordenada es:

1

2

10

23

Clasificación de selección

Esta técnica de clasificación encuentra repetidamente el elemento mínimo y lo clasifica en orden. Bubble Sort no ocupa ningún espacio de memoria adicional. Durante la ejecución de este algoritmo, se mantienen dos subarreglos, el subarreglo que ya está ordenado y el subarreglo restante que no está ordenado. Durante la ejecución de la ordenación por selección para cada iteración, el elemento mínimo del subarreglo no ordenado se organiza en el subarreglo ordenado. La ordenación por selección es un algoritmo más eficiente que la ordenación por burbuja. Ordenar tiene una Complejidad de Tiempo de O(n ² ) en los casos promedio, peor y mejor.

Ejemplo 

Aquí ordenamos la siguiente secuencia usando el ordenamiento por selección

Secuencia: 7, 2, 1, 6

(7, 2 , 1 , 6) –> ( 1 , 7, 2, 6), En la primera poligonal encuentra el elemento mínimo (es decir, 1) y se coloca en la 1ª posición.

(1, 7, 2 , 6) –> (1, 2 , 7, 6), En la segunda poligonal encuentra el segundo elemento mínimo (es decir, 2) y se coloca en la segunda posición.

(1, 2 , 7, 6 ) –> (1, 2, 6, 7 ), en la tercera poligonal encuentra el siguiente elemento mínimo (es decir, 6) y se coloca en la 3ra posición.

Después de las iteraciones anteriores, la array final está ordenada, es decir, 1, 2, 6, 7.

Implementación de clasificación de selección

# Selection Sort algorithm in Python
def selectionSort(array, size):
     
    for s in range(size):
        min_idx = s
         
        for i in range(s + 1, size):
             
            # For sorting in descending order
            # for minimum element in each loop
            if array[i] < array[min_idx]:
                min_idx = i
 
        # Arranging min at the correct position
        (array[s], array[min_idx]) = (array[min_idx], array[s])
 
# Driver code
data = [ 7, 2, 1, 6 ]
size = len(data)
selectionSort(data, size)
 
print('Sorted Array in Ascending Order is :')
print(data)

Producción:

La array ordenada en orden ascendente es:

[1, 2, 6, 7]

Tipo de inserción

Este algoritmo de clasificación mantiene una subarray que siempre está ordenada. Los valores de la parte no ordenada de la array se colocan en la posición correcta en la parte ordenada. Es más eficiente en la práctica que otros algoritmos como el ordenamiento por selección o el ordenamiento por burbuja. La Ordenación por Inserción tiene una Complejidad de Tiempo de O(n ² ) en el caso promedio y peor, y O(n) en el mejor de los casos.

Ejemplo 

Aquí ordenamos la siguiente secuencia usando el ordenamiento por inserción

Secuencia: 7, 2, 1, 6

( 7, 2 , 1, 6) -> ( 2, 7 , 1, 6), En la primera iteración, se comparan los primeros 2 elementos, aquí 2 es menor que 7 así que inserte 2 antes de 7.

(2, 7, 1 , 6) -> (2, 1, 7 , 6), en la segunda iteración se comparan los elementos 2 y 3, aquí 1 es menor que 7, así que inserte 1 antes de 7.

( 2, 1 , 7, 6) -> ( 1, 2 , 7, 6), después de la segunda iteración (1, 7) los elementos no están en orden ascendente, por lo que primero se organizan estos dos elementos. Entonces, inserte 1 antes de 2. 

(1, 2, 7, 6 ) -> (1, 2, 6, 7 ), durante esta iteración, los últimos 2 elementos se comparan y se intercambian después de intercambiar todos los elementos anteriores. 

Implementación de clasificación por inserción

# Creating a function for insertion sort algorithm
def insertion_sort(list1): 
   
        # Outer loop to traverse on len(list1) 
        for i in range(1, len(list1)): 
   
            a = list1[i] 
   
            # Move elements of list1[0 to i-1],
            # which are greater to one position
            # ahead of their current position 
            j = i - 1 
           
            while j >= 0 and a < list1[j]: 
                list1[j + 1] = list1[j] 
                j -= 1 
                 
            list1[j + 1] = a 
             
        return list1 
            
# Driver code
list1 = [ 7, 2, 1, 6 ] 
print("The unsorted list is:", list1) 
print("The sorted new list is:", insertion_sort(list1))

Producción:

La lista desordenada es: [7, 2, 1, 6]

La nueva lista ordenada es: [1, 2, 6, 7]