Question? Leave a message!




Sorting algorithms

Sorting algorithms
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Website URL
Comment
ECE 250 Algorithms and Data Structures Sorting algorithms Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.Sorting algorithms 2 Outline In this topic, we will introduce sorting, including: – Definitions – Assumptions – In-place sorting – Sorting techniques and strategies – Overview of run times Lower bound on run times Define inversions and use this as a measure of unsortednessSorting algorithms 3 8.1 Definition Sorting is the process of: – Taking a list of objects which could be stored in a linear order (a , a , ..., a ) 0 1 n – 1 e.g., numbers, and returning an reordering (a' , a' , ..., a' ) 0 1 n – 1 such that a' ≤ a' ≤ · · · ≤ a' 0 1 n – 1 The conversion of an Abstract List into an Abstract Sorted ListSorting algorithms 4 8.1 Definition Seldom will we sort isolated values – Usually we will sort a number of records containing a number of fields based on a key: 19991532 Stevenson Monica 3 Glendridge Ave. 19990253 Redpath Ruth 53 Belton Blvd. 19985832 Kilji Islam 37 Masterson Ave. 20003541 Groskurth Ken 12 Marsdale Ave. 19981932 Carol Ann 81 Oakridge Ave. 20003287 Redpath David 5 Glendale Ave. Numerically by ID Number Lexicographically by surname, then given name 19981932 Carol Ann 81 Oakridge Ave. 19981932 Carol Ann 81 Oakridge Ave. 19985832 Khilji Islam 37 Masterson Ave. 20003541 Groskurth Ken 12 Marsdale Ave. 19990253 Redpath Ruth 53 Belton Blvd. 19985832 Kilji Islam 37 Masterson Ave. 19991532 Stevenson Monica 3 Glendridge Ave. 20003287 Redpath David 5 Glendale Ave. 20003287 Redpath David 5 Glendale Ave. 19990253 Redpath Ruth 53 Belton Blvd. 20003541 Groskurth Ken 12 Marsdale Ave. 19991532 Stevenson Monica 3 Glendridge Ave.Sorting algorithms 5 8.1 Definition In these topics, we will assume that: – Arrays are to be used for both input and output, – We will focus on sorting objects and leave the more general case of sorting records based on one or more fields as an implementation detailSorting algorithms 6 8.1.1 In-place Sorting Sorting algorithms may be performed in-place, that is, with the allocation of at most Q(1) additional memory (e.g., fixed number of local variables) – Some definitions of in place as using o(n) memory Other sorting algorithms require the allocation of second array of equal size – Requires Q(n) additional memory We will prefer in-place sorting algorithmsSorting algorithms 7 8.1.2 Classifications The operations of a sorting algorithm are based on the actions performed: – Insertion – Exchanging – Selection – Merging – Distribution Sorting algorithms 8 8.1.3 Run-time The run time of the sorting algorithms we will look at fall into one of three categories: 2 Q(n) Q(n ln(n)) O(n ) We will examine average- and worst-case scenarios for each algorithm The run-time may change significantly based on the scenarioSorting algorithms 9 8.1.3 Run-time 2 We will review the more traditional O(n ) sorting algorithms: – Insertion sort, Bubble sort Some of the faster Q(n ln(n)) sorting algorithms: – Heap sort, Quicksort, and Merge sort And linear-time sorting algorithms – Bucket sort and Radix sort – We must make assumptions about the dataSorting algorithms 10 8.1.4 Lower-bound Run-time Any sorting algorithm must examine each entry in the array at least once – Consequently, all sorting algorithms must be W(n) We will not be able to achieve Q(n) behaviour without additional assumptionsSorting algorithms 11 8.1.4 Lower-bound Run-time The general run time is W(n ln(n)) The proof depends on: – The number of permutations of n objects is n, h – A tree with 2 leaf nodes has height at least h, – Each permutation is a leaf node in a comparison tree, and – The property that lg(n) = Q(n ln(n)) Reference: Donald E. Knuth, The Art of Computer Programming, Volume 3: Sorting and nd Searching, 2 Ed., Addison Wesley, 1998, §5.3.1, p.180.Sorting algorithms 12 8.1.5 Optimal Sorting Algorithms The next seven topics will cover seven common sorting algorithms – There is no optimal sorting algorithm which can be used in all places – Under various circumstances, different sorting algorithms will deliver optimal run-time and memory-allocation requirementsSorting algorithms 13 8.1.6 Sub-optimal Sorting Algorithms Before we look at other algorithms, we will consider the Bogosort algorithm: 1. Randomly order the objects, and 2. Check if they’re sorted, if not, go back to Step 1. Run time analysis: – best case:Q(n) – average:Q(n·n) n permutations – worst: unbounded...Sorting algorithms 14 8.1.6 Sub-optimal Sorting Algorithms There is also the Bozosort algorithm: 1. Check if the entries are sorted, 2. If they are not, randomly swap two entries and go to Step 1. Run time analysis: – More difficult than bogosort... See references and wikipedia – Hopefully we can do better...Sorting algorithms 15 8.1.7 Inversions Consider the following three lists: 1 16 12 26 25 35 33 58 45 42 56 67 83 75 74 86 81 88 99 95 1 17 21 42 24 27 32 35 45 47 57 23 66 69 70 76 87 85 95 99 22 20 81 38 95 84 99 12 79 44 26 87 96 10 48 80 1 31 16 92 To what degree are these three lists unsorted?Sorting algorithms 16 8.1.7 Inversions The first list requires only a few exchanges to make it sorted 1 16 12 26 25 35 33 58 45 42 56 67 83 75 74 86 81 88 99 95 1 12 16 25 26 33 35 42 45 56 58 67 74 75 81 83 86 88 95 99Sorting algorithms 17 8.1.7 Inversions The second list has two entries significantly out of order 1 17 21 42 24 27 32 35 45 47 57 23 66 69 70 76 87 85 95 99 1 17 21 23 24 27 32 35 42 45 47 57 66 69 70 76 85 87 95 99 however, most entries (13) are in placeSorting algorithms 18 8.1.7 Inversions The third list would, by any reasonable definition, be significantly unsorted 22 20 81 38 95 84 99 12 79 44 26 87 96 10 48 80 1 31 16 92 1 10 12 16 20 22 26 31 38 44 48 79 80 81 84 87 92 95 96 99Sorting algorithms 19 8.1.7 Inversions Given any list of n numbers, there are n  n(n1)    2 2  pairs of numbers For example, the list (1, 3, 5, 4, 2, 6) contains the following 15 pairs: (1, 3) (1, 5) (1, 4) (1, 2) (1, 6) (3, 5) (3, 4) (3, 2) (3, 6) (5, 4) (5, 2) (5, 6) (4, 2) (4, 6) (2, 6)Sorting algorithms 20 8.1.7 Inversions You may note that 11 of these pairs of numbers are in order: (1, 3) (1, 5) (1, 4) (1, 2) (1, 6) (3, 5) (3, 4) (3, 2) (3, 6) (5, 4) (5, 2) (5, 6) (4, 2) (4, 6) (2, 6)