I am trying to decide how best to implement a recursive quicksort on a vector. I know that I want to swap the first and middle elements of the vector and use the value in the first position as the pivot after the swap. After that, I have some questions about what is best to do.
1) Is it better to partition the vector by starting my iterators at the ends of the vector and move them inward toward each other:
|pivot||first element|-------------------|last element|
___i --->______________________________<--- j
or is it better to use my textbook's approach and place one iterator at the end of the partition of elements that are less than the partition and another iterator at the beginning of the partition of unsorted elements and move both iterators in the same direction toward the end of the vector:
|pivot|-----|last element less than pivot|----elements greater than pivot-----------|first unsorted element|-------|last element|
_________________i--->____________________________________________________________ j --->
If one of these approaches is better than the other, why is it better?
2) My textbook code places pivot in the first position of the vector and then copies pivot's value to a variable. If pivot will be in the first position of the vector until it is moved after partitioning the vector is complete, why not use vector when I need the pivot's value? Is there any reason to copy the pivot's value to a variable and use that for comparisons rather than vector?
Any input would be appreciated. Thanks.