EIMACS:
Looked at the quicksort a little bit more, using their graphical explanation. Based on my observation, it "locks in" elements to their final resting positions by incrementing the position of a bottom index and decrementing the position of the top index. Along the way, if it finds that an element at a bottom index greater than the pivot element and an element at a top index less than the pivot element, they are swapped. Eventually, the top and bottom indexes intersect, or cross over one another, such that the top index is less than the bottom index. At this point, the pivot element is known to be greater than all elements in indexes less than the pivot index and less than all elements in indexes greater than the pivot due to how the elements were swapped. The pivot element is now in its final position in the array, and the list is then split along the pivot element, and the process repeats recursively.
Sam showed me a cool website which gives a visual of the quicksort (along with other sorting algorithms)
Sam showed me a cool website which gives a visual of the quicksort (along with other sorting algorithms)
That is a nice looking visualization. Thanks (and thank Sam) for sharing! I had mentioned that heap sort is my favorite, primarily because I loved the way a tree abstraction could be stored implicitly inside an array. I've heard that quicksort is usually much faster, however, and this demo supports that.
ReplyDelete