Python programma ievietošanas kārtošanai
Ievietošanas kārtošana ir vienkāršs šķirošanas algoritms, kas darbojas tāpat kā mēs savās rokās kārtojam spēļu kārtis.
Python programma ievietošanas kārtošanai
Funkcija insertionSort kā ievadi izmanto masīvu arr. Vispirms tiek aprēķināts masīva garums (n). Ja garums ir 0 vai 1, funkcija nekavējoties atgriežas, jo tiek uzskatīts, ka masīvs ar 0 vai 1 elementu jau ir sakārtots.
Masīviem ar vairāk nekā vienu elementu funkcija turpina atkārtot masīvu, sākot no otrā elementa. Tas ņem pašreizējo elementu (saukts par atslēgu) un salīdzina to ar elementiem sakārtotajā masīva daļā, kas atrodas pirms tā. Ja atslēga ir mazāka par elementu kārtotajā daļā, funkcija pārvieto šo elementu pa labi, radot vietu atslēgai. Šis process turpinās, līdz tiek atrasta pareizā atslēgas pozīcija, un pēc tam tā tiek ievietota šajā pozīcijā.
Sniegtais piemērs parāda kārtošanas procesu, izmantojot ievietošanas kārtošanas algoritmu. Sākotnējais masīvs [12, 11, 13, 5, 6] tiek pakļauts funkcijai insertionSort. Pēc šķirošanas masīvam jābūt [5, 6, 11, 12, 13]. Kods izdrukā sakārtoto masīvu kā galīgo izvadi.
Python
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>>> |
