Algorithms Lesson 4: Quicksort

http://xoax.net/

For this lesson, we explain and demonstrate graphically how to perform the quicksort algorithm with a pseudocode implementation.

Please submit all questions to our forum: http://xoax.net/forum/

Category:

Education

Tags:

• algorithm
• computer
• science
• quick
• sort
• quicksort
• demo
• animation
• efficient
• array
• algorithms
• university

[0xMal]

The pseudocode was particularly helpful. I am writing an algorithms exam tomorrow, and this video's helped me make sure I know what's going on.

[shion16]

u save me dude!!!!

[tristantao]

Worst case maybe N^2, but don't forget that if you shuffle the array(before any sorting) and pick the median as the pivot, then use insertion sort for small enough sections, you can avoid N^2 with a very high probability, getting closer to the best case, Nlg(N). This is why this algorithm is widely used in the industry...

[uyensa]

@VinUnleaded182

Umm no. Has nothing to do with "worst case scenario".

[uyensa]

@vileguy "After it swaps, the cursors move forward."

You are assuming unique values. KHCshadow1 was talking about duplicate values, which will produce an infinite loop.

[uyensa]

@unrealhacker12

Yeah man. You're right! Good catch.

[uyensa]

@illusionist50

In this case, there will be an infinite loop, because the 17's will swap back and forth indefinitely WITHOUT ADVANCING THE CURSORS. See the line of code that advances the L cursor "while (A[L] < pivot) L = L + 1". Now substitute the value 17 for A[L] and pivot. Notice condition will always be false, therefore cursor will not advance. Same story with the R cursor.

[VinUnleaded182]

@unrealhacker12 yea its called the worst case scenario

[illusionist50]

@unrealhacker12

not really, what you are talking about is the worst case scenario. However, it will not be infinite loop. But it will sort the items one at a time costing O(n^2) "quadratic complexity"

swapping 17 with another 17 can happen only once because after that, the two pointers which are doing the swaps will intersect and that is a stop condition for the q sort algorithm.

By the way this is the third method to do a quick sort.

[unrealhacker12]

I don't see how this algorithm would work, if 17, 32, 29, 17, 37, 15, 10, 42, 15,17 if the pivot was the last element 17 then it would get caught in a loop indefinitely swapping 17 with 17 as both are equal to the pivot.

[kaigamwasdf]

you are the man! thank you dude!

could you please let me know how did you make this video? what program did you used?