## Lecture Notes

Previewing page *1*
of
actual document.

**View the full content.**View Full Document

## Lecture Notes

0 0 80 views

- Pages:
- 4
- School:
- University of Northern Iowa
- Course:
- Cs 1520 - Data Structures

**Unformatted text preview: **

Data Structures Lecture 15 Name 1 Quick sort general idea is as follows Select a random item in the unsorted part as the pivot Rearrange called partitioning the unsorted items such that Pivot Index Pivot Item All items to Pivot All items to Pivot Quick sort the unsorted part to the left of the pivot Quick sort the unsorted part to the right of the pivot Given the following partition function which returns the index of the pivot after this rearrangement def partition lyst left right Find the pivot and exchange it with the last item middle left right 2 pivot lyst middle lyst middle lyst right lyst right pivot Set boundary point to first position boundary left Move items less than pivot to the left for index in xrange left right if lyst index pivot temp lyst index lyst index lyst boundary lyst boundary temp boundary 1 Exchange the pivot item and the boundary item temp lyst boundary lyst boundary lyst right lyst right temp return boundary a For the list below trace the first call to partition and determine the resulting list and value returned lyst 0 54 1 26 2 93 3 17 4 77 5 31 6 44 7 55 8 20 left 0 right 8 index boundary b What initial arrangement of the list would cause partition to perform the most amount of work c Let n be the number of items between left and right What is the worst case O for partition Lecture 15 Page 1 Data Structures Lecture 15 Name d What would be the overall worst case O for Quick Sort e Why does the partition code select the middle item of the list to be the pivot f Ideally the pivot item splits the list into two equal size problems What would be the big oh for Quick Sort in the best case g What would be the big oh for Quick Sort in the average case Lecture 15 Page 2 Data Structures Lecture 15 Name 2 Consider the coin change problem Given a set of coin types and an amount of change to be returned determine the fewest number of coins for this amount of change a What greedy algorithm would you use to solve this problem with US coin types of 1 5

View Full Document