10th CoRe Seminar
Date and time: | 2021.05.24 Mon. 10:00-12:00
|
---|---|
Venue: | Online |
Speaker: | TERUYAMA, Junichi (U. Hyogo, Group B01) |
Title: | Sorting algorithms with small number of comparisons |
Summary: | Sorting is one of the most fundamental tasks in computer science. A majority of existing sorting algorithms are so-called "comparison-based sorting", whose basic operation is a comparison of two input elements.Its time-complexity is evaluated by the number of comparisons executed during the computation.Although researches on identifying the minimum number of comparisons have been performed more than 50 years, the optimal number of comparisons even for sorting 16 elements is still open.In this talk, I will give a brief survey on the research on this line.I will also describe algorithms which nearly match a theoretical lower bound asymptotically.
|
Update:2021.05.11