- 7 minutes ago
Transcript
00:00I have defined the main function of the main function
00:03and I have created a print array function
00:06What does print array do? I have put a single loop in my array
00:10and I have printed my elements
00:13I have to write a function for merge sort
00:14I will write a recursive function
00:16which I will name public static
00:18void type
00:19and in this function we will put the elements here and here
00:23and sort
00:24so I will not need to return
00:27because I will directly reflect all the changes in the array
00:30I will name it Merge Sort
00:32I will have an integer type
00:35I will have a starting index and ending index
00:39In the beginning, I will have to sort the array
00:42I will have to send total array
00:45starting index and ending index
00:47so if I want to call this function
00:49I will call Merge Sort
00:51I will pass the array
00:53starting index
00:53I will pass this index
00:54I will pass the ending index
00:55then what is the length of array
00:57minus 1
00:57what is the length of array
00:59What is the first thing?
01:00First, I will do my work
01:02What is my work?
01:02My work is that
01:03I will remove mid
01:04the mid
01:05What will I get to help?
01:06Mid
01:06I will have to know
01:07how much the left and right
01:09so my mid
01:11will be starting index
01:12plus ending index minus starting index by 2.
01:17I could also write starting index plus ending index by 2.
01:22If you write it, the code will also go out.
01:24Now we will start off our left-hissing.
01:27What is going to happen?
01:28Left-hissing will start my starting index and will end my mid.
01:32So I will call merge sort for array starting index.
01:37After that, I will call merge sort.
01:42I will call array for mid plus 1, this is my right-hissing and ending index.
01:47I assumed that my same function recursively will sort my left-hissing.
01:53This is my left-hissing.
01:55I assumed that my same function recursively will solve my right-hissing.
02:00This is my right-hissing.
02:01After that, I have sorted left and sorted right.
02:04Then I have to merge both.
02:07I will write a different function.
02:08I will write a function in which I can pass my array, starting index, mid-pass, and ending index.
02:15Now I assume that this function already exists.
02:18I will paste a little header.
02:20We will create a little header.
02:21Public static void.
02:23We will name it merge integer arrays.
02:27Then I will add my starting index, middle index, and ending index.
02:32So this is my recursion work.
02:34Now I have to write a base case.
02:36If my starting index is greater or equal to my ending index, I don't have to do anything in that
02:43case, I have to simply do the return.
02:46This is my base case.
02:47This is my work.
02:48Now let's complete the merge.
02:49What do I have to do in the merge?
02:52First of all, I have to do a temporary array to merge both the left and the right parts.
02:57So what will my temporary array be?
03:00My temporary array will be ending index minus starting index plus 1.
03:05Why do I do this?
03:07Let's say that my left is going to 0 to 3 and my right is going to 4 to 6.
03:14Now from 0 to 3, how many elements do I have?
03:170, 1, 2, 3.
03:19I have 4 elements.
03:21From 4 to 6, how many elements do I have?
03:244, 5, 6.
03:25I have 3 elements.
03:27If I have 4 elements in my left, and if I have 3 elements in my right,
03:31then how many elements do I have to do the temporary area?
03:34I have to do the temporary area with the temporary area.
03:364 plus 3.
03:38So how will this 7 come from?
03:39This will come from the last index, which is 6.
03:44I will minus my starting index, which is 0.
03:47It is not necessary, because the starting index will always be 0.
03:49It can be 2, 4, 8.
03:53So what size I will give 6 to 0, but I need 7.
03:58In this case, I will plus 1.
04:00Because the index of my array is 0 based,
04:03so that's why I have to do plus 1 in the size.
04:07So I have to remember this small thing.
04:09I have to write the ending index minus starting index here.
04:12I always have to add the plus 1 if you need the right answer.
04:14What will I have to do for my next step?
04:16The next step is that I have made the temporary area.
04:18Now I am looking at my indexes.
04:20I am making an iterator.
04:22I will initialize it with the starting index.
04:25This is my iterator for the left part.
04:28Then I will make an iterator with J.
04:31I will initialize it with mid plus 1.
04:33This is my iterator for the right part.
04:39So I have made an iterator for the left part.
04:41I have made an iterator for the left part.
04:43I have made an iterator for the right part.
04:45I have made an iterator for temporary part.
04:52I have made an iterator for the left part.
05:06I have made an iterator for the left part.
05:23For the left part, I will do less than the array of J.
05:28This is my left part because I have my left iterator.
05:32This is my right part because I have my right iterator.
05:36So if the left part of the element is reduced,
05:38I would store it in temporary part.
05:40So temporary of K is equal to the array of I.
05:43Now what will I do? I will do plus plus because this i will use, now I will reach the
05:48next index.
05:50In this case, I will do k plus plus.
05:52So i and k will be plus plus because I have changed something in both.
05:57Now I have to add them further.
05:58If this condition is not true, I have to add the right part to the element and add temporary.
06:04So what will I do? Temporary of k is equal to my array of j.
06:09And now I will do j and then I will do k.
06:12I will summarize it. Merge.
06:15I assume both left and right parts are sorted.
06:19Where are sorted? In this recursive function.
06:22Now I have to merge them.
06:23I will make temporary area to store both elements.
06:27Then I will make an iterator for the left part.
06:30The other is right part.
06:31The other is temporary.
06:33Now I am checking, until my two parts will not be finished.
06:36What is the first part of the element from the second part?
06:39If it is like this, add it in temporary.
06:41If it is like this, add it in temporary.
06:41No, add it in temporary.
06:43Now there is k plus plus,
06:45Now there is k plus plus.
06:45I can add it in two conditions.
06:47So I will write this k plus plus.
06:51If it is i or j or k,
06:53then k plus plus is here.
06:55Now there will be all elements copied here.
06:57But as I will finish one part,
07:00I will finish my left part.
07:01My left part is complete.
07:02But j is also saved.
07:03Because it is and condition.
07:04So for left over elements,
07:07I will write a while loop.
07:09I will copy all the elements of the first part.
07:12But in the second part,
07:14I will write a while loop.
07:16And the second part,
07:17I will write a while loop.
07:19I will write a while loop.
07:20First, I will write the left part.
07:23If there is something left in the left part,
07:25then I will write less than or equal to mid.
07:29Then what will I do?
07:30Then the temporary of k plus plus is equal to my array of i plus plus.
07:35What will I do?
07:36I will combine this condition and this condition
07:38and put it in the index.
07:40And I can do this.
07:41I have read the unary operators.
07:43What will I do?
07:44I will take the current value of k and increment it.
07:47What will I do?
07:48I will take the current value of i and increment it.
07:50So this is a very small method.
07:53I have used the same method.
07:54Now what will I do?
07:55I will do the same part in the right part.
07:57What will I do?
07:58While my j is less than or equal to my ending index.
08:01Then I have to equal the temporary of k plus plus.
08:05Array of j plus plus.
08:07I have copied the elements of the left part.
08:09I will copy them too.
08:10Now what will I do?
08:11I will copy temporary to my original array.
08:15I will put a loop for int i equals 0.
08:19I will score this.
08:20K starts from 0.
08:22The value of k is temporary.length.
08:25I will do k every time.
08:26I will do k plus plus.
08:27I will take another iterator.
08:29I will start with i value of starting index.
08:31And I will do i every time.
08:33I will do k plus plus.
08:33What will I do?
08:34I will copy temporary of k.
08:39I will copy the array of i.
08:40In this statement,
08:43Temporary value of i and original array will be copied.
08:47I will summarize it a little bit.
08:49This was my merge.
08:50I will create an iterator.
08:52Then I will compare the elements and copy the elements.
08:55Then I will write a loop for it.
08:56And in last, I will copy my temporary array in the original array.
09:00This is my merge function.
09:03This function.
09:03And this is my recursive function.
09:05Which is my merge sort function.
09:07Now I have called the main function.
09:09We have already called the main function.
09:10In which I have passed the starting index.
09:11In which I have passed the starting index.
09:13In which I have passed the starting index.
09:13And the ending index.
09:13Array.length passed.
09:15Now what will I do?
09:16I will print my array.
09:18I have already created the print.
09:19I have already created the print array.
09:21Here.
09:22Let's save and run.
09:29Now I have added my sorted array.
09:31In which I have 2, 3, 5.
09:33Then 6, 8, 9.
09:34Then the entire array is converted into a sorted array.
09:37Here there were even elements.
09:39That means I have 6 elements.
09:40Now I will add another minus 2.
09:43Then I will add odd elements.
09:46Then I will add odd elements.
09:47Then the same answer for odd.
09:48The same answer for odd.
09:49The same answer for odd.
09:50The same answer for odd.
09:51The same answer for odd.
09:51So we write the code for merge sort.
09:53If there is a little problem in this code.
09:55Then we have to see a little more explanation.
09:57No.
09:57Then we have to try to do the code.
10:00We have to write it with the class.
10:02Now we have to close the video.
10:04We have to try to do the code.
10:05Then we have to discuss more things in merge sort.
10:09First, let's discuss how to do the work.
10:11The work I have done was that I had a big array.
10:16I have to consider the big array.
10:18I have passed my own 6, 3, 9, 5, 2 and 8.
10:22So what happened?
10:24In this step, it was divided here.
10:27So I made a mid find out here.
10:30Then in this step, the merge sort,
10:33I have to call both merge sort.
10:35So here I have a call for 6, 3, 9.
10:39Here I have a call for 5, 2 and 8.
10:43Then what happened?
10:44We have to come here again.
10:45Now if we have to consider the stack call,
10:47if we have to consider this function,
10:50then we have to solve it first.
10:52It means this part.
10:54We have to solve this part.
10:55What did we do?
10:56We have to divide this problem.
10:57We have to divide this part.
10:58We don't know how it will divide.
11:00It will come here.
11:029.
11:02So it will divide in 9.
11:03It will divide this part.
11:04I have to divide this part.
11:04Here I have to have 6.
11:06Here I have to have 3.
11:08What happened?
11:09I have to divide this part.
11:11Now this part is sorted and this part is sorted.
11:14So the two parts are sorted.
11:16I have to merge call for both of them.
11:19When I have to merge call,
11:21I will make temporary.
11:22I have to make temporary something here.
11:24I will give it 2.
11:26I have a sorted array and a sorted array.
11:29I will compare both elements in this loop.
11:32I will compare it with this.
11:34I know that 3 is small,
11:35so 3 will come before.
11:366 will come after 6.
11:38But this is temporary.
11:39How is it in the original array?
11:40I will copy temporary.
11:41For the original array,
11:42I will copy temporary.
11:44For the original array,
11:45I will copy temporary.
11:46it means that I will add 3 and 6.
11:50What happened?
11:51In the original array,
11:51it will be sorted.
11:54Now I have to add 9.
11:56First of all,
11:58I will make temporary array.
11:59I will sort these three.
12:01I will sort it.
12:01Then here,
12:02the whole part is sorted.
12:05So,
12:06there is a lot of logic.
12:08I hope that you will try to dry run it.
12:11For some small array.
12:12For n is equal to 3 or n is equal to 5,
12:15we can try to dry run it.
12:19Now,
12:19some important things.
12:20The time complexity,
12:22in the merge sort,
12:23is n log in.
12:25This is a good time complexity
12:26when we talk about sorting algorithms.
12:28Here,
12:29space complexity,
12:30which is how much extra space
12:31we have used.
12:32It is a temporary array.
12:34That is,
12:35we use extra space in the merge sort.
12:37So,
12:38if you have to say that
12:39I have to sort it,
12:40but I don't have extra space.
12:42So,
12:43we cannot use this sorting technique.
12:45Yes,
12:46where we have a place in sorting,
12:48we can use the merge sort.
12:50With extra space.
12:51Another special thing,
12:52that we have taken the process,
12:54recursion,
12:54we have seen here
12:55that we must go into the very circle
12:57and then sort it.
12:59Then,
13:00the large part of it.
13:01Then,
13:01the large part of it.
13:02Then,
13:03we call them depth first.
13:06We have to solve it first.
13:07we have to solve a small part in depth,
13:10then we have to solve a major part in depth.
13:12i mean,
13:12one depth is solved the left.
13:14and then the right is solved the right.
13:16then,
13:16I have to combine both.
13:18So,
13:19we go first depth.
13:20Depth 1, Depth 1, Depth 1, Merge Sort 1.
13:25Now we are reading the details of the time complexity
13:29so there is no tension about it.
13:31Yes, now we can remember what is the time and space complexity.