thumb|shellsortering, trin for trin shellsortering () er en sorteringsalgoritme som blev opdaget af Donald Shell i 1959.Nogle ældre lærebøger og kilder kalder algortimen "Shell-Metzner" efter Marlene Metzner Norton, men Metzner har udtalt at hun intet havde at men den gøre: "I had nothing to do with the sort, and my name should never have been attached to it." Se 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.
Eksempelkode Med brug af Marcin Ciuras gapsekvens, med en indre indsættelsessortering.
# 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 1 foreach (gap in gaps) { # Do a gapped insertion sort for this gap size. # The first gap elements a[0..gap-1] are already in gapped order # keep adding one more element until the entire array is gap sorted for (i = gap; i < n; i += 1)
# add a[i] to the elements that have been gap sorted # save a[i] in temp and make a hole at position i temp = a[i] # shift earlier gap-sorted elements up until the correct location for a[i] is found for (j = i; j >= gap and a[j - gap] > temp; j -= gap)
a[j] = a[j - gap]
# put temp (the original a[i]) in its correct location a[j] = temp
Referencer
Eksterne henvisninger
Open Problem Garden Samling af uløste problemer inden for matematik
Kategori:Sorteringsalgoritmer