Python-program til indsættelsessortering
Indsættelsessortering er en simpel sorteringsalgoritme, der fungerer, som vi sorterer spillekort i vores hænder.
Python-program til indsættelsessortering
Funktionen insertionSort tager en array-arr som input. Den beregner først længden af arrayet (n). Hvis længden er 0 eller 1, returnerer funktionen med det samme, da et array med 0 eller 1 element anses for allerede sorteret.
For arrays med mere end ét element fortsætter funktionen med at iterere over arrayet fra det andet element. Den tager det aktuelle element (omtalt som nøglen) og sammenligner det med elementerne i den sorterede del af arrayet, der går forud for det. Hvis nøglen er mindre end et element i den sorterede del, flytter funktionen dette element til højre, hvilket skaber plads til nøglen. Denne proces fortsætter, indtil den korrekte position for nøglen er fundet, og den indsættes derefter i den position.
Det medfølgende eksempel demonstrerer sorteringsprocessen ved hjælp af indsættelsessorteringsalgoritmen. Det indledende array [12, 11, 13, 5, 6] udsættes for funktionen insertionSort. Efter sortering skal arrayet være [5, 6, 11, 12, 13]. Koden udskriver det sorterede array som det endelige output.
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>> => 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)> |
Produktion:
Sorted array is: [5, 6, 11, 12, 13]
Tidskompleksitet: O(N 2 )
Hjælpeplads: O(1)
Se venligst hele artiklen vedr Indsættelsessortering for flere detaljer!
