文章基本信息

标题：Algorithm Engineering for Sorting and Searching, and All That (Invited Talk)
本地全文：下载
作者：Stefan Edelkamp
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：160
页码：2:1-2:3
DOI：10.4230/LIPIcs.SEA.2020.2
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We look at several proposals to engineer the set of fundamental searching and sorting algorithms. Aspects are improving locality of disk access and cache access, the efficiency tuning by reducing the number of branch mispredictions, and reducing at leading factors hidden in the Big-Oh notation. These studies in algorithm engineering, in turn, lead to exiting new algorithm designs. On the practical side, we will establish that efficient sorting and searching algorithms are in tight collaboration, as sorting is used for finding duplicates in disk-based search, and heap structures designed for efficient graph search can be exploited in classical and adaptive sorting. We indicate the effects of engineered sorting and searching for combined task and motion planning.
关键词：Sorting; Searching; Algorithm Engineering