COEN 179 Lecture Notes - Lecture 11: Quicksort, Array Data Structure, Selection Sort

• School: Santa Clara University
• Department: Computer Engineering
• Course: COEN 179
• Professor: Tran

Document Summary

Merge: simple divide step (cut array in half) but complicated combine step (merge). Quick: complicated divide step (partition), but no combine step. Partition: compare every element against a pivot element (arbitrarily chosen) rearrange the array into 3 positions. 7 6 1 8 3 5 2 4 after partition. //pp in the new, final position of pivot pp = partition(a[lohi]); I partition(a[lohi]){ //pivot is a[hi] i = 10; for(j = 10; j < hi; ++j){ if(a[j] < a[hi]) swap(a[j], a[i++]); swap(a[i], a[hi]); return i; //new position of pivot. E. g 7 6 1 8 3 5 2 4. 3 l 4 ; s > 4 i. 22 4 : swap : 3 & 6 do nothing swap 2 & 7 swap y d8 i d. Do y# swap at cibao;d just ft i. C(n) = worse case number of array element comparisons by qs.