Question

trace by using quicksort on the array : 4 6 5 3 2 7 1 using 7 as the pivot

Answer 1

Steps involved in quick sort are: -

1. Choose a pivot element.(in this case, 7)
2. Initialize left and right pointers at extremes.
3. Starting at the left pointer and moving to the right, find the first element which is greater than or equal to the pivot value.
4. In the same way, starting at the right pointer and moving to the left, find the first element, which is smaller than pivot value
5. Swap elements found in 3 and 4.
6. Repeat steps 3,4,5 until left pointer is greater or equal to right pointer.
7. Repeat the whole thing for the two subarray to the left and the right of the left pointer.

Now, The given array is {4,6,5,3,2,7,1}

pivot element is 7, left pointer is at 4 and right pointer is at 1.

Now, first element from left which is greater than or equal to 7 is 7 itself and 1st element from right which is smaller than 7 is 1. so left pointer is at 7 and right pointer is at 1. So, we swap them and array becomes

4,6,5,3,2,1,7

Now our pivot element is at it's right place in when the array is sorted. All elements before 7 are smaller than 7.