Insertion sort
Në shqip: Renditja me futje
ShpjegimiSQ
Insertion sort merr elementet një nga një dhe e fut secilin në vendin e duhur mes atyre që janë renditur tashmë. O(n²) në rastin e keq, por shumë e shpejtë kur lista është pothuajse e renditur.
EnglishEN
Insertion sort takes the items one at a time and slots each into the right place among those already sorted. O(n²) in the worst case, but very fast when the list is nearly sorted.
Si ta mendosh
Si t'i rendisësh letrat në dorë gjatë një loje: çdo letër të re e fut në vendin e saj.
Lexoje në anglisht
Like sorting cards in your hand during a game: each new card slides into its place.
Shembull kodipython
def insertion(v):
for i in range(1, len(v)):
x, j = v[i], i - 1
while j >= 0 and v[j] > x: v[j + 1] = v[j]; j -= 1
v[j + 1] = x