[5-26]Sort Race
Date:2016-05-25
Title:
Speaker:
Time: May 26th, 2016, 10:00 am
Venue:
Abstract.
Sorting is perhaps the computing problem studied by most researchers and still very important in the age of big data. Various algorithms (insertsort, quicksort, mergesort, heapsort, shellsort, shellsort, smoothsort, splaysort, etc.) and implementation techniques have been used to demonstrate various algorithm design techniques. In this study, we focus on comparison based, internal sorting algorithms. We created 10 types of data of various sizes (up to 10 millions) for experiments and tested extensively best (claimed by original authors) implementations in a single setting. We discovered that quicksort is still the best sorting algorithm (and mergesort is the second best). Our implementations of quicksort and mergesort are quite different from other implementations reported in all textbooks or research articles, so that they not only work best for randomly generated data but also work very well for various types of nearly sorted data. This experiment can help the user to choose the best sorting algorithm for the hard sorting job at hand.
Short bio.
Professor Hantao Zhang received BS in Computer Science from Wuhan University in 1982, Doctor of Third Cycle in Informatics from University of Nancy I, France, in 1985, and PhD in Computer Science from Rensselaer Polytechnic Institute (RPI) in 1988. Professor Zhang has been a faculty member of Computer Science at University of Iowa since 1988 and is the recipient of numerous NSF awards, including the prestigious NSF Career Award. He has many years of experiences teaching algorithms and his research is in the field of automated reasoning. In 2015, he is the recipient of the Skolem Award by CADE (International Conference on Automated Deduction) as one of his papers has passed the test of time, by being a most influential paper in the field.