Quicksort pivot

Question

Sort the following array a using quicksort,

[6, 11, 4, 9, 8, 2, 5, 8, 13, 7] 

The code should be selected as the arithmetic mean of the first and last elements, i.e. (a[0] + a[size - 1]) / 2 (rounded down) .

Show all the important steps, such as partitioning and recursive algorithm calls.

---

I understand how to sort an array using quicksort, however I'm not sure how to calculate the anchor point.

Is the arch calculated by 6 + 7 = 13 , then 13 / 2 = 6.5 (rounded down 6 ), so is the axis of rotation 2 (i.e. the 6th element)?

I know that elements smaller than the pivot are displayed on the left, and elements larger than the pivot are displayed on the right, and the section repeats this step of sorting the submatrix.

Any help would be greatly appreciated.

Answer 1

For quick sorting, the bar can be any item you want. Check out Wikipedia .

The problem was easily solved by choosing either a random index for the pivot point, choosing the average section index or (especially for longer sections), choosing the median of the first, middle and last section elements for the rotation axis

So there are three options:

• First element
• Middle element
• Median of the first, middle and last.

And in your case, using the average of the first and last elements the value will give you:

 6 + 7 = 13 13 / 2 = 6.5 6.5 rounded down = 6 

Answer 2

By the way, the question is formulated, the pivot point should be 6 and not necessarily the 6th element in the array.

This is most certain, because if there were only 3 elements in the array, and the arithmetic average was greater than 3, you would not have a choice, because there is no element with this index.

Note. Be careful how you index elements in your array. You said that the 6th element is “2” if it can be “5” if your programming language starts indexes at 0.

Answer 3

Your core 6. Your core is NOT the 6th element. Now you can apply the following algorithm.

 function quicksort(array) var list less, greater if length(array) ≤ 1 return array // an array of zero or one elements is already sorted select and remove a pivot value pivot from array for each x in array if x ≤ pivot then append x to less else append x to greater return concatenate(quicksort(less), pivot, quicksort(greater)) 

Answer 4

The position of the bar from this calculation does not matter, quicksort sorts the elements based on whether they are more or less reference. Then the axis is between two sets (more and less).