Shell sort

Shell sort algoritm färgfält

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.

Pseudokod

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