Sorting applications Sorting algorithms are essential in a broad variety of applications Organize an MP3 library. Display Google PageRank results. List RSS news items in reverse chronological order. Find the median. Find the closest pair. Binary search in a database. Identify statistical outliers. Find duplicates in a mailing list. Data compression. Computer graphics. Computational biology. Supply chain management. Load balancing on a parallel computer. ... Advanced Topics in Sorting anhtt-fit@mail.hut.edu.vn dungct@it-hut.edu.vn http://www.4shared.com/file/79096214/fb2ed224/lect01.html Sorting algorithms Which algorithm to use? Many sorting algorithms to choose from Internal sorts Insertion sort, selection sort, bubblesort, shaker sort. Quicksort, mergesort, heapsort, samplesort, shellsort. Solitaire sort, red-black sort, splaysort, Dobosiewicz sort, psort, ... External sorts Poly-phase mergesort, cascade-merge, oscillating sort. Radix sorts Distribution, MSD, LSD. 3-way radix quicksort. Parallel sorts Bitonic sort, Batcher even-odd sort. Smooth sort, cube sort, column sort. GPUsort. Applications have diverse attributes Stable? Multiple keys? Deterministic? Keys all distinct? Multiple key types? Linked list or arrays? Large or small records? Is your file randomly ordered? Need guaranteed performance? Cannot cover all combinations of attributes. 1 Case study 1 Problem Sort a huge randomly-ordered file of small records. Example Process transaction records for a phone company. Which sorting method to use? 1. Quicksort: YES, it's designed for this problem 2. Insertion sort: No, quadratic time for randomly- Case study 2 Problem Sort a huge file that is already almost in order. Example Re-sort a huge database after a few changes. Which sorting method to use? 1. Quicksort: probably no, insertion simpler and faster 2. Insertion sort: YES, linear t