Describe how the quicksort works including a discussion of the pivot, how it is selected, and why the pivot is important to the quicksort.
Let’s start describing what pivot is, its function and why is so important. The pivot is the element that basically divides the array in two halves, where the left half contains the smaller values and the right half contains the greater values.
The pivot can be selected in many ways. First, last, middle element, actually any element of the array can be equally chosen for the pivot it all depends on how you want to implemented the array; if you select first or last will cause worst-case performance if you choose middle would be a better choice because it minimizes the chances of encountering worse case O(n2). …show more content…
It may look a little confusing but it is not as complicated as it seems but the best way to do this is with an example.
Let’s assume that we have an array with 5 elements (4 2 5 1 3) and we are going to arrange the array in ascending order.
0 1 2 3 4
4
pivot 2 5 1 3
Index
Elements
If we look at the chart above we have 4 as the first element on the left of the array and 3 as the last element on the right of the array now we have to remember a simple rule “elements to the right of the pivot are suppose to have greater values than elements to the left of the pivot” consequently if we select 4 as the pivot (worst-case) and quick sort the array, we do a comparison check; is 4 (pivot) less than right element 3? ... In this case is not, so what we do is swap:
4
pivot 2 5 1 3
Elements
Now the pivot (4) is showing on the right and is greater that the left (3) element (remember the rule) so the next step is to move one position to the right, check the next element (2), and compare again is 4 > 2 = yes:
3 2 5 1
Let’s start describing what pivot is, its function and why is so important. The pivot is the element that basically divides the array in two halves, where the left half contains the smaller values and the right half contains the greater values.
The pivot can be selected in many ways. First, last, middle element, actually any element of the array can be equally chosen for the pivot it all depends on how you want to implemented the array; if you select first or last will cause worst-case performance if you choose middle would be a better choice because it minimizes the chances of encountering worse case O(n2). …show more content…
It may look a little confusing but it is not as complicated as it seems but the best way to do this is with an example.
Let’s assume that we have an array with 5 elements (4 2 5 1 3) and we are going to arrange the array in ascending order.
0 1 2 3 4
4
pivot 2 5 1 3
Index
Elements
If we look at the chart above we have 4 as the first element on the left of the array and 3 as the last element on the right of the array now we have to remember a simple rule “elements to the right of the pivot are suppose to have greater values than elements to the left of the pivot” consequently if we select 4 as the pivot (worst-case) and quick sort the array, we do a comparison check; is 4 (pivot) less than right element 3? ... In this case is not, so what we do is swap:
4
pivot 2 5 1 3
Elements
Now the pivot (4) is showing on the right and is greater that the left (3) element (remember the rule) so the next step is to move one position to the right, check the next element (2), and compare again is 4 > 2 = yes:
3 2 5 1