Shell sort

Från Wikipedia
Hoppa till navigering Hoppa till sök
Shell sort
Sorting shellsort anim.gif
Sorteringsalgoritm, in-place-algoritm, parvis jämförelse Redigera
Undertyp avalgoritm
 • kombinatorisk algoritm
  • sorteringsalgoritm Redigera
Upp­täc­ka­re eller upp­fin­na­reDonald Shell Redigera
Upp­täckts­da­tum1959 Redigera
Defi­nie­ran­de formel Redigera
Tids­komp­lex­i­tet i värsta fall Redigera
Tids­komp­lex­i­tet i bästa fall Redigera
Tids­komp­lex­i­tet i medel Redigera
Rums­komp­lex­i­tet i värsta fall Redigera

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[redigera | redigera wikitext]

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;
    }
}