Merge Sort | Code and Explanation | C++ Course - 19.1
ฝัง
- เผยแพร่เมื่อ 27 ก.ย. 2024
- Complete C++ Placement Course (Data Structures+Algorithm) : • C++ Full Course | C++...
Telegram: t.me/apnikaksh...
Instagram: / dhattarwalaman
Notes of this Lecture:drive.google.c...
accha explanation tha bs thoda code dry run kr k batate tho zyada accha hota
Kahe ka acha kuch samaj ni aata 😢
@@akshaykumar192 😅😅😅😅
It is difficult topic but this lecture of 15 minutes make it easier and make program just in 10 minutes. Thanks Apna College Team and Aman bhaiya.
is this course for beginner.....
@@turbo4free631 NO BIG NO
Code is giving undesired output if array elements are other than descending order.
I have checked many testcases.
bro after seeing your comment i realised the same mistake i made , maybe in int main you forgot to put mergesort(arr,0,length-1) and instead wrote mergesort(arr,0,length)
@@vindhyakumar3434 then also It didn't work
thanks to all who created this free of cost course
instead of using 2 more while loops in merge( ) , u can simply just change the && with || , so..we do not need those extra while loops.
I also thought so does it worked??
No it won't work, might give a segmentation fault/ wrong answer as you are accessing element of an array outside its bounds.
Suppose, i has reached n1 but j hasn't reached n2, by replacing "and" with "or" in while loop, you would still enter the loop, but this time you would be checking a[n1] with b[j], a[n1] might contain garbage value. Same case if j reaches n2 first, b[n2] contains garbage value.
Hope this clears your doubt.
no we can't do that because we would have 0 element in either array so we can't compare
For Time comple. We get fractional part and n so it is simple it is logn*n
Take input from user
fr i couldnt understand anything after didi stopped teaching😂🤣🤣🤣
can anyone tell the problem that i faced in running the same code in the video
my output is 5 2 5 5 5
Bhaiya this code is working correctly only for the input (5,4,3,2,1) while we are changing this input then this code is not giving the correct output so please look into this matter. and please highlight this comment so that bhaiya can read this comment
Thank you
mera bhi output nahi aa raha hai
Yes same problem anyone found solution so please help
Bro which part sorts the arrays of size n1 and n2???
#include
#include
using namespace std;
void merge(int arr[],int l,int mid,int r)
{
int n1=mid-l+1;
int n2=r-mid;
int a[n1];
int b[n2];
for (int i = 0; i < n1; i++){
a[i]=arr[l+i];
}
for ( int i = 0; i < n2; i++){
b[i]=arr[mid+1+i];
}
int i=0;
int j=0;
int k=l;
while (i
@@irshadali-xx1ms thank you bhai 😀😀
In the int main func when we write mergesort func then copy of arr should be sent .
Then how does the sorted array got print by for loop not original array ???
merge is done with only one extra array. it is not necessary to take 2 extra arrays and then merge.
Yes ,by using two pointer
we are using two arrays of size n1 and n2 that is n1+n2=n.
so basically we are using O(n) extra space that is equal to one array of size n.
how?
@@MohammadKhan-ld1xt #include
using namespace std;
void merge(int a[],int s,int m,int e)
{
int temp[e-s+1];
int p1=s;
int p2=m+1;
for (int i=0;im)
{
temp[i]=a[p2];
p2++;
}
else if (p2>e)
{
temp[i]=a[p1];
p1++;
}
else if (a[p1]>n;
int arr[n];
for (int i=0;i>arr[i];
merge_sort(arr,0,n-1);
for (int i=0;i
her voice!!! too sweet!
Great explanation!
Awesome video, thanks for the easy explanation! :)
What does( mid-l+1 ) mean how can I substrate l from mid
As l always starts from 0. Suppose the value of Mid is 3 so "3-0+1" is equal to 4 which should be the size of first part of the array.
Just another way to merge. We can take a single array of size n instead of 2 of n1 and n2. What we do is we divide the original array by marking them with the pointers i,j(not the * pointers xD). We merge and store them in the temp array and at the end we store the values in the original array.
void merge1(int a[], int l, int mid, int h)// low, mid, high
{
int i=l, j=mid+1, k=0, n=h-l+1;
int temp[n];
while(i
brother....can you explain me why the size of " n1=mid-l+1" array is taken? and in your problem also n=h-l+1?..please help I am confused
@@adityagupta3870 ok let's say the array we take has size 10. While calling the function the value passed to low is 0 and the value passed to high is n-1(cuz if size 10 means from 0 to 9), i.e. 9 in this case. Now in the function, n denotes the size of our array(specifically size of the part of the array corresponding to the merge but here i will explain for the entire array cuz its easier to understand that way). So n needs to be 10. now low=0 and high=9, so high-low=9-0=9.
So we add 1. High-low+1=9-0+1=10.
@@sajankumarkar8237 damn bro!!!.. Thanks!!!... Can I have your id or something
... So that we can start with dsa together?
thanks for this amazing playlist!
Please upload web development course...🙏🏻🙏🏻
@Nikunj Manhas thanks Nikunj 😂
merge function is not only to to merge 2 arrays, its is also to sort and merge
But in which portion is the sorting occuring???
@@sohammukherjee_2193 in the merge fn
your absolutely right and maybe didi missed it
Yeah u can say like that while merging we sort them first
Only one of you can teach me correctly so proud you
🔥🔥🔥Verithanam🔥🔥🔥
Isn't the L pointer going to be zero and in what case it will be non zero?
It's special for me because it is on Apna College Video.....first time ever😇1 comment, 1st like😄
th-cam.com/video/2k7pS9wWPTI/w-d-xo.html
Bhaiya Please upload the NOTES OF LECTURE 31 - Strings in c++
Its 13
@@aadityasharma6855 Its Lecture 31
@@saimadhumita2144 yeah
Thank you Aman Bhaiya and Apna College team as now the Notes of Stings in C++ are uploaded
Ma'am bhut axa smjhati h
explanation is just so clear
Mergesort() function seems bit odd for me, since there is no returning statement🤔. I think it should return 0 at end
its a void function bro
well yes but actually no !! Firstly mergesort is a void function so it should not return anything but let's say if it wasn't a void function and something happened in the function but it doesn't return anything,in that case, no one knows for sure what will happen. The program may or may not run i.e it can result in a crash so to avoid that situation we always have return statements even after giving a return in a conditional statement inside a function.
ps: I am not sure if the above claim made by me is totally correct and maybe there is good logic behind it, suggestions will be appreciated.
there are two ways in which a function frame can be destroyed, either if return statement is encountered or if nothing is left in function.
Try to think with a stack diagram. Hope it will help.
@@praveenawesome2182 definitely u r correct i encounter many time no output wthout return statement bt after return statement program gives correct output
Sir notes of this lecture??
Documentation of our program is very important thing because it reminds us the logic behind program make sure everyone will write reason after each code using commenting
ji sir jaisa aap kahen😶
For those who are having doubt in line of code where: n1 = mid-l+1;
see initially we have given l = 0, r = 7 in the array of length 8.
then we will get mid = (l+r)/2 as (7+0)/2 = 3;
so n1 = mid - l +1; will be 3 - 0 + 1 = 4;
If you guys have any doubt you can reply to this comment.
Here, mid is pointer and n1 is length from 0 to 3 (0,1,2,3)
Why do u not get errors, even if u declare size of arrays as variables at runtime
varies from compiler to compiler
you need to declare and take input the variable, which you use as the size of the array, while declaring the array.
THEY SKIP TO THE PART WHEN CODE IS RIGHT YOU CAN SEE IT FOR YOURSELF
EXAMPLE THE VEDI THEY TYPE "mergeSort(arr,0,4);" BUT AFTER EXECUTION WHEN YOU CAREFULLY LOOK IT IS SUPPOSED TO BE " mergeSort(arr,0,5);"
In the Merge function, why did we initialize k with L and not 0
Can we get backtracking part 2?
Amazing👍😍🤩
Don't we have to take dynamic temp array in merge function. Why didn't you get errors?
space complexity ne allow kr dia On ko isl;ie
very good explanation .
I really enjoyed.
output is coming wrong what's the problem behind it.
#include
using namespace std;
void merger(int a[],int l,int r ,int mid){
int n1=mid-l+1;
int n2=r-mid;
int b[n1];
int c[n2];
for(int i=0;i
Love u didi 😘 bdiya pdhaya
Backtracking ke baad toh kuch samajh nhi aa raha!! What to do??
Ek baar poora course dekhlu aur uske baad phirse dekh lunga..... Yaa fir abhi poora concept clear karte huye chalu?
Bhai clear krta chal abhi se wrna pura dekhne tkk itna frustrate ho jaega ki kr nhi paega🤐
expecting better explanation for time complexity
Only legends know video length is 17:10 ,before the video premiere
Kaise bata rha hai bhai tu?
Kaise?
define "legend"
@@II_xD_II map ke icons ko identify krne waaala chart lol
Int n1 = mid - l + 1
Didi ne 8:24 par (mid - l )mein 1 kyo plus Kiya hai agar kisi Ko iska reason pta hai toh pls jrur btana
Best explaination Of Logic And TimeComplexity
I have copied same code word by word but My code isn't running 😒
same here bro wont know what the problem is
Kyo karna hai merge sort jab hum pehle hi Selection Sort, Bubble Sort aur Insertion Sort padh chuke hai ????
Due to time Complexity. Most efficient sorting technique as compared to others.
Function Mergesort how it working samajh nahi aaya
Thanks a lot for this video
Excellent and clear explanation. Thank you.
Thank you mam
THANK YOU SO MUCH!!
Didi iss lecture ke notes add kardo description box main .. Woh blank reh gaya hh
Test Cases Not included--
Code is Below--->
void merge(int input[], int low, int mid, int high){
int b[high-low+1];
int l1=low,l2=mid+1,i=0;
while(l1
Thx for Desi explanation , Ghusenge ghusenge...
in void merge(int arr[ ], int l, int mid, int r). You said in arr[ ] we are getting to small size SORTED array. 1st array from l to mid. And 2nd array from mid+1 to r. And you said now we will make two temporary arrays. then merge them. KINDLY SOMEONE HELP 🙏🙏🙏🙏
But in the starting how this arr[ ] got SORTED small size arrays??
we are using recursion here, merge() function will be called number of times for every separation after mergeSort() function, not only once. And two temporary arrays because we can't traverse and make changes in the same array at the same time.
Thanks 🔥☺️
why is it showing expression must have a constant value while declaring temp array? pls help somebody
Sorry ur eplanation was right ,😙😙😙😙😙😅😅😅👍👍👍👌I was doing in the wrong way
1no. Content 🔥
aced it...!!❤
Thank you so much sister for your informative speech.
Sir, time complexity nahi samjh aai? Please elaborate, the procedure. Or please suggest some materials to practice from.
Are voh keh raha hai ki humne pehele n length ki array ko divide kiya half mai toh hum abb left array ko sort karne ko humko t(n/2)time lagega some for the right half of that array jab hum dono side ko plus karenge tab yee ayega -->>>
i.e.
t(n) = t(n/2)+t(n/2) = 2t(n/2)
but hum divide karne ke baad merge bhi kar rahe hai toh usko humko merge karne ko linear time lagega i.e 'n'
toh final recurrence relartion atta hai ki
t(n) = 2 t(n/2) + n ...eq1
yee aaya hai for the first split jo humne kiya n ko n/2 mai but hum mergeSort mai we divide the input list of length n in half successively until there are
n lists of size 1.
so, if humko left or right half of the array ke liye recurrence relation chahiye toh follow same procedure but iss baar n half hai.
replace n by n/2 in the eq 1
@@sachinbairi6353 thnx bro
@@sachinbairi6353 tumne toh bade acche se samjhaya bro
When God come to help poor students ❤️
CAN ANYONE PLEASE EXPLAIN WHAT IS THE ERROR IN THIS CODE:
#include
using namespace std;
void merge(int arr[],int l,int mid,int r){
int n1= mid-l+1;
int n2= r-mid;
//temp arrays
int a[n1];
int b[n2];
//array ke elements ko 2 temp arrays mein bhar rhe hai
for (int i = 0; i < n1; i++)
{
a[i]=arr[l+i];
}
for (int i = 0; i < n2; i++)
{
a[i]=arr[mid+1+i];
}
//checing when putting the values backing in the k array
int i=0;
int j=0;
int k=l;
while(i
In merge function the second for loop should be b[i]=arr[mid+1+i] instead of a[i]
i have copied same code but my array is not sorting please help
like bubble sort
Program is not working it show error in running in online gdb c++ compiler
I got the code, but why did she use 'l' and 'r' ??
I didn't understand the time complexity part
Great explanation maam, it's clear all of my doubts
Love dey. 🤡
Ma'am mergeSort sahe work nhe kar rahr hy mana bhut bhar check kiya hy liken program main kohe error nhe hy liken arr ko sorrt nhe kar raha hy
output blank aaraha hai. Can anyone help please
any better approach than this while using functions in recursive way??
for better time complexity use quick sort
thanx a bunch
Why is the size of temporary array (mid-L+1)
0th to midth...inclusive
will merge sort work for odd no. elment in an array?
Yes
shukriya
Nice
the array was not dynamic then how it got sorted in main function?
plz someone explain
Mam u r keep saying pointer..
Is that pointer or index?
Bcz pointer should have Asterix(*) sign
Aree Bro Pointer Doesn't Only Means That U have To Take a * Sign , Pointer also Means To Pointing something
@@harshitrathi3077 acha
Roses are red,
Violets are blue,
The title is in English,
So the VIDEO SHOULD BE TOO
in mergeSort function we pass arr of main function by value, then how did this changed the array in main function
Thanks didi for good explanation with less time.
Thanks
I am having segmentation fault while running this code can anyone help??
getting output only when I give input as same you have given but whenever I change my input array sequence or give a sorted array as input code is not working
ye voice switch itni funny thi lol
It is important for us not gonna lie but this is hard.
If it wasn't this important most of us would've skipped this right???
I have copied same code , but it's not running, frustrated af 😑
NOTES PLEASE
Suggestion: please use comments to explain what the variables are
ye th even number of elements pe kaam ni kr rha hai...
in the next while loop, i replaced the while loop with for loop and it was not showing correct results but I don't understand y
Why initializing k as 0 not giving the right answer?
Help please
Because k is the iterator for arr[] array which starts from l and end at r.
how merge function return value as it above declared with void data type
In case of array , whatever changes are made in the array are inflicted in the original array itself that is arr[], we need not return anything. Changes are made in the original array only.
classic video!!!!!
I will like apna college only when it will rectify the isssue.
my time complexity is coming out O(n log(2n))
Amazing
Please put hindi in the description or smtn, I got really confused by the intro lmao
This code is not working properly on gfg😑