Quicksort 2 – Alternative Algorithm

This video describes the principle of the quicksort, which takes a ‘divide and conquer’ approach to the problem of sorting an unordered list. In this particular algorithm, the approach to partitioning a list does not rely on the explicit nomination of a pivot value, but still makes use of left and right pointers that advance towards each other. Items at the positions of the pointers are compared and if necessary swapped, so that the smaller of the two items is at the left pointer and the larger of the two is at the right pointer. This continues until the item that was originally at the right hand side of the list finds itself in the correct position. In other words, the item that was originally at the right hand side of the list is the pivot value. This video also includes a description of some pseudocode for this particular quicksort algorithm.

[rahulz]

Simpler and more intuitive than the traditional algo. Thank you :)

[stkyriakoulisdr]

Nice explanation and even nicer accent

[alvaro]

Great video although it didn't make it clear when the left or right pointer should advance. Initially you say that when there's a swap, it's the right pointer that moves left (vs when there isn't a swap, it's the left pointer that moves right). But then you didn't follow this process consistently.

[nikitamas]

unfortunately works bad when a[i] == a[j], infinity loop happens

[YusaMorgan]

Thank you for this. Really helped me understand my notes.

[nikofoonk]

FYI, this is not Hoare's partition scheme.

[aouldah]

Kevin with all due respect, what if the list is already sorted and the first while will keep advancing till the leftPtr hit the rightPtr which won't get to be compared to its left, then the rest of the code will do unnecessary swap and extra while loop. Please correct me if i am missing something.

[balajishanmugam]

whether this is dual pivot quick sort or not