Quick Sort - Data Structures & Algorithms Tutorial Python #15

Quick sort is a popular sorting algorithm invented by British scientist Tony Hoare. Often interviewers ask questions around quick sort in software engineering interviews. This technique uses divide and conquer approach to divide given list into partitions and then recursively sort these partitions. It starts with a pivot element and tries to put pivot element in its correct position. This video goes over theory and two popular partition schemes called hoare partition and lomuto partition. We will write code to implement quick sort algorithm in python. In the end I have an exercise for you to solve.

Topics
00:00 Quick sort technique
03:59 Hoare partition scheme
08:11 Lomuto partition scheme
13:17 Python code for quick sort
29:06 Exercise

#quicksort #datastructures #algorithms #python

DISCLAIMER: All opinions expressed in this video are of my own and not that of my employers'.

[RishiKumar-zsvj]

who named it quick sort.. maybe they named it sarcastically ☻

[MountainDrum]

I can see the humongous effort you have taken in making this video. Love the energy and I am extremely grateful for this series

[awsomeslayer]

I don't think this partitioning scheme can be learnt by anyone in the very first attempt. But, the code looks so beautiful when it runs. By the way, 'Divide and Conquer' is now truly British. Thank You, Mr. Hoare.

[rahulnegi]

19:13, meanwhile in Rocket Science classes 'Come on guys this is not Data Structures and Algorithms'.

[priyavardhanpatel]

Thank you so much Daval sir for the simplistic explination.

[graceguo]

I love this video series! I learned data structures & algos back in my freshman year and i almost forgot everything. Your videos saved me from the frustration of applying to an software engineer role as a data science student.
Thank you!!!!

[amitbudhiraja]

Hi Sir the thing I love about u is that u do it all by yourself not just looking at the standard codes here and there and then doing 
by the same format.
By seeing your videos we are also able to learn how to approach the problem
Thanks a lot, sir

[narinpratap]

You are the coolest instructor I know. Thank you for explaining a concept which no one else on YouTube was able to explain.

[code-heads]

This is the most detailed explaination on Yt. Thank you for putting so much effort.🤗

[sarasijbasumallick]

Elements array is [50, 40, 30, 20, 10], pivot element = 50, start = 50, end = 10
Elements array is [10, 40, 30, 20, 50], pivot element = 10, start = 10, end = 20
Elements array is [10, 40, 30, 20, 50], pivot element = 40, start = 40, end = 20
Elements array is [10, 20, 30, 40, 50], pivot element = 20, start = 20, end = 30
The sorted array is [10, 20, 30, 40, 50]

After executing the code step by step, I noticed that for the initial step you are taking start_index = pivot_index
But in the theory part, you teach start_element is the next element of pivot element i.e start_index = pivot_index +

so that is making a confussion how to fix it?

[adamhendry]

Mistake: at 9:08 you say "you only compare against pivot" (correct), but at 9:25 you say "you move i until you find a value less than 11". You should've said "less than pivot".

[mohammadpatel]

To be honest I only understood the algorithm after implementing it myself. I have attached my python solution below. Thanks a lot for the videos!!
def quicksort(element, start, end):
if start < end:
p = partition(element, start, end)
quicksort(element, start, p-1)
quicksort(element, p+1, end)

def partition(element, start, end):
pivot = element[end]
i = start
j = start

while(j <= end):
if element[j]< pivot:
if i!= j:
element[i], element[j] = element[j], element[i]
i+=1
j+=1
element[i], element[end] = element[end], element[i]

return i

[tesfatsionshiferaw]

I loved the lack of energy lol. But great presentation! Thank you!

[firdousProgrammer]

12:50 Talking about the O(nlogn) time complexity, I think you got it confused with the space complexity!

[yp]

Thank you.This is the explanation others lack.

[ishikagarg]

He has coded from starting how a coder should do coding, what problems might come and how to solve those problems. I like it. Thank you so much

[rogernunes]

There’s a mistake at 9:27 u said eleven instead of pivot

[neelshah]

Awesome learning experience, even though I have to spend 10X time to wrap my brain around, and keep on rewinding!! Thank you sir😀!

[ashenisuranga]

you are always a better explainer than others on the you tube ❤✌

[MrRenaissance]

This is great you explained this relatively well. Though I am still very confused I'll try to watch it again until I get it.