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.
Code: github.com/codebasics/data-st...
Exercise: github.com/codebasics/data-st...
Data structures and algo in python playlist: • Data Structures And Al...
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
Do you want to learn technology from me? Check codebasics.io/ for my affordable video courses.
#quicksort #datastructures #algorithms #python
Next Video: • Insertion Sort - Data ...
Previous video: • Bubble Sort - Data Str...
Complete playlist: • Data Structures And Al...
Website: codebasics.io/
Facebook: / codebasicshub
Twitter: / codebasicshub
DISCLAIMER: All opinions expressed in this video are of my own and not that of my employers'.

[@codebasics]

Do you want to learn python from me with a lot of interactive quizzes, and exercises? Here is my project-based python learning course: codebasics.io/courses/python-for-beginner-and-intermediate-learners

[@MountainDrum537]

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

[@codebasics]

You are so welcome

[@rahulnegi456]

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

[@puneethv4138]

Lol ....😂🤣

[@avinashgarg500]

Yup! 😂

[@RishiKumar-zs4vj]

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

[@awsomeslayer1]

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.

[@amitbudhiraja7498]

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

[@tesfatsionshiferaw3474]

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

[@neelshah1943]

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

[@CodingWithKids]

Great explanation! 👏👏👏

[@soumadeepdey1594]

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

[@narinpratap8790]

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

[@piyushkumarsahoo8771]

Watch abdul bari

[@pankajkumarbarman765]

I'm extremely grateful for this series, ❤ thank you sir

[@ronylpatil]

You have explained whole Data Structure series very very well. It helps me alot, please upload videos on Algorithms please.

[@adityakumarsingh9305]

We need more teachers like you sir......

[@priyavardhanpatel6155]

Thank you so much Daval sir for the simplistic explination.

[@MrRenaissance17]

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.

[@ishikagarg5261]

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

[@ashenisuranga2915]

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

[@priyavardhanpatel6155]

thank you so much dhaval sir, it really helped a lot.

[@shenmi6919]

Tqsm for the simple nd neat explanation sir!

[@bharatmishra250]

Great explanation sir we need more videos on DS algorithm

[@codebasics]

Will upload soon

[@rogernunes8699]

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

[@nileshbharadwaj2039]

great explanation

[@shahfazil8443]

keep continuing best resource

[@codebasics]

Yup. Next one is on insertion sort

[@syedrehan7108]

Thanks for such a great video and explanation. If I do quick sorting in below fashion, will it be fine? I am using last element as pivot >>> traversing through list to see which is less/equal/greater than pivot >>> Adding items to another list >>> Adding all lists together >>> Then making recursive call to repeat the process. def quick_sorting(sample_list): print(f"Got list: {sample_list}") smaller, equal, larger = [], [], [] if len(sample_list) < 2: return sample_list pivot = sample_list[-1] print(f"Pivot element >>> {pivot}") for item in sample_list: if item < pivot: smaller.append(item) elif item == pivot: equal.append(item) else: larger.append(item) print(f"Processing: {smaller}, {equal}, {larger}") return quick_sorting(smaller) + quick_sorting(equal) + quick_sorting(larger) if __name__ == "__main__": given_list = [11, 9, 29, 7, 2, 15, 28] qs = quick_sorting(given_list) print(f"After quick-sorting: {qs}") # [2, 7, 9, 11, 15, 28, 29] PS: I haven't written code all by myself but I go through other videos as well. DSA understanding takes time for me. 😀

[@slingshot7602]

Thanks. It really helped

[@codebasics]

I am happy this was helpful to you.

[@Akash0515]

I have a question, when did you initialised value of start from 0, in theory you told we dont need to initialize start from 0 but from 1?

[@tanmaysingh3724]

Great Sir

[@k.prithvisai9247]

line 20 in partition function , you wrote it as while start < len(elements) and elements[start]

[@mohammadpatel2315]

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

[@sairajdhonnar2299]

You are using nested while loop which makes the time complexity as n*n and quick sorts time complexity should be nlogn?

[@vaibhavmathur6216]

Thank you sir....

[@rogerthat7190]

Thank you sir

[@surajk508]

why is pivot initialized to start when the code is being made generic? isnt it start-1? correct me please

[@strivefitness7766]

Thanks so much dude, great tutorials. Could you point out what the mistake is with this script that I wrote ? def lomuto_partition(elements, start, end): pivot_index = end pivot = elements[pivot_index] p_index = start i_index = p_index+1 while i_index < end: while p_index < len(elements) and elements[p_index] pivot: i_index +=1 if p_index < i_index: swap(p_index, i_index, elements) if elements[p_index] > pivot: swap(p_index, pivot_index, elements) return p_index

[@yolamontalvan9502]

Does Python supports recursion? I have the algorithm in C++ and I want to have the Python version.

[@adamhendry945]

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

[@codeofcoffee8722]

Thank You Sir

[@xslyfer]

hello, can you explain better why did you return end? thank you for the great video btw

[@chandamwenechanya8614]

It is working friends, it is working!

[@hargobindsingh9763]

I'm so glad you started this series But I had a question in mind How important is dsa for data science and machine learning how should we go about it if our main goal is ml and data science not software engineering? What are the important topics one should be aware of ? And pls do complete this series it's imperative for a lot of us

[@purnimamanna8332]

Need to know this answer

[@randomdude79404]

Another youtuber who makes data science videos ( Krish Naik ) has a video which explains why every programmer should learn data structures and algorithms. Here is the link to that video kzbin.info/www/bejne/hHWWeYt5aZuthZY

[@shwetanksingh9571]

U r awesome man!!!!!!

[@anirbanc88]

awesome!

[@pawans1910]

What about if input 50 40 30 20 10 start goes beyond bound in while loop right

[@kavishjain3702]

How swap function is effecting directly to the actual list, as it is not returning anything

[@namnguyenngoc1948]

have a error if arr dont have any numbers that less than pivot so fix this issue, we have to add a condition right > 0 in second while

[@Harsh_Chouksey10]

I didn't understand what happened after the first pivot element(11) was positioned in its correct position.

[@roshanzameer5020]

Is Binary Search a divide & conquer method?

[@lohit0319]

Great explanation sir!!!. Sir how many more videos will be uploaded??

[@codebasics]

10 more atleast

[@dailywebmoments]

zabardast😍😍😍

[@Gokul-eq4wm]

Just in gpt, def quick_sort(arr): if len(arr) pivot] return quick_sort(left) + middle + quick_sort(right)

[@zack176]

Hey could you help me in the exercise where we have to sort the string part because i have sorted the number part but how do i implement sorted string

[@anirudhgoutam6401]

Sir in your code pivot & start indexes are same pivot_index = start pivot = elements[pivot_index] why ???

[@kallasrikanth5397]

The while condition is written as

[@mbappekawani9716]

interesting that the array doesnt get returned internally yet it gets updated and shared recursively

[@user-li2nr9sg8q]

9:15 beginners we don't start i here. we start i and p.index together. if i

[@stevenzayas5527]

Quick note on a tiny mistake that you made: at around 10:21, when P-index hits and stops at 29, you said that "29 is less than 28", instead of "29 is greater than 28". Nothing major, I know what you meant, but it gave me pause for a second. Great videos, thank you so much! These have been the most helpful.

[@joxa6119]

On 9:34, why do you said 7 is less than 11? Because you said we only compare with pivot, but now you compared with 11, which is not the pivot.

[@lensin-re5if]

although, we are saying do the swap if start < end , when we swap 7 iwith 11 , start index was 4 and end index was 3. so how come the code is working?

[@kallasrikanth5397]

He didn't write an if condition; it's a while loop. The condition checks if the outer loop's start is less than the end. If the condition is false, the outer loop breaks. Since 4 is greater than 3, the loop breaks, and the end is swapped with the pivot at that moment.

[@raghav876]

Good explanation. Noticed for test case [1, 2, 3, 4, 5] its giving [1, 2, 3, 5, 4].

[@codebasics]

Ahh... Are you saying my code on GitHub has this issue. Do you have a fix? If yes please give me a pull request

[@codebasics]

hi i just ran my code on [1, 2, 3, 4, 5] and dont see any issues. it gave me back [1, 2, 3, 4, 5].

[@oskardonis7647]

@@codebasics in my case, i prove the code in colab, there i notice some issues with the right partition, showing 28,15,29 as the result for that segment of the list of values

[@matissjansons8789]

how about this: def quicksort(arr): if len(arr) pivot] return quicksort(left) + middle + quicksort(right)

[@SimranUppal6991]

In Lomuto, the resultant was not sorted.....

[@aryan_b03]

Could you please check the error in my code def swap(a,b,arr): if a !=b: temp = arr[a] arr[a] = arr[b] arr[b]=temp def partition(start,end,array): pivot_index = start pivot = array[pivot_index] start =pivot_index+1 while start

[@zack176]

Hey could you help me in the exercise where we have to sort the string part because i have sorted the number part but how do i implement sorted string .

[@amranmohamed377]

def quick_sort(collection): if len(collection)

[@kumarrajneesh9601]

Correct but you are using extra space for left and right arrays

[@Jack_X075]

5 minutes to watch the video. 2 hours to implement the lomuto partition!

[@bhavikjain1077]

🔥👍

[@codebasics]

👍😊

[@sarasijbasumallick4036]

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 + 1........... so that is making a confussion ..... how to fix it?

[@abhinav.sharma732]

the code is wrong it wont work for array having duplicate elements.

[@sidhantgi899]

Sir iam B.A graduate can i became data scientist? How?

[@zack176]

Hey could you help me in the exercise where we have to sort the string part because i have sorted the number part but how do i implement sorted string

[@sachinmaurya3259]

lumtttottt .... haha .......... great video

[@codebasics]

I am happy this was helpful to you.

[@yourcodingerror3816]

I went to programming language course hindi and online class programming in hindi. You know any online class . Tell me . please sir

[@padmanabhan5907]

Lol

[@yourcodingerror3816]

@@padmanabhan5907 why🤔

[@ssss22144]

❤

[@whatwhat2573]

YASSSSS

[@suryasrimanthkaja8744]

Woww

[@mbappekawani9716]

a,b = b,a is a better way to swap

[@meralmaradia4774]

Hello Sir, can you please create a video developing of project using only DSA ?

[@reynaldoruizflores]

The pivot election is an influencer too naive(low), high, random. Random is the best according to my research.

[@304nikhilgohil5]

U actually did a little bit mistake but only in speaking n showing was different just a bit but that's ok i gotch u 💓

[@BYogeshwaran49]

So quick sort is nothing but a binary search but not searching only sorts .... I think so...

[@neyazanwar8226]

24 18 38 43 14 40 1 54 what about this input

[@manojkperadka9197]

yes.. implementation needs to be tuned further. try giving [15,16,17], output would not be right for this case too.

[@RonnyTalk]

Why man you confused me, don't upload such video, do partition of this video in 2....

[@user-gj8mb8gv6i]

oooooooooo..

[@gajendersingh222]

hindi mai padha do sir aap

[@godtech1987]

over complicated the python code

[@adityadeep619]

could have explained in better way.. felt a bit difficult understanding while other youtube video were more clear.. for ex : kzbin.info/www/bejne/i5vHqpuEoMaCb80 Honest review, no hate !

[@kartikwagh8553]

Hindi aati hai You know Hindi

[@Multi159632478]

is he drunk?

[@ryansheikh4109]

worst explanation, honestly you should stop trying to act funny to hide stupid mistakes

[@mohamedhassan-ub4kj]

I dont know what is happening to u my friend but I feel like if you had some alcohol .. hopefully you are good now