报告题目：Sort Race
报告日期及时间：5月18日周三15:00
报告地点：B403
报告人： 张瀚涛教授
报告人单位： The University of Iowa
报告人简介： 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.
报告摘要： 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.
邀请人： 梁意文教授
