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.
Since, we are always choosing pivot to be the first element of the array, we can always avoid the O(n^2) case by pre-checking if the array is pre-sorted (with O(n) Time Complexity) and if it is not then only feed it into the quick sort function.
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
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.
00:06 - Quick sort is a sorting algorithm with time complexity of n log n and space complexity without using an extra temporary array. 04:36 - Pick up elements and place them in their correct place in a sorted array. 09:07 - The quick sort algorithm works by picking a pivot, placing it in its correct place, and recursively sorting the left and right arrays. 13:48 - Sorting an array using the partition index 18:43 - Quicksort algorithm explained in a simple way 22:51 - The algorithm involves partitioning an array based on a pivot element. 27:23 - Implementing the Quick Sort algorithm 31:23 - Quick sort algorithm has a time complexity of n log n and a space complexity of O(1).
For Descennding Order Sorting -> //Just Reverse the inequality sign in partition function :- #include int partition(vector&arr,int low,int high){ int pivot =arr[low]; int i=low ,j=high; while(i
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
When I try to run this code(using array), I getting no output and the code runs for infinite time. When I try with ArrayList, I am getting output. Explain why? This put me into severe headache
@@DineshKumar-pw7qb Heyy!! You mean my code? Either way, can you send me the code you are working on. I want to try it. How about that? Maybe we can fix it together?
@@DineshKumar-pw7qb Hey, mate! I copied my code, and yes it works with arrays. It doesn't give me errors or infinite loops, but... this line: while(arr[i] > pivot && i < high) I missed the =. I am so sorry. I should be: while(arr[i] >= pivot && i < high) Check it out now. But as I understand, the problem with your code is the array itself, yes? Not the output? If you want you can send the code. Because mine works well with array. P.S.: I will edit the original comment, and put the equal.
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 &nums) { int n = nums.size(); queue 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 && 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}); } }
So Yah u tried the iterative version of Quick Sort but still you are using the space what the Recursive func calls use in func call stack in the QUEUE FORM. O(logN) Queue takes as extra space. Like the point is Quick sort no matter what -> You can further optimize. Func Stk Space or in Iterative normal stack or queue space is needed. As we need to store it somewhere -> what are the next range of places where it is unsorted. Either use the system's func call stack or make ur own.
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!
#Free Education For All...... # 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, India.......
Quick sort in Descending order in Python: def qS(array): if len(array) pivot] return qS(elm_grater_than_pivot) + elm_equal_pivot + qS(elm_less_than_pivot)
Understood sir. For descending order: int partitionFunction(int arr[], int low, int high){ int i = low, j = high, temp; int pivot = arr[low]; while(ipivot and i
For Decending order #include using namespace std; int pick_place_pivot(int arr[],int low,int high){ int pivot=arr[low]; int i=low,j=high; while(i= pivot && i=low+1) j--; if(i> n; int arr[n]; for(int i=0;i> arr[i]; quick_sort(arr,0,n-1); for(int i=0;i
// for descending order just we have to do the tweaks in the how we are selecting elements when which we are stopping when we are finding element smaller in left and stop when we find the element greater the pivot then we just we swap it than it goes in the recursion stack public class Quicksort { static int partiton(int arr [] , int low , int high ){ int pivot = arr[low]; int i= low; int j = high; while (i < j ) { while (arr[i] >= pivot && i = low + 1 ) { j--; } if(i < j ){ int temp = arr[i]; arr[i] = arr [j]; arr[j] = temp; } } int temp = arr[j]; arr[j] = arr[low]; arr[low] = temp; return j ; } static void quicksort(int arr [] , int low , int high){ if(low < high ){ int PartionIndex = partiton(arr,low,high) ;
Damn it, i have learnt sorting algorithms a lot of times, but i aways manage to somehow forget.But after seeing this video now i understand it in so much more detail and depth which i earlier didn't even notice. thanks you soo much striver !
public: // Function to sort an array using quick sort algorithm in descending order. void quickSort(int arr[], int low, int high) { if (low < high) { int pIndex = partition(arr, low, high); quickSort(arr, low, pIndex - 1); quickSort(arr, pIndex + 1, high); } } public: int partition(int arr[], int low, int high) { int pivot = arr[low]; int i = low; int j = high; int temp; while (i < j) { while (arr[i] >= pivot && i = low + 1) { j--; } if (i < j) { temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } temp = arr[low]; arr[low] = arr[j]; arr[j] = temp; return j; } }
//for Descending order #include using namespace std; int partition(vector &arr, int low, int high){ int pivot = arr[low]; int i = low; int j = high; while(i= pivot && i n; // int arr[n]; // for (int i = 0; i < n; i++) // { // cin >> arr[i]; // } vector arr = { 3, 9, 4,1}; int n = arr.size(); vector result= quick_sort(arr, n); for (int i = 0; i < n; i++) { cout
home work question (to print in decreasing order)- #include using namespace std; int partition(vector &arr, int low, int high){ int pivot=arr[low]; int i=low; int j=high; while(i=arr[low] && i
# code for reverse sorted i.e. descending sort def quickSort(self,arr,low,high): if low < high: p_index = self.partition(arr,low,high) self.quickSort(arr,low,p_index-1) self.quickSort(arr,p_index+1,high)
def partition(self,arr,low,high): # modified pivot = arr[high] i = low j = high while i < j: #modified while arr[i] >= pivot and i = low+1: j -= 1 if i < j: arr[i], arr[j] = arr[j], arr[i] arr[low], arr[j] = arr[j],arr[low] return j
C++ Code : #include using namespace std; int partition (vector& arr, int low, int high){ int i = low; int j = high; int pivot = arr[low]; while(i low) j--; if(i= high){ return; } int pt = partition(arr,low,high); quickSort(arr,low,pt-1); quickSort(arr,pt+1,high); return; } int main() { vector arr={4,2,8,5,6,7,0,1,3,9}; quickSort(arr,0,9); for(auto i:arr){ cout
Its a great video, but you should also explain the cases where complexity for quick sort can result to O(n^2) in the case where all elements of array are same and when array is already sorted, in those cases partition will always be 1, n-1.
by the way, there exist some examples where the code shown can return in out of vector subscript error because the partition index might be returned as 0 and when we try to access pIndex-1 it will of course crash. so put an extra little check where the code just returns if pIndex is 0.
Java code for QuickSort in descending order with comments public class Quick_Sort { //descending public static int pivotloc(int []arr,int low,int high){ int pivot=low; //choosing arr[low] as pivot element //greater or equal on left, less on right int i=low,j=high,t; while(i=arr[pivot] && i
little tweaks in partition function for descending case int partition (vector &arr, int low, int high){ int pivot = arr[low]; int i = low; int j = high; while (i=pivot && i
Everything will be same , only we have to do some changes in partition function to get array in decreasing order: int decendingPartition(int arr[],int low,int high){ int pivot=arr[low]; int i=low; int j=high; while(i=pivot && i
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.
Yes striver , even i was thinking same that you didn't explain this thing , btw thankyou so much for this much crystal clear explaination ..
Hi striver @takeUforward ,
when are you going to release video solutions for string type problems and heaps?
There is a minor mistake in your algo at 23:54 in while loop condition must be arr[i]
Since, we are always choosing pivot to be the first element of the array, we can always avoid the O(n^2) case by pre-checking if the array is pre-sorted (with O(n) Time Complexity) and if it is not then only feed it into the quick sort function.
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
same here
same heree
same here
Same
Not same 😢
I tried to learn this from every yt channel but striver is the one i got it from, respect++
then you haven't tried Abdul Bari
@@navagharkiran5769 sadly I did, its not that abdul bari is not good, its me who is dumb uk but striver made me understand it anyhow
@@navagharkiran5769 abdul bari is better for college academics but striver is for campus selections
//for descending
while (arr[i]>=pivot && i
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.
Appreciate the effort you put for writing this comment 😇❤
Thanks for the comment. i was looking for it.
Hey can you give me the code for pivot = median element pls??
@@dreamer12nwhat kind of code do you want
@@dreamer12nJust set pivot = (low + high)/ 2 or in a better way to deal with larger numbers make it low +(high -low)/2
Probably one of the crisp and to the point explanation of quick sort algorithm available online!!
Thanks for this amazing lecture,this is my humble request please complete this course as soon as possible.
00:06 - Quick sort is a sorting algorithm with time complexity of n log n and space complexity without using an extra temporary array.
04:36 - Pick up elements and place them in their correct place in a sorted array.
09:07 - The quick sort algorithm works by picking a pivot, placing it in its correct place, and recursively sorting the left and right arrays.
13:48 - Sorting an array using the partition index
18:43 - Quicksort algorithm explained in a simple way
22:51 - The algorithm involves partitioning an array based on a pivot element.
27:23 - Implementing the Quick Sort algorithm
31:23 - Quick sort algorithm has a time complexity of n log n and a space complexity of O(1).
1 video every 2 days...
Seems TRUE ❣️
Here is my Assignment question solution :
#include
using namespace std;
int partition(vector &arr, int low, int high){
int pivot = arr[low];
int i = low;
int j = high;
while(i < j){
while(arr[i] >= pivot && i = low + 1) j--;
if(i < j) swap(arr[i], arr[j]);
}
swap(arr[low], arr[j]);
return j;
}
void qs(vector& 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 v = {4, 3, 2, 1};
vector v = {4, 3, 2, 1, 4, 7, 5, 6};
int n = v.size();
qs(v, 0, n-1);
for(auto it : v) cout
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❤
For Descennding Order Sorting ->
//Just Reverse the inequality sign in partition function :-
#include
int partition(vector&arr,int low,int high){
int pivot =arr[low];
int i=low ,j=high;
while(i
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
CODE FOR DESCENDING (JAVA):
public void quickSort(int[] arr, int low, int high){
if(low low){
j--;
}
if(i
When I try to run this code(using array), I getting no output and the code runs for infinite time. When I try with ArrayList, I am getting output.
Explain why? This put me into severe headache
@@DineshKumar-pw7qb Heyy!! You mean my code?
Either way, can you send me the code you are working on. I want to try it. How about that? Maybe we can fix it together?
@@tasneemayham974bro are sure about your code is working well with array?
@@DineshKumar-pw7qb Hey, mate! I copied my code, and yes it works with arrays. It doesn't give me errors or infinite loops, but...
this line:
while(arr[i] > pivot && i < high)
I missed the =. I am so sorry. I should be:
while(arr[i] >= pivot && i < high)
Check it out now. But as I understand, the problem with your code is the array itself, yes? Not the output? If you want you can send the code. Because mine works well with array.
P.S.: I will edit the original comment, and put the equal.
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 &nums)
{
int n = nums.size();
queue 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 && 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});
}
}
So Yah u tried the iterative version of Quick Sort but still you are using the space what the Recursive func calls use in func call stack in the QUEUE FORM. O(logN) Queue takes as extra space.
Like the point is Quick sort no matter what -> You can further optimize. Func Stk Space or in Iterative normal stack or queue space is needed.
As we need to store it somewhere -> what are the next range of places where it is unsorted.
Either use the system's func call stack or make ur own.
Understood!
Thank you!! You are the best!
Thanks a lot for making this DSA playlist! It really is helping me a lot!
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=piviot and i
Hey I haven't done a dryrun of your code but as i has index of high how can in increment in the while loop?
yes make sense and have to chnage the while (i
shouldn't it be while(i > j) ?
This is gold... Plz keep doing this..
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!
Don't worry he is working at Google. Doing great in life :)
#Free Education For All...... # 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, India.......
best explanation of quick sort on youtube
how do you know which doubts are going to come in my mind. GREAT LECTURE SIR 🔥
Because once he was also in the same place as we are now and he worked hard to reach this point now he is helping us
for the assigment problem just change the condition while (i < j) {
while (arr[i] > pivot && i
Understood, will be a quick way to remember the algorithm, well taught!! Thanks
it's very understandable way you teach. thank you for this amazing lecture
for decreasing Quick Sort:-
int partition(vector &arr, int low, int high) {
int pivot = arr[low];
int i = low;
int j = high;
while (i < j) {
while (arr[i] >= pivot && i = low + 1) {
j--;
}
if (i < j) {
swap(arr[i], arr[j]);
}
}
swap(arr[low], arr[j]);
return j;
}
void quickSort(vector &arr, int low, int high) {
if (low < high) {
int pIndex = partition(arr, low, high);
quickSort(arr, low, pIndex - 1);
quickSort(arr, pIndex + 1, high);
}
}
vector sortArray(vector &arr) {
quickSort(arr, 0, arr.size() - 1);
return arr;
}
A great man with the best of the best teaching skills and a kind attitude to make it free is awesome ❤
Quick Sort in Descending Order (C++):
int partitionArray(int input[], int start, int end) {
int pivot = input[start];
int i = start;
int j = end;
while (i < j) {
while (input[i] >= pivot && i < end) {
i++;
}
while (input[j] < pivot && j > start) {
j--;
}
if (i < j) {
int temp = input[i];
input[i] = input[j];
input[j] = temp;
}
}
input[start] = input[j];
input[j] = pivot;
return j;
}
void quickSort(int input[], int start, int end) {
if (start >= end) return;
int partition = partitionArray(input, start, end);
quickSort(input, start, partition - 1);
quickSort(input, partition + 1, end);
}
love from pakistan we need these type of legend to teach progamming
Thanks a lot for Quick Short. Feels easier to understand 🥰
Understood.... 💯💯 Excited for Arrays playlist❤
striver you are the best out of best....this tutorial is just amazing and you are like god for us A big thank you so much for your effort 🙂
Quick sort in Descending order in Python:
def qS(array):
if len(array) pivot]
return qS(elm_grater_than_pivot) + elm_equal_pivot + qS(elm_less_than_pivot)
Code for descending order :-
#include
int fn(vector &arr,int low, int high){
int pivot = arr[low];
int i = low;
int j = high;
while(i=pivot && i
Excellent content about DSA .I am follwing you A-Z coarse and improve my self in DSA day by DSA Thanks for making such a amazing content
at time 23:52 it should be pivot not ar[pivot] thanks bhaiya
Yes bro.👊 😊
bro you are a true saviour !!
Understood sir.
For descending order:
int partitionFunction(int arr[], int low, int high){
int i = low, j = high, temp;
int pivot = arr[low];
while(ipivot and i
Why can't we give while (i
int partition (int arr[], int low, int high)
{
int p=arr[low];
int i=low,j=high;
while(i=p && i
I also completed 2 steps can we connect?
For Decending order
#include
using namespace std;
int pick_place_pivot(int arr[],int low,int high){
int pivot=arr[low];
int i=low,j=high;
while(i= pivot && i=low+1) j--;
if(i> n;
int arr[n];
for(int i=0;i> arr[i];
quick_sort(arr,0,n-1);
for(int i=0;i
Understanding everything u r teaching to us u r magician striver
16 Aug 2024, 2:00 a.m.🎯🔥
Thanks for giving this content for free it helps me a lot
Thanks for recursive effort brother.And till now all your lectures are absolutely awesome 🔥🔥
Thank You anna because of u I have learned something new today🙂
Best explanation ever ❤️❤️❤️
Thanks bhaiya
for descending order
const partition = (arr, low, high) => {
let pivot = arr[low];
let i = low;
let j = high;
while (i < j) {
while (arr[i] >= pivot && i < high) {
i++;
}
while (arr[j] low) {
j--;
}
if (i < j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
let temp = arr[low];
arr[low] = arr[j];
arr[j] = temp;
return j
};
const quickSort = (arr, low, high) => {
if (low < high) {
let partitionIndex = partition(arr, low, high);
quickSort(arr, low, partitionIndex - 1, high);
quickSort(arr, partitionIndex + 1, high);
}
console.log(arr)
};
Quicksort in python.
def partition(L,lower,upper):
i=lower
pivot=L[lower]
for j in range(lower+1,upper+1):
if(L[j]
Manhhhh 🥵, you are awesome. I can see the effort you are putting in! Thanks a lot! ❤
Can't thank you more. Great lectures. Appreciate it.
checking for out of bounds like this makes it simple and natural
while (i pivot) {
j--;
}
Understood! Super amazing explanation as always, thank you very much!!
class Solution {
public static void quickSort(int[] arr,int low,int high) {
if(low
Best , Detailed and Crisp
Your explanations are the best 💕👌👌
awesom explanation , love it learning DSA .
u r just amazing. keep educating man u r blessing for us.❤
// for descending order
just we have to do the tweaks in the how we are selecting elements when which we are stopping when we are finding element smaller in left and stop when we find the element greater the pivot then we just we swap it
than it goes in the recursion stack
public class Quicksort {
static int partiton(int arr [] , int low , int high ){
int pivot = arr[low];
int i= low;
int j = high;
while (i < j ) {
while (arr[i] >= pivot && i = low + 1 ) {
j--;
}
if(i < j ){
int temp = arr[i];
arr[i] = arr [j];
arr[j] = temp;
}
}
int temp = arr[j];
arr[j] = arr[low];
arr[low] = temp;
return j ;
}
static void quicksort(int arr [] , int low , int high){
if(low < high ){
int PartionIndex = partiton(arr,low,high) ;
quicksort(arr, low , PartionIndex-1);
quicksort(arr, PartionIndex+1 , high);
}
}
public static void main(String[] args) {
int arr [] = {10, 80, 30, 90, 40};
int n = arr.length-1;
quicksort(arr, 0, n);
for (int i : arr) {
System.out.print(i + " ");
}
}
}
Java Code:
public class QuickSort {
public static void main(String[] args) {
int [] nums = {3,4,2,1,5,0};
quickSort(nums, 0, nums.length -1);
for(int element : nums){
System.out.print(element + " ");
}
}
public static void quickSort(int[] nums, int low, int high) {
if(low >= high) return ;
int partitionIndex = partition(nums,low,high);
quickSort(nums,low,partitionIndex-1);
quickSort(nums,partitionIndex +1, high);
}
public static int partition(int[] nums, int low , int high){
int pivot = nums[low];
int i = low, j = high;
while(i < j ){
while(i pivot) j--;
if(i < j) swap(nums, i, j);
}
swap(nums,low,j);
return j ;
}
public static void swap(int [] nums, int i , int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j]= temp;
}
}
Kaha se sikha hai aise padana?
vai koi vi nahi hai tumhare jaisa.
Maza aa gaya
//Code for reversing the sorted array using quick sort
// feel free to review
class ReverseSortedArray {
public static void main(String[] args) {
int[] arr = {1,3,5,2,7,6,8,10};
Qsort(arr,0,arr.length - 1);
for(int i :arr){
System.out.print(i + " ");
}
}
public static void Qsort(int[] arr,int low,int high){
if(low < high){
int partition = parrtitionArrray(arr,low,high);
Qsort(arr,low,partition - 1);
Qsort(arr,partition + 1,high);
}
}
static int parrtitionArrray(int[] arr,int low,int high){
int val = arr[low];
int i = low,j = high;
while(i < j){
while(val = low - 1){
j--;
}
if(i < j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[low];
arr[low] = arr[j];
arr[j] = temp;
return j;
}
}
Damn it, i have learnt sorting algorithms a lot of times, but i aways manage to somehow forget.But after seeing this video now i understand it in so much more detail and depth which i earlier didn't even notice. thanks you soo much striver !
Thanks Striver :)
understood Bhayya.The best explanation in youtube😎
descending order code:
from typing import List
def partition(arr,low,high) -> int:
r=arr[low]
i=low
j=high
while(i=r and i
Understood,Thanks striver for this amazing video.
You rocks the DSA
very well explained brother appreciate your efforts
Crystal clear bhaiya 😍
Excellent explanation :)
Awesome explanation! TYSM for the videos
public:
// Function to sort an array using quick sort algorithm in descending order.
void quickSort(int arr[], int low, int high)
{
if (low < high) {
int pIndex = partition(arr, low, high);
quickSort(arr, low, pIndex - 1);
quickSort(arr, pIndex + 1, high);
}
}
public:
int partition(int arr[], int low, int high)
{
int pivot = arr[low];
int i = low;
int j = high;
int temp;
while (i < j) {
while (arr[i] >= pivot && i = low + 1) {
j--;
}
if (i < j) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
temp = arr[low];
arr[low] = arr[j];
arr[j] = temp;
return j;
}
}
//for Descending order
#include
using namespace std;
int partition(vector &arr, int low, int high){
int pivot = arr[low];
int i = low;
int j = high;
while(i= pivot && i n;
// int arr[n];
// for (int i = 0; i < n; i++)
// {
// cin >> arr[i];
// }
vector arr = { 3, 9, 4,1};
int n = arr.size();
vector result= quick_sort(arr, n);
for (int i = 0; i < n; i++)
{
cout
Understood bhaiya! Thank you
26:58 That will be |1 3 2| 4. Right?
Quick Sort Descending order : java Code
private static void sort(int arr[],int low, int high) {
if(low
// condition i
Yes you are right, it should evaluate this first as a precaution.
home work question (to print in decreasing order)-
#include
using namespace std;
int partition(vector &arr, int low, int high){
int pivot=arr[low];
int i=low;
int j=high;
while(i=arr[low] && i
# code for reverse sorted i.e. descending sort
def quickSort(self,arr,low,high):
if low < high:
p_index = self.partition(arr,low,high)
self.quickSort(arr,low,p_index-1)
self.quickSort(arr,p_index+1,high)
def partition(self,arr,low,high):
# modified
pivot = arr[high]
i = low
j = high
while i < j:
#modified
while arr[i] >= pivot and i = low+1:
j -= 1
if i < j:
arr[i], arr[j] = arr[j], arr[i]
arr[low], arr[j] = arr[j],arr[low]
return j
Understood
Striver on TOP!
Completely Understood 👍👍
C++ Code :
#include
using namespace std;
int partition (vector& arr, int low, int high){
int i = low;
int j = high;
int pivot = arr[low];
while(i low) j--;
if(i= high){
return;
}
int pt = partition(arr,low,high);
quickSort(arr,low,pt-1);
quickSort(arr,pt+1,high);
return;
}
int main() {
vector arr={4,2,8,5,6,7,0,1,3,9};
quickSort(arr,0,9);
for(auto i:arr){
cout
understood everything sir so far all sorting techniques
Its a great video, but you should also explain the cases where complexity for quick sort can result to O(n^2) in the case where all elements of array are same and when array is already sorted, in those cases partition will always be 1, n-1.
sorted or even if sorted in descending order complexity will be n^2
by the way, there exist some examples where the code shown can return in out of vector subscript error because the partition index might be returned as 0 and when we try to access pIndex-1 it will of course crash. so put an extra little check where the code just returns if pIndex is 0.
Instead of 3,2,1 it should be 1,3,2 coz we have done swapping b/w 4 & 1 like swap(arr[low], arr[j]) right ?
Understood sir.....u r the best👍💞
Java code for QuickSort in descending order with comments
public class Quick_Sort {
//descending
public static int pivotloc(int []arr,int low,int high){
int pivot=low; //choosing arr[low] as pivot element
//greater or equal on left, less on right
int i=low,j=high,t;
while(i=arr[pivot] && i
After checking all lectures on internet...None has explained better than you
nice way of explaination
little tweaks in partition function for descending case
int partition (vector &arr, int low, int high){
int pivot = arr[low];
int i = low;
int j = high;
while (i=pivot && i
class Solution
{
public:
//Function to sort an array using quick sort algorithm.
void quickSort(int arr[], int low, int high)
{
if(low
Was eagerly waiting for your videos 🙌
Reverse Sort need only 2 changes from original code :
while(arr[i]>=pivot && i
Understood...thank u sir🙂
thank you so muchbhiaya for this masterpiece
Thanks striver this video helped me ❤
understand bhaiya !!!
thank uh so much
understood , Step 2 completed :)
Everything will be same , only we have to do some changes in partition function to get array in decreasing order:
int decendingPartition(int arr[],int low,int high){
int pivot=arr[low];
int i=low;
int j=high;
while(i=pivot && i
FYI - Quick sort takes O(n^2) in worst case so obviously merge is best sorting algorithm out there.