Algorithms Lesson 4: Quicksort

[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...

[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.

[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.

[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

[uyensa]

@VinUnleaded182

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

[uyensa]

@unrealhacker12

Yeah man. You're right! Good catch.

[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?

[kefkeuh]

Thank you very much for your videos

Very helpfull!

[seyas85]

very nice! thx

[coolnics11]

superb video....thnx...

[Metalgod89]

I may be wrong but to me this title is misleading. This is the in-place Quick sort. There is another form of quick sort that I am studying that uses a tree. If I am correct on this then the title should probably be changed. I almost second guessed myself until I consulted my book.

[zskhan47]

Thanks. This really helped to clear my confusions.

[patchtok]

Great explanation. Very Clear and precise. Thanks.

[pooyasami]

thank you! very useful and informative vid!

[KHCshadow1]

What happens if A[L] and A[U] are both equal to the pivot...

[vileguy]

@KHCshadow1 this can only happen when L and U are both pointing to the pivot. at this point, it would swap the element with itself and then exit the while loop.

[KHCshadow1]

@vileguy If you have a value in your array that's equal to the pivot it will bring this into an infinite loop because it just constantly swaps it with either the pivot or yet another value equal to the pivot. A. For example, in the original example of this video replace both the 86 and the 3 with 34 and think through the algorithm (the same thing will happen if you replace only the 3 or only the 86 with 34, it will just take longer to get to the infinite loop conditions).

[KHCshadow1]

Its a bug in the code

[vileguy]

@KHCshadow1 The algorithm swaps an element that is less than or equal to the pivot on one side or greater than or equal to the pivot on the other side. If the there are 3 elements with the same value, 1 being the pivot, it will just swap them. After it swaps, the cursors move forward. You could have redundant switching with duplicate elements, but it wouldn't get stuck in an infinite loop if you write it properly. Additionally, the data being sorted often has distinct values which prevents dupes

[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.

[cjfong425]

love the background music

[himiker]

Napoleon Dynamite ?

[zigzagnet1]

It is very useful and informative .. it really helps me alot .. Thanks

[konsu89]

thx great video - but how do i analyze the runtime of the algorithm - i know that the average case is O(n*log(n)) but how do i get there?!

[deadlybug]

I like how you say pipet

[nolliepoper]

pivot = nums[rand() % size] was giving me a dividing by zero error. So I use "pivot = nums[size / 2]"

[vileguy]

@nolliepoper if you're getting divide by zero then make sure size isn't zero. taking the middle element and a random element are equivalent with a random list, but some lists you want to sort may have a start state that could make taking the middle element close to the worst-case. you don't have to pick your pivot at random, it may be more effective to pick it systematically, but you have to consider what type of list you're sorting.

[spdzodzo]

finally i understood how Quicksort works, thanks for lesson

[TheonEvilbuho]

Refreshing my mind for my texes exam and this definitely helps thank you

[amoghavarsha1990]

8 losers live in a cave and have no knowledge abt computers

[phonebooth19]

thanks dude!

[iRouRoui]

Nice video, but i'm going to sleep now

[0dark]

this fucking song is annoying, but good vid.

[filkarada]

At 2:40 why did the 3 swap with the 5?

[Atrofiado91]

@filkarada Because 5 was selected as the pivot of the left side of the array. So, after partitioning that side, all the values lower than 5 go to its left.

[nik1rookie]

Super helpful .. awesome teaching.

god bless u.

[crazyidiot101]

ZaaoooZaaa

[Herrgolani]

1:49 According to your explanation, those two elements must've been switched as well, but you aren't doing so. Why?

[Rebbirth]

Very helpful, thank you!

[Farmerbr0s]

thank you !!

[rival843]

Algorithm doesn't work for duplicate values.

[johnxxx9]

Thank you! Was struggling to understand how this sorting works.

[Krimson444]

Nice. Love the music, too ;)

[AntonTheOmniscient]

thanks a lot! I'm one of those who would dig into the books and understand absolutely nothing until I see how it works with my own eyes :)

[LazyHermit]

Its amazing how much a simple video can explain something so difficult.

[jayvanjj]

Pivot can also the length of A // 2. //= will give you an int.

[felfaj]

i didnt find a better explanation thanxxx!!!!!!

[kamillys]

Very good tutorial for quicksort. This video explains a lot.

[praslisa]

awesome !!

[vuraboz]

THUMBS-UP! you're the best man! ;)

[prettatva]

what happens if the arry doesnt have unique elements?

[bunower]

@prettatva write this:

while(A[L]<= pivot)

[pithikoulis]

@prettatva Nothing. From Wikipedeia(step 2): "2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way)."

[ivanatomic]

Best explanation so far!

[afarhangi]

The algorithm presented at the end of the video has a small bug. This alg works fine when all array elements are unique. In the case that the array has a duplicate element, and the pivot happend to be set to one the duplicate elements, then the bigger while loop hangs indefinately. This statement in the bigger while is needed to fix this bug.

if (pivot == Array[lower] && pivot == Array[upper])

{ lower++; // move either lower up, or upper low

}

[tivrfoa]

very clear explanation, as always.

[AleAleDane]

Thank you!

[Untitledwiz]

wonderful video 5*

[Suyamu]

thanks - best explanation I've seen - quick, to the point and short and clear pseudocode.

[praveenmandloi51]

thanxxxxxxxx by watching this video all algo becomes easy to understand

[lelinhosgp]

Hey guys, thanks for this set of videos on sorting algorithms. Great jog!!!

[Hoogoo123]

great video! Keep working!

[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!!!!

[MarcosMora]

i think this last 2 videos i have seen (merge and quick) should show the O(nlnn) stuff

[heezhot]

great video, make it very simple to understand and implement ! :)

[FromHeavenBaby]

What is the purpose of the quick sort? Why not use a bubble sort?

[Kulik0]

Quicksort is considered the fastest sorting algorithm on current computers (it hits caches better than merge sort). On the other hand bubble sort is veery slow and requires a lot of comparisons.

[onegor]

that's because quick sort is better then bubble sort..

[hgeithus]

bubble sort is O(n^2) on avarage, quick sort is O(n*lg(n)) on avarage.

[Givicencio]

You get less average and worst-case-scenario steps.. In algorithms its all about the number of steps... If you have n elements to sort, bubblesort sorts them in n^2 steps, while quicksort sorts them in less than nlogn most of the time

[hyperstation123321]

Because quick sort is much faster than bubble sort when the number of elements to be sorted increases.

[taitaisparks]

thank you for the great vids

[TheBatchGuy]

awesome keep 'em coming!! !!!!!! ... . . .. !

[Globox822]

thx for this