Programa Python para ordenación por inserción
La clasificación por inserción es un algoritmo de clasificación simple que funciona de la misma manera que clasificamos los naipes en nuestras manos.
Programa Python para ordenación por inserción
La función insertionSort toma una matriz arr como entrada. Primero calcula la longitud de la matriz (n). Si la longitud es 0 o 1, la función regresa inmediatamente ya que una matriz con 0 o 1 elemento se considera ya ordenada.
Para matrices con más de un elemento, la función procede a iterar sobre la matriz comenzando desde el segundo elemento. Toma el elemento actual (denominado clave) y lo compara con los elementos de la parte ordenada de la matriz que lo precede. Si la clave es más pequeña que un elemento en la parte ordenada, la función desplaza ese elemento hacia la derecha, creando espacio para la clave. Este proceso continúa hasta que se encuentra la posición correcta para la llave y luego se inserta en esa posición.
El ejemplo proporcionado demuestra el proceso de clasificación utilizando el algoritmo de clasificación por inserción. La matriz inicial [12, 11, 13, 5, 6] está sujeta a la función insertionSort. Después de ordenar, la matriz debe ser [5, 6, 11, 12, 13]. El código imprime la matriz ordenada como resultado final.
Pitón
def> insertionSort(arr):> > n> => len> (arr)> # Get the length of the array> > > if> n <> => 1> :> > return> # If the array has 0 or 1 element, it is already sorted, so return> > for> i> in> range> (> 1> , n):> # Iterate over the array starting from the second element> > key> => arr[i]> # Store the current element as the key to be inserted in the right position> > j> => i> -> 1> > while> j>> => 0> and> key # Move elements greater than key one position ahead arr[j+1] = arr[j] # Shift elements to the right j -= 1 arr[j+1] = key # Insert the key in the correct position # Sorting the array [12, 11, 13, 5, 6] using insertionSort arr = [12, 11, 13, 5, 6] insertionSort(arr) print(arr)> |
Producción:
Sorted array is: [5, 6, 11, 12, 13]
Complejidad del tiempo: O(N 2 )
Espacio auxiliar: O(1)
Consulte el artículo completo sobre Tipo de inserción ¡para más detalles!
