This video shows how partitioning may be achieved, as part of the process of Quicksort. At the end of the partitioning process, the array is divided into two sub-arrays. One sub-array contains elements that are less than a chosen pivot, while the other contains elements that are more than the pivot. The partition function should return the position of the pivot.
Note:
While recording the video, I was focusing on moving the pivot to the (i+1)th position towards the end of the video, and in my hurry to finish the video, I had forgotten that a swap is sufficient. Agree (and this has been brought up many times in the past) that a swap at the last step is quicker and more efficient. However, it is not incorrect to shift - just inefficient. Actually, as mentioned right at the beginning, the objective here is to find the position of the pivot for the partition.
15 окт 2014
