Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:
http://dx.doi.org/10.18419/opus-13112
Langanzeige der Metadaten
DC Element | Wert | Sprache |
---|---|---|
dc.contributor.author | Stober, Florian | - |
dc.contributor.author | Weiß, Armin | - |
dc.date.accessioned | 2023-06-02T13:23:25Z | - |
dc.date.available | 2023-06-02T13:23:25Z | - |
dc.date.issued | 2020 | de |
dc.identifier.issn | 1432-4350 | - |
dc.identifier.issn | 1433-0490 | - |
dc.identifier.other | 1850512418 | - |
dc.identifier.uri | http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-ds-131314 | de |
dc.identifier.uri | http://elib.uni-stuttgart.de/handle/11682/13131 | - |
dc.identifier.uri | http://dx.doi.org/10.18419/opus-13112 | - |
dc.description.abstract | MergeInsertion, also known as the Ford-Johnson algorithm, is a sorting algorithm which, up to today, for many input sizes achieves the best known upper bound on the number of comparisons. Indeed, it gets extremely close to the information-theoretic lower bound. While the worst-case behavior is well understood, only little is known about the average case. This work takes a closer look at the average case behavior. In particular, we establish an upper bound of nlogn-1.4005n+o(n) comparisons. We also give an exact description of the probability distribution of the length of the chain a given element is inserted into and use it to approximate the average number of comparisons numerically. Moreover, we compute the exact average number of comparisons for n up to 148. Furthermore, we experimentally explore the impact of different decision trees for binary insertion. To conclude, we conduct experiments showing that a slightly different insertion order leads to a better average case and we compare the algorithm to Manacher’s combination of merging and MergeInsertion as well as to the recent combined algorithm with (1,2)-Insertionsort by Iwama and Teruyama. | en |
dc.description.sponsorship | Deutsche Forschungsgemeinschaft | de |
dc.description.sponsorship | Projekt DEAL | de |
dc.language.iso | en | de |
dc.relation.uri | doi:10.1007/s00224-020-09987-4 | de |
dc.rights | info:eu-repo/semantics/openAccess | de |
dc.rights.uri | https://creativecommons.org/licenses/by/4.0/ | de |
dc.subject.ddc | 004 | de |
dc.title | On the average case of MergeInsertion | en |
dc.type | article | de |
dc.date.updated | 2023-05-14T22:11:38Z | - |
ubs.fakultaet | Informatik, Elektrotechnik und Informationstechnik | de |
ubs.institut | Institut für Formale Methoden der Informatik | de |
ubs.publikation.seiten | 1197-1224 | de |
ubs.publikation.source | Theory of computing systems 64 (2020), S. 1197-1224 | de |
ubs.publikation.typ | Zeitschriftenartikel | de |
Enthalten in den Sammlungen: | 05 Fakultät Informatik, Elektrotechnik und Informationstechnik |
Dateien zu dieser Ressource:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
s00224-020-09987-4.pdf | 1,95 MB | Adobe PDF | Öffnen/Anzeigen |
Diese Ressource wurde unter folgender Copyright-Bestimmung veröffentlicht: Lizenz von Creative Commons