This is another example of a divide and conquer algorithm Step 1 divide Select a pivot value and logically partition the list into two sub lists L1 values less than the pivot L2 values greater than the pivot Your list is now L1 pivot L2 Step 2 conquer Sort L1 and L2 SORTED Algorithm Let s assume that our list L is held in an array and that we want to use as little extra space as possible QuickSort array L int first int last if first last pivotpos Partition L first last QuickSort L first pivotpos 1 QuickSort L pivotpos 1 last NOTE We would still need to write the partition algorithm The easiest thing to code would probably be to pick the last value in the list as the pivot and then partition based on that There are many ways to implement the partition algorithm but in terms of data comparisons what should its runtime be Start with T 0 T 1 0 For the recurrence what is The worst case split The best case split The average expected runtime Let s return to the idea of expected values Let s assume that every division situation is equally likely If we let posp represent the position of p then we could represent the expected runtime as being
View Full Document
Unlocking...