Insertion sortSelection sortBubble sortShell sortElementary Sorting Algorithms2Q: Isn’t the system sort good enough?A: Maybe.•Is your file randomly ordered?•Need guaranteed performance?•Multiple key types?•Multiple keys?•Keys all distinct?•Linked list or array?•Large or small records?A: An elementary method may be the method of choiceA: Use well-understood topic to address basic issues.A: Interesting open research problems still arise.1234. ...MA●●B●● ●C●●D●E●F●●●G●●.●●●.●● ●.●●K●●attributesalgorithmmany more combinations of attributesthan algorithmsWhy study sorting algorithms?3Basic termsFox1A 243-456-9091 101 BrownQuilici1C 343-987-5642 32 McCoshChen2A 884-232-5341 11 DickinsonFuria3A 766-093-9873 22 BrownKanaga3B 898-122-9643 343 ForbesAndrews3A 874-088-1212 121 WhitmanRohde3A 232-343-5555 115 HolderBattle4C 991-878-4944 308 BlairAaron4A 664-480-0023 097 LittleGazsi4B 665-303-0266 113 WalkerEx: struct { char name[20]; int class; char grade; long id; char addr[30]; }recordkeyfileSORT: Rearrange records such that keys are in orderAaron4A 664-480-0023 097 LittleAndrews3A 874-088-1212 121 WhitmanBattle4C 991-878-4944 308 BlairChen2A 884-232-5341 11 DickinsonFox1A 243-456-9091 101 BrownFuria3A 766-093-9873 22 BrownGazsi4B 665-303-0266 113 WalkerKanaga3B 898-122-9643 343 ForbesRohde3A 232-343-5555 115 HolderQuilici1C 343-987-5642 32 McCosh4Fox 1 A243-456-9091101 BrownQuilici 1 C343-987-564232 McCoshChen 2 A884-232-534111 DickinsonKanaga 3 B898-122-9643343 ForbesAndrews 3 A874-088-1212121 WhitmanFuria 3 A766-093-987322 BrownRohde 3 A232-343-5555115 HolderBattle 4 C991-878-4944308 BlairGazsi 4 B665-303-0266113 WalkerAaron 4 A664-480-0023097 Little@#%&@!!records withkey value 3not in orderon first keyAaron 4 A 664-480-0023 097 LittleAndrews 3 A 874-088-1212 121 WhitmanBattle 4 C 991-878-4944 308 BlairChen 2 A 884-232-5341 11 DickinsonFox 1 A 243-456-9091 101 BrownFuria 3 A 766-093-9873 22 BrownGazsi 4 B 665-303-0266 113 WalkerKanaga 3 B 898-122-9643 343 ForbesRohde 3 A 232-343-5555 115 HolderQuilici 1 C 343-987-5642 32 McCoshStabilityA STABLE sort preserves relative order of records with equal keysAnnoying fact: many otherwise useful algorithms are not stableEx: sort file on 1st keythen sort file on 2nd key5More general (and more expensive) alternative: Item ADTGOAL: Specify key such that sort code is reusable•use records of type Item•use less(Item, Item) to compare two records•use exch(Item, Item) to exchange two recordsEx: array of integerstypedef int Item;#define less(A, B) (A < B)#define exch(A, B) { Item t = A; A = B; B = t; }Ex: record with associated informationtypedef struct { ... } Item;#define less(A, B) (strcmp(A.name, B.name) < 0) or#define less(A, B) (A.id < B.id)Abstract compare and exchange6Pointer sortFox 1 A243-456-9091101 BrownQuilici 1 C343-987-564232 McCoshChen 2 A884-232-534111 DickinsonFuria 3 A766-093-987322 BrownKanaga 3 B898-122-9643343 ForbesAndrews 3 A874-088-1212121 WhitmanRohde 3 A232-343-5555115 HolderBattle 4 C991-878-4944308 BlairAaron 4 A664-480-0023097 LittleGazsi 4 B665-303-0266113 WalkerMaintain pointers to recordsRearrange pointers, leave records untouched34300100343001503430020034300250343003003430035034300400343004503430050034300600Fox 1 A243-456-9091101 BrownQuilici 1 C343-987-564232 McCoshChen 2 A884-232-534111 DickinsonFuria 3 A766-093-987322 BrownKanaga 3 B898-122-9643343 ForbesAndrews 3 A874-088-1212121 WhitmanRohde 3 A232-343-5555115 HolderBattle 4 C991-878-4944308 BlairAaron 4 A664-480-0023097 LittleGazsi 4 B665-303-0266113 Walker343005003430035034300450343002003430010034300250343006003430030034300400343001507Pointer sort implementationGOAL: Use reusable sort code•use records of type Item•use less(Item, Item) to compare two records•use exch(Item, Item) to exchange two records•Ex: record with associated informationtypedef struct { ... } Record;typedef Record* Item;#define less(A, B) (A->key < B->key)#define exch(A, B) { Item t = A; A = B; B = t; }Avoids excessive moves of large recordsValidates rule of thumb: cost of compare similar to cost of exchange8 scans from left to rightInvariant:•elements to right of are not touchedImplication:•keep elements to left of in sorted orderInsertion sort1123457614672542in order not touched9Shift right all larger elements on left j = i;while (j > l && less(v, a[j-1])) { a[j] = a[j-1]; j--; }3112457614672542Insertion sort inner loop: maintaining the invariant31124573614672542Save current element v = a[i];Store v in vacant spota[j] = v;1123457614672542in order not yet seen10Insertion sort exampleASORTINGEXAMP LEASORTINGEXAMP LEAOSRTINGEXAMPLEAORSTINGEXAMP LEAORST INGEXAMP L EAIO R S TNGEXAMP L EAINO R S TGEXAMPLEAGI N O R S TEXAMPLEAEG I N O R S TXAMP L EAEGINORSTXAMP LEAA E G I N O R S T XMP L EAAEGIM N O R S T XPLEAAEGIMNOP R S T XLEAAEGIL M N O P R S T XEAAEE G I L M N O P R S T X= 1 comparison and 1 assignment to memory11Insertion sort codeTo sort a[l]...a[r]scan left to rightsave itemshiftlargeritemsinsert itemvoid insertion(Item a[], int l, int r) { int i; for (i = l+1; i <= r; i++) { Item v = a[i]; int j = i; while (j > l && less(v, a[j-1])) { a[j] = a[j-1]; j--; } a[j] = v; } }12 scans from left to rightInvariant:•elements to left of are not touchedImplications:•keep elements to left of are in final order•no element to left of is larger than any element to its rightSelection sort1122234476675547in final order13Select minimumint j, min = i;for (j = i+1; j < r; j++) if (less(a[j], a[min]) min = j;Selection sort inner loop: maintaining the invariantExchange into positionexch(a[i], a[min]);11222344766755471122234476675547112223444667557714Selection sort exampleA SORT I N G E X A M P L EA AORT I N G E X S M P L EA AERT I N G O X S M P L EA AEET I N G O X S M P L RA AEEG I N T O X S M P L RA AEEG I N T O X S M P L RA AEEG I L T O X S M P N RA AEEG I L M O X S T P N RA AEEG I L M N X S T P O RA AEEG I L M N O S T P X RA AEEG I L M N O P T S X RA AEEG I L M N O P R S X TA AEEG I L M N O P R S X TA AEEG I L M N O P R S T XA AEEG I L M N O P R S T X= 1 assignment to memory= 1 comparison 15void selection(Item a[], int l, int r) { int i; for (i = l; i < r; i++) { int j, min = i; for (j = i+1; j < r; j++) if (less(a[j], a[min])) min = j; exch(a[i], a[min]); } }Selection sort codeTo sort
View Full Document
Unlocking...