2015-03-05 HW

posted Mar 5, 2015, 8:14 AM by Samuel Konstantinovich   [ updated Mar 6, 2015, 8:16 AM ]

QuickSelect

Homework By Tomorrow:

Write the function void partition(int[]ary,int si, int ei) to partition an array about a randomly chosen pivot element. 

For now assume that the array you're working in has all unique elements (and make your test data to enforce this).

Your function should:

  • you will have the array ARY, a start index SI and an end index EI
  • make a new empty array called D of the same size as ARY
  • copy all the elements not in the range SI to EI over to the new array
  • select a pivot element and pull it out of the arrray. Just choose L[SI] for now and increment SI
  • for the rest of the elements between SI and EI:
    • if it's less than the pivot value copy it to D[SI] and increment SI
    • if it's greater than the pivot value copy it to D[EI] and decrement EI
  • when SI and EI meet, you should be out of elements. the pivot value goes in this location and is now in it's sorted location.
Comments