L'ordenació per inserció és un algorisme d'ordenació senzill que funciona de la mateixa manera que classifiquem les cartes a les nostres mans.
Programa Python per a l'ordenació d'inserció
La funció insertionSort pren com a entrada una matriu arr. Primer calcula la longitud de la matriu (n). Si la longitud és 0 o 1, la funció retorna immediatament ja que una matriu amb 0 o 1 element es considera que ja està ordenada.
Per a matrius amb més d'un element, la funció passa a iterar sobre la matriu començant pel segon element. Pren l'element actual (anomenat clau) i el compara amb els elements de la part ordenada de la matriu que el precedeixen. Si la clau és més petita que un element de la part ordenada, la funció desplaça aquest element cap a la dreta, creant espai per a la clau. Aquest procés continua fins que es troba la posició correcta per a la clau, i després s'insereix en aquesta posició.
L'exemple proporcionat mostra el procés d'ordenació mitjançant l'algorisme d'ordenació per inserció. La matriu inicial [12, 11, 13, 5, 6] està sotmesa a la funció insertionSort. Després d'ordenar, la matriu hauria de ser [5, 6, 11, 12, 13]. El codi imprimeix la matriu ordenada com a sortida final.
mides de lletra en làtex
Python
estructures de dades en java
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)> |
>
>
Sortida:
Sorted array is: [5, 6, 11, 12, 13]>
Complexitat temporal: O(N2)
Espai auxiliar: O(1)
Consulteu l'article complet sobre Ordenació d'inserció per a més detalls!