QUICK SORT | Sorting Algorithms | DSA | GeeksforGeeks

Join us in this video as we dive into the inner workings of Quick Sort, a pivotal sorting algorithm in the realm of Data Structures and Algorithms. Operating on the divide-and-conquer technique, Quick Sort Algorithm efficiently sorts through arrays, showcasing its speed and effectiveness in solving complex problems.

-------------------------------------------------------------------------

-------------------------------------------------------------------------

📖 Want to Learn more about Data Structures and Algorithms?

-------------------------------------------------------------------------

Follow us for more fun, knowledge, and resources:

Related Queries:
DSA course
Data Structures and Algorithms
DSA Quick Sort
Quick Sort algorithm
Sorting Algorithms
DSA sorting algorithms
working of quick sort algorithm
time complexity of quick sort algorithm
important algorithms for interview

#quicksort #sorting #algortihms #DSA #datastructuresandalgorithms #sortingalgorithm #quicksortalgorithm #sort #gfg #geeksforgeeks #dsaalgorithms

[GeeksforGeeksVideos]

Correction (00:07-00:14): The video mentions that Pivot divides the array into 'two halves' instead it should be 'two parts'.

[kyzmitch]

Wow, that music is so good, I even can't concentrate and remember algorithm

[cefundmaream]

After ... 10 years of work in computer software industry... I still cannot understand the logic behind some of the sorting algorithms.

[whatdoyousay]

This got a bit confusing. Could have used a better array as an example. It seems like everything got done in the 1st step itself, which is not how quicksort works.

[blaskode]

A narration would be an improvement. The music is distracting.

[ARUSHIGUPTABBTCS]

I love this animated method of explaining algorithms... really really helped me understand something I was confused with for months

[paulotcj]

This video would be nice if:
-The algorithm was actually Quick Sort
-If you followed your algorithm, whatever this is
-If it made sense

[ghosthunter]

If you're wondering why partition works:, this is sort of a proof that helped me understand

1) Fact: every element up to l is smaller than 70.
explanation: if an element was smaller than 70 we swapped it to the the value of l at the time. the l value was everything
between 0 and current l. (the main thing you have to understand, the rest comes from it)



2)Fact: There are exactly l+1 elements below 70
explanation: With J we went over every item in the array exactly once. every time an item below 70 was encountered we "l++ 'd" if an item below 70 was encountered

Conclusion 1 : Since every item at l or below is smaller than 70 and there are exactly l+1 items in those locations and l+1 items below 70.:
Every element at l or below is less than 70.
Conclusion2: Every item above l is more than 70. (immediate from conclusion 1)

[md]

Median-of-Three Partitioning

The median of a group of N numbers is the ⌈N/2⌉ th largest number. The best choice of pivot would be the median of the array. Unfortunately, this is hard to calculate and would slow down quicksort considerably. A good estimate can be obtained by picking three elements randomly and using the median of these three as the pivot. The randomness turns out not to help much, so the common course is to use as the pivot the median of the left, right, and center elements. For instance, with input 8, 1, 4, 9, 6, 3, 5, 2, 7, 0 as before, the left element is 8, the right element is 0, and the center (in position ⌊(left + right)/2⌋) element is 6. Thus, the pivot would be v = 6. Using median-of-three partitioning clearly eliminates the bad case for sorted input (the partitions become equal in this case) and actually reduces the number of comparisons by 14 percent.

[farqadmazhar]

Please use a darker shade of green as the back ground. Its really difficult to read the codes.

[futurexjam]

Brief explanation for whom is still confused:
pivot is the reference point. Here the initial high value is 6, initial low value is zero then the initial pivot will be the latest element in the initial execution of partition function. In the initial execution of partition function every element is compared with the pivot and smaller valued ones are replaced with the bigger ones according to the pivot. Since, we say which ones are smaller or bigger by using pivot value; as a result we replace them with each other, not with the pivot. In the last line of partition we change the pivot's place and return this index value. As a result we have guarantied the place(index) of the initial pivot. So we must try to sort before and after parts of the array according to guarantied placement of the pivot. In recursive executions low and high values will be the same in some time and recursive executions will end. Recursive executions will work atomic so do not think very deeply recursive, it is not human behavior :) You should think that after guarantying the index of pivot you should do the same thing for the before and after parts of the array or list or... I agree that there should be good comments in the code. In the first recursive calling quicksort, the before part of the array will be sorted according to the new pivot but after gauarantying this new pivot's placement, again the code will try to sort before and after parts of the array according to the new pivot. As I have said, do not think too deep recursively, try to think the main issues, which are guarantying the pivot's index, try to sort before and after parts of the array according to pivot's index and stop condition of the recursion. Yes, deciding the stop condition of recursion may be struggling but if you figure out the how the recursion should work, going through beofre and after parts of the array according pivot, you will see low and high values will be the same, so recursion will continue if low is lower than high, low < high. In summary, our sortings are done by using pivot's value. We change the elements' placements according to pivot's value and we replace the pivot's guaranteed place. Other elements have been sorted but by pivot's value so it is not enough. We have aggreed that the elements before pivot's index are smaller than pivot, the elements after pivot's index are bigger but they may not be sorted with each other After finding out the initial pivot's place, we should use another pivot. By doing so, at the end of recursive executions the array will be sorted completely. The executions guarantee the index of pivot, the elements before the pivot are smaller, the elements after the pivot are bigger. By calling the executions recursively the array will be sorted completely.

[applewatch]

*What the hell is the music for? Am I supposed to be able to concentrate? if I wanted to listen to this music I would have hit the gym!*

[deboparnabanerjee]

1) unclear about whats the purpose of i and j.
2) suggestion - please use arrows to indicate the i and jth position on the array.

[anishkumargiri]

No Platform can ever compete geeksforgeeks

[petergeorge]

why is the GeeksforGeeks music always BUSSIN

[toszter]

Quite possibly one of the best examples of spaghetti code. There is a much cleaner, clearer way to accomplish this and demonstrate an ability to write simplified code.

[romanpleshkov]

no need to set i to -1, set it to 0 and increment after swap

[BomKySu]

I don't know if this video follows quick sort or not,
but when I look at the quicksort flow chart, *I created a faster one.*

[hugoirwanto]

i like the music.. idk why everyone hate the music

[omarnsimpson]

Play this at 1.5x speed, the music is ten times better.