Quick Sort For Beginners | Strivers A2Z DSA Course

Notes:

You can follow me across social media, all my handles are below:

0:00 - intro
1:10 - Flow Chart
3:28 - Explanation of the Algo
19:29 - Psuedo Code & Dry run
27:32 - Note about comparator signs
29:01 - Important Point
29:52 - Online code
32:31 - Time Complexity and Space complexity
34:22 - Outro

[takeUforward]

Let's march ahead, and create an unmatchable DSA course! ❤

The worst case complexity will be O(N ^ 2) if we end up choosing the largest or smallest element as the pivot always. We will add this in the notes in the description. I missed this in the video.

[yashsharma]

I have to state it that "I tried to learn all sorting techniques various time. I learned but after a few days I forgot. But when you just added the real meaning of each sorting techniques. Like why it is called as selection sort and so on.... SO now I just remember their meanings and write the algorithm on my own." Thank you very much. Loved your teaching style

[deepanshuthakur]

I tried to learn this from every yt channel but striver is the one i got it from, respect++

[Kaushik]

Probably one of the crisp and to the point explanation of quick sort algorithm available online!!

[ParasSharma-mfor]

Thanks for this amazing lecture, this is my humble request please complete this course as soon as possible.

[omkarsawant]

Quick Sort's in-place partitioning makes it more memory-efficient than Merge Sort in practice, but the worst-case space complexity can be higher when the partitioning is unbalanced.

Time Complexity:
Best Case: O(n log n) when the pivot choices consistently lead to balanced partitions.
Average Case: O(n log n)
Worst Case: O(n^2) when the pivot choices consistently lead to unbalanced partitions. However, with good pivot selection strategies (e.g., using the median element), this can be mitigated.

Space Complexity:
O(log n) auxiliary space for the recursive call stack in the best and average cases.
O(n) in the worst case when the partitioning is highly unbalanced.
Quick Sort's in-place partitioning makes it more memory-efficient than Merge Sort in practice, but the worst-case space complexity can be higher when the partitioning is unbalanced.

Quick Sort tends to perform well in practice and is often faster than other O(n log n) algorithms, but its worst-case time complexity is worse than Merge Sort.

Merge Sort's space complexity makes it less memory-efficient compared to some other sorting algorithms, but its stable performance and guaranteed O(n log n) time complexity in all cases make it a preferred choice for certain scenarios.

Space Complexity:
O(n) additional space is required for the temporary arrays during the merging process.
It has a space complexity of O(n) due to the need for additional space for merging.

[kingreja]

//for descending
while (arr[i]>=pivot && i<high){
i++;
}
while (arr[j]<pivot && j>low){
j--;
}

[adityamaheshwari]

Really you make everything a cakewalk!
Thank you so much sir, it takes a big heart to do such a lot for the community for free❤

[FunkyPanda]

1 video every 2 days...
Seems TRUE ❣️

[animeshmishra]

how do you know which doubts are going to come in my mind. GREAT LECTURE SIR 🔥

[AdityaSharma-hsos]

please upload full course you are douing a good job bhaiyaaa, you are really a honest teacher other youtubers who has million subscribers just make us fool on name of dsa course, they just tell the problem and paste the soultion but you solve every aspect -f our doubt please cpmplete this and dont worry of views and watch time, time will come when everyone will know who is the best teacher on youtube for dsa

[parthmangalkar]

Understood!

Thank you!! You are the best!

Thanks a lot for making this DSA playlist! It really is helping me a lot!

[shubhamagarwal]

#Free Education For # Bhishma Pitamah of DSA...You could have earned in lacs by putting it as paid couses on udamey or any other elaerning portals, but you decided to make it free...it requires a greate sacrifice and a feeling of giving back to community, there might be very few peope in world who does this...."विद्या का दान ही सर्वोत्तम दान होता है" Hats Off to you man, Salute from 10+ yrs exp guy from BLR,

[isaacreyes]

Damn, I have been looking at sort, recursion, etc forever. I was first confronted with merge/quicksort back in 2019. Been looking at them from various other sources over the years but nobody ever explained it like you do. You are absolutely amazing at this stuff. Idk where you are in life but I hope you go onto make amazing things because someone with this in depth knowledge shouldn't be stuck teaching!

[ArunKumar-skjl]

A great man with the best of the best teaching skills and a kind attitude to make it free is awesome ❤

[tanmaykarmakar]

Quick sort in Descending order-(PYTHON)

arr=[25, 1, 8, 7, 32, 2, 5]
def piviot(arr, high, low):
piviot=arr[high]
i=high
j=low
while(i<j):
while(arr[i]>=piviot and i<=low-1):
i+=1
while(arr[j]<piviot and j>=high):
j-=1
if(i<j):
arr[i], arr[j]=arr[j], arr[i]
arr[high], arr[j]=arr[j], arr[high]
return j
def qsort(arr, high, low):
if(high<low):
pIndex=piviot(arr, high, low)
qsort(arr, high, pIndex-1)
qsort(arr, pIndex+1, low)
qsort(arr, 0, len(arr)-1)
print(arr)

[makerNg]

it's very understandable way you teach. thank you for this amazing lecture

[Manishgupta]

Here is my Assignment question solution :

#include<bits/stdc++.h>
using namespace std;

int partition(vector<int> &arr, int low, int high){
int pivot = arr[low];
int i = low;
int j = high;

while(i < j){
while(arr[i] >= pivot && i <= high - 1) i++;

while(arr[j] < pivot && j >= low + 1) j--;

if(i < j) swap(arr[i], arr[j]);
}
swap(arr[low], arr[j]);
return j;
}

void qs(vector<int>& arr, int low, int high){
if(low < high){
int pIndex = partition(arr, low, high);

qs(arr, low, pIndex - 1);
qs(arr, pIndex + 1, high);
}
}

int main(void){
// vector<int> v = {4, 3, 2, 1};
vector<int> v = {4, 3, 2, 1, 4, 7, 5, 6};
int n = v.size();
qs(v, 0, n-1);

for(auto it : v) cout << it << " ";
return 0;
}

Output : 7 6 5 4 4 3 2 1

Thankyou Striver for making such an amazing tutorial.❤

[alessandrocamilleri]

Excellent explanation as usual. Thank you.
I am posting the iterative version which should further save on recursion call stack space. I have used a queue as the data structure but stack works just as well.

void quickSort (vector<int> &nums)
{
int n = nums.size();
queue<pair<int, int>> q;
q.push({0, n-1});

int low, high, pivot, i, j;

while(!q.empty())
{
low = q.front().first;
high = q.front().second;

q.pop();
if (low >= high) continue;

pivot = nums[low];
i = low; j = high;
while (j > i)
{
while (nums[i] <= pivot && i < n-1)
i++;
while (nums[j] > pivot && j > 0)
j--;
if (j >= i)
swap(nums[i], nums[j]);
}
swap (nums[low], nums[j]);
q.push({low, j-1});
q.push({j+1, high});
}
}

[keshariaman]

Thanks a lot for Quick Short. Feels easier to understand 🥰