Shell sort
![]() | Den här artikeln behöver källhänvisningar för att kunna verifieras. (2023-07) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan. |
Shell Sort är en sorteringsalgoritm som uppfanns 1959 av Donald Shell. Algoritmen kan ses som en förbättring av andra enklare sorteringsalgoritmer, vanligtvis Insättningssortering. Det som gör att Shell Sort är effektivare än vanlig insättningssortering är att algoritmen tillåter jämförelse mellan två element som ligger långt ifrån varandra.
Exempelkod
Två funktioner "swapItems" och "compare" antas finnas tillgängliga för ett indexerbart objekt för att kasta om respektive göra jämförelser mellan objektets element.
void shellSort(int itemSize, swapFuncType swapItems, compFuncType compare) { itemSize--; int offset = itemSize / 2; while (offset > 0) { bool done = false; int limit = itemSize - offset; while (done == false) { int swap = 0; done = true; for (int i = 0; i <= limit; i++) { if (compare(i, i + offset)) { swapItems(i, i + offset); swap = i; done = false; } } limit = swap - offset; } offset = offset / 2; } }