Shellsortering

shellsortering (engelsk: Shellsort) er en sorteringsalgoritme som blev opdaget af Donald Shell i 1959.[1][2] Algoritmen kan ses som en forbedrin

Shellsortering
shellsortering, trin for trin

shellsortering (engelsk: Shellsort) er en sorteringsalgoritme som blev opdaget af Donald Shell i 1959.[1][2] 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.[3][4]

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

  1. ^ Shell, D. L. (1959). "A High-Speed Sorting Procedure" (PDF). Communications of the ACM. 2 (7): 30-32. doi:10.1145/368370.368387. Arkiveret fra originalen (PDF) 30. august 2017. Hentet 26. november 2017.
  2. ^ 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 "Shell sort". National Institute of Standards and Technology. Hentet 17. juli 2007.
  3. ^ "Shell sort". National Institute of Standards and Technology. Hentet 17. juli 2007.
  4. ^ Knuth, Donald E. (1997). "Shell's method". The Art of Computer Programming. Volume 3: Sorting and Searching (2nd udgave). Reading, Massachusetts: Addison-Wesley. s. 83-95. ISBN 0-201-89685-0.

Eksterne henvisninger

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.