Sortare prin inserție este un algoritm simplu de sortare care funcționează așa cum sortăm cărțile de joc în mâinile noastre.
Programul Python pentru sortarea prin inserare
Funcția insertionSort ia ca intrare o matrice arr. Mai întâi calculează lungimea matricei (n). Dacă lungimea este 0 sau 1, funcția revine imediat, deoarece un tablou cu 0 sau 1 element este considerat deja sortat.
Pentru tablourile cu mai mult de un element, funcția continuă să itereze peste matrice pornind de la al doilea element. Acesta ia elementul curent (denumit cheie) și îl compară cu elementele din porțiunea sortată a matricei care îl precedă. Dacă cheia este mai mică decât un element din porțiunea sortată, funcția mută acel element la dreapta, creând spațiu pentru cheie. Acest proces continuă până când se găsește poziția corectă pentru cheie și apoi este introdusă în acea poziție.
Exemplul oferit demonstrează procesul de sortare folosind algoritmul de sortare prin inserare. Matricea inițială [12, 11, 13, 5, 6] este supusă funcției insertionSort. După sortare, matricea ar trebui să fie [5, 6, 11, 12, 13]. Codul tipărește matricea sortată ca rezultat final.
flux de filtru java
Piton
sortarea unui arraylist 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>>>> 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)> |
>
>
Ieșire:
Sorted array is: [5, 6, 11, 12, 13]>
Complexitatea timpului: O(N2)
Spațiu auxiliar: O(1)
Vă rugăm să consultați articolul complet pe Sortare prin inserare pentru mai multe detalii!