
_START_ARTICLE_
Shellsortering
_START_PARAGRAPH_
shellsortering (engelsk: Shellsort) er en sorteringsalgoritme som blev opdaget af Donald Shell i 1959. Algoritmen kan ses som en forbedring af andre, enklere, sorteringsalgoritmer, typisk indsættelsessortering. Det der gør shellsortering mere effektiv end normal indsættelsessortering er at algoritmen tillader sammenligning mellem to elementer, som ligger langt fra hinanden. Algoritmens afviklingstid er voldsomt afhængig af den anvendte gapsekvens. For mange praktiske varianter er deres tidskompleksitet et uløst problem.
_START_SECTION_
Eksempelkode
_START_PARAGRAPH_
Med brug af Marcin Ciuras gapsekvens, med en indre indsættelsessortering._NEWLINE_# Sort an array a[0...n-1].gaps = [701, 301, 132, 57, 23, 10, 4, 1]# Start with the largest gap and work down to a gap of 1foreach (gap in gaps){_NEWLINE_    # Do a gapped insertion sort for this gap size._NEWLINE_    # The first gap elements a[0..gap-1] are already in gapped order_NEWLINE_    # keep adding one more element until the entire array is gap sorted_NEWLINE_    for (i = gap; i < n; i += 1)_NEWLINE_    {_NEWLINE_        # add a[i] to the elements that have been gap sorted_NEWLINE_        # save a[i] in temp and make a hole at position i_NEWLINE_        temp = a[i]_NEWLINE_        # shift earlier gap-sorted elements up until the correct location for a[i] is found_NEWLINE_        for (j = i; j >= gap and a[j - gap] > temp; j -= gap)_NEWLINE_        {_NEWLINE_            a[j] = a[j - gap]_NEWLINE_        }_NEWLINE_        # put temp (the original a[i]) in its correct location_NEWLINE_        a[j] = temp_NEWLINE_    }}