Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:
http://dx.doi.org/10.18419/opus-10244
Autor(en): | Stober, Florian |
Titel: | Average case considerations for Mergelnsertion |
Erscheinungsdatum: | 2018 |
Dokumentart: | Abschlussarbeit (Bachelor) |
Seiten: | 44 |
URI: | http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-ds-102614 http://elib.uni-stuttgart.de/handle/11682/10261 http://dx.doi.org/10.18419/opus-10244 |
Zusammenfassung: | The MergeInsertion Algorithm, also known as Ford-Johnson Algorithm, is a sorting algorithm that was discovered by Ford and Johnson in 1959. It was later described by Knuth as MergeInsertion. The algorithm can be divided into three steps: First pairs of elements are compared. Then the larger half is sorted using MergeInsertion. And last the remaining elements are inserted. The most interesting property of this algorithm is the number of comparisons it requires, which is close to the information-theoretic lower bound. While the worst-case behavior is well understood, only little is known about the average-case. This thesis takes a closer look at the average case behavior. An upper bound of n log n − 1.4005n + o(n) is established. For small n the exact values are calculated. Furthermore the impact of different approaches to binary insertion on the number of comparisons is explored. To conclude we perform some experiments to evaluate different approaches on improving MergeInsertion. |
Enthalten in den Sammlungen: | 05 Fakultät Informatik, Elektrotechnik und Informationstechnik |
Dateien zu dieser Ressource:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
Bachelorarbeit_MergeInsertion_2018-11-28.pdf | 610,62 kB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repositorium sind urheberrechtlich geschützt.