Simple and Fast BlockQuicksort using Lomuto's Partitioning Scheme

Martin Aumüller, Nikolaj Hass

Publikation: Konference artikel i Proceeding eller bog/rapport kapitelKonferencebidrag i proceedingsForskningpeer review

Abstrakt

This paper presents simple variants of the BlockQuicksort algorithm described by Edelkamp and Weiss (ESA 2016). The simplification is achieved by using Lomuto's partitioning scheme instead of Hoare's crossing pointer technique to partition the input. To achieve a robust sorting algorithm that works well on many different input types, the paper introduces a novel two-pivot variant of Lomuto's partitioning scheme. A surprisingly simple twist to the generic two-pivot quicksort approach makes the algorithm robust. The paper provides an analysis of the theoretical properties of the proposed algorithms and compares them to their competitors. The analysis shows that Lomuto-based approaches incur a higher average sorting cost than the Hoare-based approach of BlockQuicksort. Moreover, the analysis is particularly useful to reason about pivot choices that suit the two-pivot approach. An extensive experimental study shows that, despite their worse theoretical behavior, the simpler variants perform as well as the original version of BlockQuicksort.
OriginalsprogEngelsk
Titel2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX)
Antal sider14
ForlagSociety for Industrial and Applied Mathematics
Publikationsdato2019
ISBN (Elektronisk)978-1-61197-549-9
DOI
StatusUdgivet - 2019

Fingeraftryk

Dyk ned i forskningsemnerne om 'Simple and Fast BlockQuicksort using Lomuto's Partitioning Scheme'. Sammen danner de et unikt fingeraftryk.

Citationsformater