2004ioi讲义.ppt

12 Jun 2004 IOI/ACM/Supercom Session 7 IOI/ACM/Supercom 2004 Training Session 7 Dr Kan Min-Yen Topics and outline Sorting Computer Arithmetic and Algebra Invariants and Number Theory Sorting Problems and Parameters Comparison-based sorting Non-comparison-based What sort of problems? Sorting is usually not the end goal, but a prerequisite _________ _________ _________ _________ _________ Two properties of sorting Stable Items with the same value are ordered in the same way after the sort as they were before Important for doing ____________ sorts E.g., sorting by First name, Last name In-place: sorts the items without needing extra space ___________________________________ Comparison-based sort Based on comparing two items Many variants, but not the only way to sort Discuss only the important ones for programming contests Selection, Insertion, Merge and Quick Comparison Sorts Comparison Sort Animation: /TMCM/java/xSortLab/ Selection Algo: find min or max of unsorted portion Heapsort: is selection sort with heap data structure Remember: ____________________ Insertion Algo: insert unsorted item in sorted array Remember: ____________________ Comparison Sorts Merge Idea: divide and conquer, recursion Algo: merge two sorted arrays in linear time Remember: _________________________ Quick Idea: randomization, pivot Algo: divide problem to smaller and larger half based on a pivot Remember: ________________________! A problem with sorting as its core may not be best solved with generic tool. Think before using a panacea like Quicksort. Miscellaneous sort Most sorting relies on comparisons between two items. Proven to be Θ(n log n) Example: sort an array of distinct integers ranged 1-k We’ll go over Radix sort Counting sort What is radix? Radix is the same as base. In decimal system, radix = 10. For example, the following is a decimal number with 4 digits Radix Sort Suppose we are given n d-digit decimal integers A[0..n-1], radix sort tries to do the following: for