Understanding Sorting Algorithms
Understanding Sorting Algorithms 관련
Every programming language uses sorting algorithms. While programming languages have easy-to-use sorting methods, it can be helpful to understand how they work.
We just released a course on the freeCodeCamp.org YouTube channel that will teach you some of the most popular sorting algorithms!
Haris Iftikhar developed this course. Haris runs the channel Coding Cleverly and he has a lot of experience creating helpful tutorials.
In this course, you will learn selection sort, bubble sort, insertion sort, merge sort, and their order of complexities. This course uses C++ but the concepts apply to any programming language.
Here are the algorithms and topics covered in this course:
- Simple Sorting Algorithm
- Selection Sort
- Diagrammatic Explanation
- Bubble Sort
- Graphical Explanation of BubbleSort
- Insertion Sort
- Graphical Implementation
- Merge Sort
- Extensive Explanation
- Difference b/w the Algorithms
Watch the course below or on the freeCodeCamp.org YouTube channel (1-hour watch).
Full Transcript
(Note: autogenerated)
Sorting algorithms are used regularly in computer science and programming.
In this course, you will learn how the most popular sorting algorithms work using diagrams and code. Coding time with coding cleverly, but this time, we're on a different channel. That's right, coding cleverly is being featured by Free Code Camp.
This video will be about some of the different sorting algorithms that you can apply to almost any programming language.
The language focused in this video will be c++, however, like I said, you can apply the concepts to any other languages of your choice like Java, Python, C, and so on, you would at least need to know the fundamental core concepts of programming, especially the basic programming constructs, like sequence selection and iteration.
To understand this video, Also, make sure to check out my channel coding cleverly, where I've covered almost every concept from programming fundamentals, to object oriented programming all the way to data structures and algorithms and beyond.
Okay, so let's start by writing a simple algorithm for sorting an array.
So first of all, let's include our iostream and encourage you to type along with me to get the maximum practice.
So ash include iostream.
And then we have our namespace standard.
And then we have our integer main.
And we also have our return zero right here.
So we're going to start off with a very simple algorithm.
And we're going to look at its visual implementation.
So suppose we have an array of four elements.
And that's the four sides we have 231, and five.
And basically, this is an array, which is basically indexed having values from zero all the way to three.
So our job is to sort this in ascending order, we know that this is not in ascending order.
So we're going to use a very simple algorithm.
And I'm going to create, actually the implementation here.
So then after that, we go back to our code editor, and we're going to type along, and it's just going to make much more sense.
So suppose we have two variables, and we're going to have one variable, which is going to be enlisted on the top, so we're going to have that as AI.
So that is going to be the first one, which is zero location.
And then we have j, which is going to be the second one, which is going to be i plus one.
So right after the AI is going to be the J and we're going to play apply actually a nested for loop.
So first for loop is going to have some condition, though after inside, there's going to be a premonition that says j is less than I.
So over here, what it means is that the array of that j m, the value of that j is less than the value of that I now that's what I meant by array sub j and less than arrays of absolute value of j less than the I value, this is our condition that's going to be inside of our nested for loop the internal one.
And this is the condition if it's true, we're going to create a temporary variable, and we're going to store the value of i so whatever's in it, so in this case, it would two is in it.
So two is going to be stored in temp, so then we're going to swap it using a swift same swapping methodology is equal j and j is equal to temp variable.
So whatever the temp value was actually was if value is value was two, that's going to be in J.
So actually, we just implemented a swap methodology here.
So right after that, we're going to check in this condition.
So in this case, we have two and three, so a value of three is actually greater than the value of two.
So in this case, the condition won't be true, and it won't execute.
So this is just going to skip the value.
And we're just going to make our j now increment to the next portion.
So we're going to skip this.
So I just crossed this out.
And now I go and put this next pointer over here and J.
So now I n j, now you can see that j is value is less, now we have one and we have a comparing with two.
So g one is less than two.
So this condition is now true, you could see that one and two are going to be located talking about the values.
And now that the condition is going to be satisfying here.
So we're going to look over here that temp is equal to i, and then we have the value which is I so what is I to so that's going to be in that temp variable is equal to j now j is actually one, so i is equal to one, so we're going to have here i is equal to the value one.
Now after this we have j so j is equal to Now the value of temp.
Now temp value was actually two.
So now you can see that this swapped value.
So we have I, which is now one except for two now two, and now over here in the J position instead of one.
Now we have the value of two.
Now you can see that swapped out and now Jays value going to be incremented.
So you can see that the index is now no longer going to be here.
And now it's going to be in the fifth Bay actually the last one, which is where the fifth value is.
And we're going to be checking again we're gonna say i and j will say j is less than I, well, no, it's not j is greater than I.
So now this portion of that nested for loop will be terminated.
And what what's gonna happen now is our eyes are going to be incremented.
So I plus plus, and we're gonna have I know, plus one.
So originally where j was right, so now there, that's where i is going to be.
And actually, what we see here is that j is always going to be i plus one, like we mentioned before, this is our sorting algorithm process that we need.
So it's just going to be side by side, or they're going to be a jacent to each other in initially, and then after that, they're just going to be incrementing.
So like, just like Jays position, so we have j over here, and we have i and j.
So if I look over here, we have I, which is three and J, which is to check the condition.
Now that's true again.
So what's going to happen is that j is less than i that is true.
And we're going to process this temp is it, temp is equal to Now you could guess what's happening here.
Now temp is equal to the value of i, which is three now, so three is going to be placed here.
So there you go, three.
And then after that, we have i is equal to Now the value of j, j is actually two, so we just gonna have two over here, i is equal to two.
And then last one, which is j is equal to the value of 10 plus 10, plus three, so that places over here, so now we just basically swapped it again.
So we have instead of three, we have two over here, and instead of two, we have three over here.
So you can see now that j is now going to be incremented, again to the last one, and we can see i is just in the same exact position, and zero is going to compare two and five.
Well, that condition is not satisfied for this condition, so is just going to increment that process again, i and j now is going to compare and say three and five, while that condition is also not true for that while loop to be executed.
So now we have this i and j in red.
So you'll see that there's nothing to be changed.
So we have actually, our algorithm is working.
And we see that 123 and five, see 123 and five, there are in ascending order.
And that's how our algorithm was supposed to work.
So this visual implementation of this algorithm helped us and now we could map this into our code.
So we're going to be right now typing, so I would encourage you to type along with me.
So let's just get things started.
Okay, so the thing here is that we're going to have to create an array, and I call it an array, and I suppose one is have a size.
So I could define something over here on the top.
So I say hash define, and I say Max, and I say that's the 100. Alright, so this is the maximum value, so it just put max here.
And what I could say here is that, I could ask the user to enter a number and, and that will be the size and it should be in between zero to 100. So it's going to be input, and then it's going to be n now I need to define an N here, so I'm just gonna say integer.
And so this is the integer and now inputting values in an array.
So in putting values in array with a new for, don't say int i is equal to zero is less than n, I would say i plus plus really simple.
And then we have the RAND function that's going to put values randomly inside of the each indices, so we could say array sub, I would say, just the RAND function.
And that's it.
So this is going to give a number between zero to the RAND Max, whatever the integer Max is.
So what we could put here is now we just have to include one more header file for the RAND function.
So it's called C standard library.
And there you go.
So C standard libraries don't know we have values inside of this, let's output our array.
So outputting the unsorted array, so unsorted array, we would just basically say for int, i is equal to zero, i is less than n, and then we have i plus plus, and then we say console, output array sub sub i, and we put this space.
And hopefully, we'll get an array just put an end line right here at the end.
And now I save my code.
So I'm going to run it using my G plus plus compiler.
So over here, I'm going to be writing g plus plus my name, which is part one, and we have CPP, and hopefully, it's going to be compiled.
Now we just say a to run it, and through a number n.
So basically, I could say 10. Now it's going to give me 10 random numbers for my eight array.
So it has 41, this, this and this and all the way to 10. So you can see that these are 10. Let's run this one more time.
And now I'm going to input 20. Now it's supposed to give me 20 random integers.
So now though, there you go.
How about having 50 no 50 random integers.
Now you got my point over here.
It's creating a randomized array.
And putting some random values.
But you could see over here that these are not sorted in any kind of order.
They're not in ascending node or are in descending.
And our that's our job to put that.
So it's a 41. And you can see that this is a number that's greater, but then after that you can see a smaller number.
And what does this even meaning.
So we need a properly managed array.
So let's create a properly managed array.
So what we can do here is right after this, let's create a sorting algorithm.
So sorting, and array.
So how are we going to sort this array? First of all, let's go and open a for loop.
So let's say for int i is equal to zero, i is less than n, and then we say i plus plus.
And then right after this, we can put on another input array.
So we could say, this another loop, that's going to be nested inside of the beginning one, so it's going to be J.
But this is careful.
This is the next value after the array.
And I'll tell you, what's the reason behind this, say j less than n, and we say j plus plus.
And now inside of this is basically our concept that's going to be applying with array sub j is less than array sub i.
Now what does this mean? I'll tell you all of this.
So suppose we have an array.
And that says that if array sub j is less than arrays, because look at this, so this is an array, and you will see that it's an order.
So you can see that this is this I value which is starting from zero, and this is a j which is starting, which is greater than I want one times, so you'd see that j is this.
And this is now if I had a randomized or raise, oh, let's say five over here.
So you could see that this is not in ascending, it's basically 10. And then it's five, why is five over here, something bigger should be appearing.
So the condition here is that erase sub j is less than array sub i.
So meaning if array sub j, which is this is less than array sub i.
And that is the case.
Now what we want to do, we want to swap the values.
So what we could do by swapping the values, so var five could be over here, and the original value 10 should be placed over here.
How do we do this, because 510 30 and 40 will be then sorted.
And the thing is that we're going to have to create an input integer, temporary, something.
So we're going to put that in assign that with I.
Now once we have that assigned with I now what we could do here is that we could change a race of AI.
And we could say to that to a race of J.
So we're assigning a race of eyes value with array sub J's value.
And now we can have a race of J's value.
And we'd like to put that as a temp value.
So this is going to improvise our array in a sorted fashion.
And it's going to be in ascending order a sc n di, N D, or D er.
So this is going to be in ascending order.
So it's going to check and then after that, it's going to do this, it's going to go into our next iteration, which is going to be is equal to one.
So plus plus increments to this, so it's going to be this value, and then it's going to be checking with this value.
And it's going to see if it's the case that it's not right, it's going to swap it out, it's just going to next, do this next iteration until the array is done examining.
So once it's done, you can just break out the loop.
And once your break, like your free, so what's once you're free, you return to zero.
So this is going to give me my array in ascending order.
But now we don't have anything displaying it.
So let's display this array.
So I'm just going to write comments shorting the array, now we're going to display the, so let's just say the sorted array.
So displaying the sorted array, we just do a basic for loop, i is equal to zero, I'm gonna say i less than n, and we say i plus plus.
And then over here, which we could add is basically console output, and we say array sub i.
And then we say this.
And now let's just put an end line right here.
Now let's run the code.
So basically go back to our G plus plus compiler.
And we're going to be running our code.
But first of all, let's compile it.
And I'm just going to give a hyphen o flag to indicate that this is a new executable, and I'm just going to call it run.
So I'm going to hit the compiling button compiling is successful.
Now we're just going to run.
So now you'll see enter a number and so enter a number and meaning that let's just enter some random number and it's going to create an array with some randomized values in each indices, so let's have 20. Now these are 20 random numbers.
You will see over here for 2041 and all of this which is unsorted.
It goes in random order.
And then after that, it sorts it.
And you can see my sorting algorithm does the trick and sorts them in ascending order.
That's pretty amazing.
Okay, now let's do one other thing for us to have a descending order fashion.
One other thing I want to do here is that, I want to tell that this is going to be the sort of, so I could just write a console output, and I'd say sorted.
So sorted.
And right here displaying the sorted array.
And the other thing that I want to do is I just want to show you how descending works.
So this less than sign, which is arrays of J, less than arrays of I will just be turned into arrays of j greater than arrays of I.
So if it's greater than swap it, so that's basically descending order, so I'm just gonna change this ascending to d, e, s, e, n, di, N, G.
So this is now going to be in descending order.
So it's going to run again.
So I'm just going to compile this basically.
And then we're going to run it.
And now let's have a value like 22. Now you have these values, which are 41. And all of this in random order.
And then after that you call the sorted basically prompted out on the terminal screen.
And then after that, you sort them in descending order fashion, and look how awesome that took.
So that's it with this one.
And now let's continue with the other sorting algorithms.
So the next sorting algorithm is called the selection sort one of the most common and most famous, well known sorting algorithms in the world.
So how we're going to implement this is basically first type along, and we're going to be explaining side by side, as well as gonna give a brief explanation at the end.
So just keep on typing along with me.
So hash include, we're gonna have input output stream, and then we're gonna have using namespace standard.
And then we also have integer main.
And we also have the return zero.
Now, what we're going to do here is basically, first we're going to create a swap function.
So what I'm going to be implementing is basically a swap function, so void, and then we have swap.
And then we have basically an array we're going to have, and it's going to be swapping.
So I'm going to show you that it's going to have an x value, and it's gonna have a y value.
So it's going to be implementing that famous swap function process that we've been doing.
So what's going to be doing is basically, integer temp is going to be having a sub x as the first value, so a sub x, so a sub x is going to be equal to a sub y, and then we're gonna have is a sub y equals to the 10th. variable.
So and that's how we swap something.
So suppose we have an array inside of it, and we just call it an array.
And we're going to have some values to it.
So let's say some random values.
And what we want to do is basically, we want to swap the process over here, if we have some random values that are not matching, and we want to swap them, we could use a swap function like just we did in the basic algorithm in the beginning where we did ascending order.
So basically, we're implementing selection sort.
So we created our first function, which is swap, the second function that we're going to be doing is basically the selection sword.
So how this is going to go is basically we're gonna have a void.
And we're going to call this as a selection sort.
And it's going to have two input parameters.
First one is going to be the array, and the second one is basically going to be the size of the array.
Now inside of this is going to have the location index, which is zero, it's going to always start from zero array start from zero, just that and now after that, it's going to loop through this, so it's going to be i less than n minus one, we're going to loop to the last the last element, so n minus one is the last element, and then we're going to have to find the value that should be smaller than the value that we're specifying as is zero, and it should be like swapping the function, so we're going to have to indicate one j over here.
So it's going to be called, and we're going to use another function, which is going to be called location of smallest.
And don't worry, I'm going to be teaching what this is.
So basically, we're gonna have a sub i, and we're gonna have n minus one.
So we're just gonna have three input parameters, here, we're gonna have the array passed in, and you know, this is passed by reference.
So it's always going to be the same array no matter where you're going.
And then we have iron, which is going to be the current location, it's always going to be incrementing.
And it's going to be zero over here, it's going to be changing.
And over here is the ending point.
So that's the last one ending last element.
So swap is going to be implemented here.
And it's going to have three input parameters just like we did before.
So it's going to have the array, which is small a, and then it's gonna have the size of the eye and it's going to have this J.
So basically, I which is going to be the index, so it's going to be the first element and second element and wants to swap them.
So it's going to be implementing the swap function and it's going to be incrementing i plus plus here.
So this is how it's going to be doing now we need here is the location of smallest function.
So that doesn't make it oh right here.
So what we're going to do here in the location of smallest is basically have a return type.
Hello, okay, because it's going to be returning a value of J.
So you can see that j is integer, so it needs a return type at the end.
So over here location of smallest, let's have some input parameters, the first input parameter is the array.
And the second parameter is the s.
And the third input parameter is the ending point.
And you might be asking why I did this.
And you can see over here that the starting point is going to be I, the ending point is going to be n minus one.
So it's always going to be checking at the end.
So it's going to be looping through this whole array and trying to find the smallest.
And when it finds the smallest from I, then it's gonna swap the values in the swap function.
And that's how we're going to be implementing this selection sort algorithm.
So if I'm going to create an AI over here, I'm just going to create intermediate intermediary variables.
One is going to be Isaac s, so I S.
So AI is going to be as the starting point, and then we're going to have j, which is going to equal to basically I not s, so we're going to implement it, and we're going to say whatever it is, that's going to be in j and I over here is the starting point.
And then what we're doing here is that basically, we're gonna have a loop again.
So while we're gonna have i less than or equal to E, which is the ending point, now, if A and then we have a sub i, which is the first element, if that is less than a sub j, if we find some kind of thing that is greater, so a sub j is greater.
So we would say is j is equal to, I just want to swap right, we want to locate it.
And then after that, what we want to do is basically increment it using i plus one, right, so that's going to be incremented.
And then we're going to return the value object.
And don't worry, I'm going to be explaining this through a graphical representation.
So you're This is how it's done.
So we have our three functions, we have a swap function, and we have a location of smallest function.
And we also have a selection sort function, let's create a display function to display the contents of the array.
So it's going to be called display, it's going to have an integer array, and it's going to have a size of the array, which is n.
And what you're going to do here is basically it's going to start from zero.
And what how it's going to be implementing is basically while the i is less than n, and then we're going to be displaying the contents of the array by using a sub i.
And we're going to have the double quotes over here, which is space and just going to, it's going to keep on listing them out.
And then it's going to print an endline over here just to make the format a little more prettier.
So right after that, what we'll do is basically have the array over here specified, let's just create an array, which is going to be called arr.
And it's going to have some random values.
So it's going to have 100 to 12, I'm just giving random values over here, it's just in random format needs to be sorted using my selection sort function.
So I'm just gonna pass this in.
So you can see that this is random.
And now what I'm doing is basically calculate the size, how to calculate the size, one of the process I want to use is basically the size of operator size of operators is going to pass in, and it's going to have an array, and then it's gonna have the size of basically the integer variable.
So basically, you will see that this is the data type, and it's going to be for the array is basically the whole thing.
So we'll see 1234567 and eight and nine, nine, multiplied by four, which is basically 36. And now 36 will be basically divided by the integer, which is going to be four.
So 36 divided by four is going to give you the value, which is nine.
So nine is going to be the answer right here.
So once this is the size, I'll just comment over here and say size equal to nine.
Why don't we want to do here is basically we want to implement our selection.
So first of all, let's just display it.
So let's just display and we're just going to pass in the variable and the size.
So it's just going to automatically display because it's a void function, and its purpose is to display it.
And then right after that, this is called our selection sort of function.
And it's going to ask for array and also a size.
And then after that, we'll just display our selection, sorted array using array, and then when you have size.
So once I do this, I'll just execute and running.
So basically, I'm going my terminal screen over here, I'm going to write g plus plus, I'm going to use the selection sort dot cpp.
And all we know that by default, it's going to be a, so I'm just going to run it and I'm going to say Oh, and I'm going to say selection sort.
So now it's compiled, and I was running through a selection sort.
Now you'll see over here, we have some random stuff what's going on.
Okay, so something went wrong Ctrl T, to break the code, something went wrong in this code, and let's just check what it's wrong.
What's wrong in this.
So we have iOS and then we have it's incrementing.
So this is processes okay.
And minus one is okay, there's some infinite loop that's been created using selections or array and then size.
And so let's just look over here.
Okay, so I forgot to increment this i plus plus.
So just right here, I didn't commit.
And now it's going to be working.
So basically, we were done that, and let's just run this code once again, selection sort.
And now let's call us and look at that, we had this array, which was unsorted, which is 102 12 193 90, whatever 32. And now, what we did is passed in the selection sort, and it's sorted the array for us, I mean, 11 1239, in ascending order, now ascending, what is that, like, if you have the same value, it could be equal, or asked to be greater.
So just in case, if I have a value, like 11, and 11, they're gonna be in the same adjacent locations.
And then after that, it could be a bigger value.
So that's sorted.
In selection sword, I really hope you enjoyed and you understood, so what I want to do is, one other thing is basically show you how the implementation is done.
So suppose that there are arrays sorted like this in the memory.
So we have some kind of indices.
So we have like five, and we have four, and we have three, we have seven, we have nine.
So we want to sort this in ascending order.
So what we're gonna do by default, with selection, sorting does is that it sort makes this eye as the index of zero, and it will check for J.
So what my process here is like that location of smallest will be called.
And you will see in my code, which is basically in here, so I'm just going to show you over here, what I see here is that the location is zero, and the Y is not less than n minus one, the last element, what we do is we get the J and we put that in the location of smallest passing a, we have the I variable, which is basically going to be zero and n minus one, which is the last element, and it's going to be the location of smallest.
So location of smallest is going to locate for the variable, which is going to be this smallest one, even i less than equal to E if it's less than or equal to.
So if it finds it, it's going to sort that as j and it's going to return that value.
So you can see what's happening is that it find the smallest.
So you see that the smallest here is three, so j is going to be pointing here.
And then it's going to be applying that sorting algorithm, which is going to cut swap this.
So you can see over here that it's going to be swapping, so we have three over here.
And then initially five is going to be over here.
But what we want to see here is that in this text editor is that this is basically displaying so we have a selection sort.
And then once we go back into our selection sort algorithm, we have a swap function swap is going to get this value by energy that's returned from here, and it's going to swap it.
So basically the simple swap algorithm, it's going to swap the both values.
And then after that, it's going to increment and it's going to go to our next location.
So you can see the place over here is going to No, not, it's not going to be pointing over here anymore.
And it's going to be pointing over here.
And now this j is not going to be over here.
So just want to indicate that this j will now going to be pointing somewhere else.
So we have this is now implemented over here.
So I'm going to be incremented over here.
Now this is going to be its base.
And what we're going to be checking now because this is not going to be sorted with three.
So now we're always basically over here.
So now we're going to look for a value that is going to be smaller than four.
So basically, is there something for smaller than four, it's not so that we just increment, and we say I is going to be over here.
Now it's five, if there's something foreign, it's okay, so it's going to be checking all and is going to go throughout the loop until the whole array is sorted.
So I hope you understood this concept of selection sort through this graphical implementation.
Now we're going to go to our next sorting algorithm.
And let's go towards it.
Alright, so now let's look at another sorting algorithm.
This is called the bubble sort algorithm.
And it's going to go as follows.
So basically, you have to include your input output stream, and you're gonna have to do your namespace standard.
And let's just go simply write our boilerplate code.
Okay, so, boy, this bubblesort is going to also deal with swapping.
So we're gonna have to include this swapping methodology, which is basically swap, and then we have an integer array, we have an x value, we have an a y value.
And basically, when we go over here, we have actually a temporary, which is going to be assigned to the first value, and then we have the first value, which is a sub x is going to be assigned to the a sub y value, and then the a sub y value will be equaling to the 10th value.
So this is how the swap works.
And now let's have a bubble process.
So the bubble process is a little bit different.
How it's different, is that from selection sort that we already covered, we actually went from the top right, so we went from the top and then went went our way to the bottom.
So in bubblesort, we're going to go bottom to the top, so I'll just explain it.
So first, just type along.
So it's going to be bu BB le Baba.
And then what what this process is going to do is it's going to do some specific process, it's going to get an array.
And it's also going to get the size of the array.
And we're going to go back to this a little later.
So let me just, I just wrote a signature right now.
And I'm going to go and talk about the void bubble process.
So the bubble sort actual functions, this is the actual bubblesort function.
And what we're gonna do is basically, it's going to have that same integer array, which is right here, and then we have the size.
And so now over here, what we want to do is basically start from the portion what I was saying that bubblesort is going to be adopting.
So the bubblesort is going to say, integer I integer i is equal to zero.
And what we need is while we have i is less than n minus one, the last element, we're going to have bubble process.
So BB, BB le bubble, and it's going to have the rate and the end value, which is n is going to be the size is going to be the rate and it's going to increment it to the weight.
So it's just going to go and increment.
So in the bubble, what we're going to have is in here, now we're going to open it, and we want to start so the bubble process is going to be from the I.
So it's going to start from the last element.
So that's what I was talking about n minus one is the last element.
And it's going to go like while and we have basically i greater than zero, so i greater than zero.
And now inside of this is if we have a condition that if a sub is now a sub i should be less than a sub i minus one.
Now, this means that there's an A sub II, if it's the top portion is greater.
So what you want to do is that if a sub i is less than the ACI minus one, what you want to do is swap it, so we're going to swap it using this swap function that we already have, it's going to take a it's going to take the AI element, and it's going to take i minus one.
So that's how it's going to swap it.
And we're going to have a generically having going minus minus because we're starting from n minus one, it's going to go all the way to zero.
So this process should work.
So now after that, we should have our display function.
And we're ready to go.
So basically display over here have an array.
And we also have the size of the array, which is some kind of size, I will just call it as that.
And now inside of it, we need an input.
So I will just say some kind of is equal to zero integer.
And then we have the loop process, which is going to start from i less than n.
And then soon as go, so basically is less than n and you want to process it. So array. And then we have the ISO value.
And we're just going to keep on going like that, until we reach our ending point.
So which is console output over here.
Yeah, just to make it a little more similar to the previous one, I'll just change this to just and because this one's matching here.
So now let's create an array over here.
And I'm just going to call it as integer array.
And I'm just gonna give some random elements to it.
So let's just say this.
And then it is and then something like that, this, this and 33. Okay, this is just random stuff.
Now I want to sort this, so I'm just going to first display.
So I'm going to display, I'm going to say array and alternate my size data type.
So actually my size variable.
So I'm going to have size n over here, I'm going to say size of n, I'm going to have the array and I'm going to say size of and I'm going to have the INT it's going to give me the size.
Now what I can do here is basically have the display function call and then the sorted function, so it's called bubblesort.
So I'm just going to name it bubblesort.
I'm going to pass in my array, I'm going to pass in my size.
I'm going to display once again.
So I'm going to display array, and then I'm going to pass in the size.
Now, I suppose to work.
So let's just go to our c++ compiler over here, just type bubblesort bbls o r t, and we say dot cpp.
And let's just name it something like hyphen o bl s o r t.
And there we go write, compile.
And there you go.
It ran Whoa, what happened over here, I think we did the same exact mistake.
So let's just go back over here and see where we went wrong.
Okay, so we just forgot to increment on wild loops to remember to do this.
This is really important.
Okay, so i plus plus over here.
So that is just loops out and it doesn't cause an infinite loop.
So over here, and let's just go back over here to compile it, recompile it and running it again.
You can see that my original array was 102 and then 293, and then 1939, and all of that and then once we passed in our bubblesort Actually sorted out sum from 1138 102. And all the way to the last element.
So that was pretty cool.
Uh, sorting an array in ascending order using bubble sort selection sort, because the, the methodology was basically a little bit different.
So I just want to show you how this is implemented in a graphical wait.
So so the implementation of the bubble process is basically similar to what we did with selection sort.
But in actually reverse order, we have this swap function that's going on, but we have this visualization that could help us understand how this process is working.
So suppose we have some random values, here, we have three, we have five, we have one, we have four, and we have, let's say three.
Now, the bubble process is going to work like this.
So let me just go over here.
And now let's see.
So it's going to start from the bottom, and it's going to compare these two values.
Now it sees that three and four now would you mean that is basically bubbling, meaning it's liquid portion is on the bottom and liquid portion is basically heavier than the Bubble bubble is lighter bubble makes it flow on the top.
So when you compare a liquid and a bubble, bubble is lighter, so bubbles should be on the top.
So this isn't exactly the same thing.
They're talking about the weights.
So for weight is heavier than three weight, so four should be on the bottom, and three should be on the top.
So this is one actual process, what's happening here is that the swap function will be called, and this is going to be changed to three.
And this is going to be changed to four.
And then after that bubble will go up over here one step level, so it's going to go from here.
And now it's going to go over here.
So now it's going to compare three and one.
So three, and one, actually, what's different now. So you have over here is basically you say one and three, so actually, it's okay, so three is heavier than one.
So when it's okay, so go again, we're one in five.
So five is heavier.
So basically five will go on the bottom, and one will go on the top. Now.
Now over here, now one in three.
So basically three is heavier.
So three will go on the bottom right here.
So just three is on the bottom right here, and then the one is will be on the top.
So this is one actual bubble process.
And you'll see 1353 and four, right now, we basically did our one process here and we sorted till this portion, there is more processes.
And you'll need to do one more bubble process.
So again, you're going to have to go from the bottom.
So you're going to check like this.
So basically, we're going to start again, and we're going to see the values once more.
So forgive my writing, so four, and then we have three, and we have five, then we have three again over here, and we have one, so now four and three, which is heavier, it's okay, go up here, compare these two values.
Now three and five.
So three and five, actually, five is heavier.
So five will go on the bottom.
So five is over here, just cross this one out, and this portion will be having three now.
Now three and three, well, actually, it's the same equal, so it's going to be okay, so one, okay, so it's okay, so 13354. Now, one more process.
So after one more process, so we're gonna have one more process.
So let me just erase all of this, how we're going to have an even one more process.
And now, this should be our final bubble process.
So there's just look at the values again, over here, and then over here, and then over here, and then over here.
So this is one, and then this is three, and now this is three as well.
And now this is five, this is four, so it's going to start from the bottom, and you see that five and four, well, five, and four, this is different, this is heavier, so the heavier portion should be on the bottom and the lighter portion should be on the top.
So four is going to be over here, and then five should be over here.
So five, four, and then 3311 inch.
Okay, so this is our exact sorted array.
And this is how we're going to be sorting our array in bubblesort, a slower and it depends on the number of inputs.
So it could vary and exponentially grow as the inputs increase.
So that was bubble process.
Alright, so now let's jump into Insertion Sort.
So this is pretty much different from the other two that we've included right now, which one was selection sorting, the other was bubblesort.
So I would just encourage you to type along with me.
And explanation we'll be doing side by side.
So let's just go and include this main and then let's just go over here and then return the zero.
Okay, okay.
Now, what's gonna happen here is that we're not going to have a swap function like we did with the other ones, what we're going to have is basically some differences.
Now, the differences is that we're going to have an insertion sort function, and the insertion sort is going to basically have an array, it's going to have one more thing that is going to be inside of it.
So the first thing that's going to have is going to be the size.
This is pretty much the similar.
And one thing here is that it's going to start from one not from zero, like others that do because we're assuming something and assuming is that the assumption is basically that some portion of the rate is already sorted beforehand.
And we just have to like insert elements B into that sorted array, and that's how our process is going to be done.
So we're going to go and we're going to have a while loop so that I could tell you that it's going to go in a while loop, it's going to go to end and it's gonna say insert Insert ight.
Now this is going to be the function that's going to be called.
And this function is going to take in an array, it's going to take in the size, it's going to take in the element, which is going to be the portion that I'm going to be talking about.
And then this is going to keep on incrementing i plus plus, right? Like in other languages, like I is equal, i plus one, whatever it is, man, I can't get the plus.
Right.
Okay, so just like that.
So I plus plus whatever it is like that.
So now let's have the insert ICT element, how do we do this insert, I think so let's go over here.
And after this, let's just talk about the insert it.
So this is actually something that's also void, and it's going to have the insert element, so just right over here, and now inside of it, we're gonna have the array, we're gonna have, basically we're gonna have the integer n size, we're gonna have the integer size, which is specified over here, we're gonna have this key variable media intermediary variable that's going to store our location, or basically the value of our eye.
And now it's gonna say int j, and this j is going to be the last element of that sorted array.
So the last element of that sorted way is going to be i minus one, because I actually after the sorted array, and i minus one, it will be the one last element, so we're gonna have a loop again, and we're gonna have two conditions.
For this case, we have j is greater than equal to, we have j is greater than equal to zero.
And we also have one more condition that j should be actually greater than the key.
So if j is greater than the key, we're just going to keep on looping this, so not a G j, or whatever it is a key.
So a sub j, so let me just have this eight, and then a j over here, not just playing j, okay, so a sub j should be greater, and then the J should be greater than equal to, so what's going to happen here is that eight sub j plus one, this is going to be implementing, and it's going to equal to j, and I hold on, I'm just gonna teach you this, don't worry.
So now we're gonna have j is equal to j minus one, now it's just gonna keep on decrementing, going to the top, like a bubble sort is gonna go up and up and up until you reach that less than equals zero, or if a sub j is gate, basically, greater if it's less than something like, if it's less than, then it's gonna just break out less than the key.
And naturally, what's gonna happen here is if this condition is false, we're gonna have a sub j plus one or two we're trying to implement, and we're gonna put that key thing inside of it that lost value.
And now we just have this display function, which is going to be over here, let's just have it over here.
So void, let's have a display.
And let's have an integer array.
And then let's have the size of it.
And then let's have something which is going to be the AI, it's going to start from zero, it's going to go basically from while and it's going to just check that is less than n.
And then it's going to go and say our console output is going to say AR AR, actually, it's not AR AR, it's going to be a sub i, and it's going to be AI.
And then it's going to be that over here, there's going to be a comma right there.
And then there's going to be an N line, semi colon right here.
And actually not this, I don't want that I just want a semi colon.
And this is going to be incrementing.
So I plus plus.
And then we're going to have a comp end line over here.
There you go.
And let's just get some data from our previous sorting algorithm.
So like a bubblesort, let's just get some of the data, just the array portion, not anything else.
So just get this portion over here.
Let's just copy this, and it's coming here and just paste it.
So I'm just going to go here, and we're just going to paste it right here.
So the only thing I'm going to be changing here everything is okay.
I just want to sort out using my function.
So I'm just going to call it with my Insertion Sort, actually.
Yeah, so insertion sort is going to be called.
Okay, so the insertion sort should be over here.
Let's see.
Yeah, the insertion sort is right here, it's going to go and it's gonna call this one insert, right? It's gonna, it's gonna perform some operation, and then it's gonna go back plus plus, it's going to keep on doing and it's gonna keep on calling this insert it so many times until the thing is sorted.
And then after that, we just display it.
So let's just run this code.
I'm going to go over here my ci plus plus, and let's just clear this screen.
And let's just compile So basically, g plus plus is short Insertion Sort dot cpp.
And then we can say, hyphen Oflag, and then say is short.
Okay, it should be working, compiling.
Okay, so there's a warning over here and 25 no return statement and function returning non void. 25. Let's see. 25. Where are you? 25 is over here.
And there is should be something over here insertion sort and doesn't have a return type.
Wow, should we have a void so let's just have a void over here.
And let's just go back here.
And now let's just compile it recompile it.
And there you go.
Now we have an ins short, so Insertion Sort, and if I run this, you're going to have this sorted.
So 192 290-319-3918 32 Yo, yo, yo 1138 102 293 311. And this is also sorted in ascending order.
Now let's have the implementation.
So this is basically an array, just a random sample, and we have 379. And somehow this is basically sorted from here how that happened, just randomly, it just sorted beforehand.
And now our is going to be over here.
So it's going to be after that sorted, and then j is going to actually be going to be over here, remember, I said that it's going to be i minus one, so this is J, and the first process is going to happen.
So if I go over here back in my code, so my code is over here, and if I see over here that this is going to be the process insert, if it has an array, it has the inside, it has an element I, and it says a key is equal to a sub i, so there's gonna be a variable that's gonna be stored, and j is equal to i minus one, and it's gonna say that j is greater than equal to zero, and a sub j is greater than the key.
So it should be working like that.
And let's see if I could implement here, here.
So we have a key variable.
So this will have a key over here.
So key k, e, y, store that value inside of it, which is going to be something inside.
So what's it going to be, it's going to be the value of, it's going to be a sub i.
So that's four.
So four is here.
Now ignore that.
Now, what you're going to do is basically, you're going to check the condition and the condition is true, why? Because a sub j is greater than equal to zero.
Actually, if I, if I go back over here, where am I? Okay, so you can see that it's j is greater than or equal to zero, it's perfect.
And then a sub j is greater than key.
Now, if I talk about a sub j, now if I talk about that, let me just see, a sub j is basically this nine right now.
And we have a key, which is four so that j sub j is greater.
So no, no fans where we're still working.
Okay, so the work, the thing is going to still work.
If I go back over here, we're going to have a sub j plus one is equal to a sub j.
So that means that we're going to have something that we're going to be implementing, so a sub j is going to be over here.
So we're going to go over here.
So this is going to mean that j plus one is this portion, and it's going to equal it, it's going to sign this line over here.
And what's going to happen is that it's going to go minus one, so j is not going to be here anymore.
No, it's going to go over here.
Okay, so that was now that's one process of that loop.
So that's one process of it.
And let's go again.
So a sub j greater than this is greater j is greater than equal to zero, and a sub j is greater than the key, because the key is for nj seven.
So that's perfect.
Now let's go back over here.
And we see that a sub j plus one is equal to a sub j, and we have j minus one a process again, so whatever that value was, so we have seven over here, that seven is going to be now over here.
Okay, so the J is going to go up here now, and it's going to remove it.
So you can see that there is still over here in this location.
And you can see that the four was removed, so we don't have that value anymore.
That it just changed to nine.
see over here, this is nine.
And where does nine come from? It came from here.
So within seven campervan came from here, so this is happening, so we have this last value over here stored in our key.
So that was the purpose of the key Well, not nice key.
So now we're going to do is basically go over here.
And we're going to see a sub j plus one, and it's going to, it's going to see this condition, is j greater than equal to zero.
Well, that's true.
If I look at that position of here, it's over here, it's greater than or equal to zero, but it is equal zero.
So it's true.
But the second condition is not true, why a sub j is greater than key.
And actually, it's not greater.
How is it not greater, it's less than because it's true on this key is greater.
So this just terminates that loop.
And what's going to happen now is that the key is going to be sorted inside of this, this portion over here, which is j plus one.
So that key value, which is four is going to be over here.
Now, this four is going to be here, 3479. Well, this is sorted.
And now it's going to, it's going to move on and this is I know a new position of i and this is going to be a new process.
So that's how it's going to be starting, if I look back over here.
So you can see a sub j plus one is going to key and then the process starts again, if you want to do it.
And that's how it basically we're going to sort it insert sort, it's going to increment its I value again, it's gonna be a new PlayStation, and then after that position, and then after that we have inserted it and then the process starts again and again and again until the whole damn array is sorted.
And then we get this ascending order of it.
So I hope you understood this concept of Insertion Sort.
Really, if you took this concept and overall, like, take a practice of it, I definitely know that you can do it.
So next up, we're going to be diving into another algorithm.
Let's dive into the merge sort algorithm.
So let's just type along with iostream namespace standard main.
And the return zero semicolon.
Okay, so let's create some functions here.
And let's just explain it the way we do it.
So first of all, let's just find our way for the merge sort.
So we're going to initially have a merge sort function.
So how this is gonna work is basically we're gonna say void, Mr g s o r t, and we're gonna say we're gonna have an array inside of it, and we're gonna have the size of that.
Alright, so this is gonna have another function inside of it, it's going to call another function.
And what this process is called, is called, actually, this is called a wrapper function, and it's going to pass into an auxiliary function.
So this is a wrapper function.
Alright, so what we'll say is, this is merge sort, and it's going to have the array inside of it, it's going to have the size of that array.
And it's also going to have one other additional parameter.
So additional thing is that it's going to have the size but before that, it's going to have one other thing, it should have the index of the first element, so it's going to be the array, the index of the first element, and then the size of that, basically, size minus one.
And this is how the merge sort is going to be over here, we're going to have that auxiliary function called.
So on the top, we can just specify our auxiliary function, so a UXILY function.
And what we're gonna say over here is, we just have the same void, Mr g, s, o, r t, and now the same input parameters, where we have an array.
So we have this input array, we have basically the start value, and we have the end value.
Okay, these are the basically the indexes.
And we call this as the auxiliary function, or we also known as, say, helper function.
These are some of the names we're going to use.
So let's have a base case to this.
Yeah, I don't know what a merge sort is, right? Now, we just basically drew out the thing over here.
So we have this function calls another function.
Another scenario here we have is basically a same array.
And somehow, it's sorted in section.
So you have a first part, which is sorted, and the second part is sorted.
And what we our job here is, don't think of this as just two arrays, this is one single array.
And somehow, we have this first part sorted, and we have the second part sorted.
And our job is to make this sorted in one hole.
And how we could do this is the process of merge.
So we're going to use merge sort algorithm to do this.
So what we can do is, we have to know in advance how the first part is sorted, or the second part sorted, and we have to put a trust, we have to put faith in one process.
And that themes process is called recursion.
And now that's what we're going to be applying.
So you're going to check, and the process is going to go like this.
So we're gonna have this first element two, and we're gonna check this third out this part over here.
So first, first of these two sub arrays, and I'm gonna say two and three, which one is greater, I mean, which one is smaller, so basically two is smaller, so two is going to be planted here.
And then this is going to be incremented.
So this sub array index is going to be incremented.
So it's going to be plus one, which is going to be seven now, and this part is going to remain the same, now three and seven will be compared.
And we could see that three is lower, so three is going to be placed in here.
And now this is going to be incremented to four.
So you could see that four and seven will be compared, and we have four over here.
So four is going to be and this is going to be incremented to five, so five, and seven, and five is now going to be added.
So five is going to be here.
Now, it's going to be 15, and seven, so seven is going to be here, so seven is going to be here now 11 and 15, you'll see 11 is smaller, so 11 is going to be in here.
So is going to be incremented to 19. So we have 15 and 19. So now we have 15 over here.
So 15 is going to be over here.
And then we have this comparative 15 is going to be in committed to plus plus.
So we have 18 and 19. So what what is it 18. So now you can see over here, we assumed that this part is already full now.
Now what do we do? Well, now what we're going to do is basically, this, this last part, we're just gonna append to the end.
So that's our process here, what we're going to do is append these 19 and 21 to the end how we're going to do this.
And you could see by this is just sorted in our ascending order fashion.
And that's what we required.
And how do we do this? And you would ask me, now, if it was worded like this, why not just put like a pre existing sorting algorithm like a merge, like something like Insertion Sort selection sort? Well, that process is going to take longer, and this process is fairly shorter.
That's the crux of merge sort.
And that's why it makes it faster.
It's much more faster as compared to any of the sorting algorithms we've discussed so far.
So now let's go back into our code.
And now start typing along.
So first of all, let's have this merge sort and inside of this we have an array we have this int s, we have this int E, we have a helper function out in the condition we have a base case, now we have this s greater than equal to E.
This is some case that's not true.
It can never be true.
In this case, it will just return.
So this is our base case.
And that F That you could say that this is just not going to be true because start is never going to be greater than or equal to eat.
That means that it's just a logical always you have a start, which is less than equal to E, and I'm talking about the indices over here, and not the value.
So you have a start, like for instance, we have a start here, and we have an end over here, obviously, these are indexes, indices are start from zero all the way to n, right, and the C, start from n minus one, it never does the other way around.
So that's just illogical.
And now we're going to have the implementation Harry, we're going to find the midpoint value of that array.
So this is our function here.
So what we have to do here is basically means is, let me just put these plots back, okay, so our process here is, we have to find the midpoint value, which is right here.
So you can see over here, if I observe here, that I have 1-234-567-8910 10 elements, and if I, if I go from here, like the start value would zero index, and the last value, which is nine, and if I divide this way, two, I'm going to get a 4.5, right, and I'm gonna get the integer division of it.
So I'm just gonna get a four part, the decimal part is just going to be excluded.
So we're gonna have 401234, this is our fourth index.
So this is our fourth index right here.
And what I'm going to do here is I'm going to place that value.
So basically, this is our four index.
And we're going to, we're going to split this here.
And this is now you could see that this is our mid m, outside, this is our m, and, and the stuff that is before is going to be the things.
So 0123 is going to be four and then after this is 01234. So this is five over here, and this is four, and this is our midpoint.
Now, suppose if we added something like, had an odd number, then we'd have even cases here, but in this case, we don't have but this still is our process.
This is how it's going to be implemented.
Go back here, and we have this mid.
And this is going to be a simple function where we're going to do it's going to be s plus E.
Now, this is going to be the the start index and the last index and we divided by two, just like we discussed.
And I know that's pretty, really simple, because this is n minus one I told you over here, and that's the last element is indicating the last element, and it's just going to divide it by two, which is give a 4.5 it's going to be four because of its it because it's an integer division.
Okay, so now let's have that Merge Sort calling you using recursion, that what I was talking about.
So it's going to start from a, this is our starting point.
Now, careful here that it's gonna, it's this is the array, the starting point is S, but the Met endpoint is now M.
Why because now we're going to try to split into two sub arrays with sorted processes.
So we're going to call again.
And the second time we're going to have a array, it's going to start from m n is going to go all the way to the end.
So it's going to be not m but n plus one, because now we're going to have this process additional.
This over here, we have this portion we want sorted, and we want this portion sorted.
So we're just casing we're just discussing right now, this portion, not this, not this thing over here, not this right now, we're just looking at the top.
So so I hope you got the point over here that we wanted to sorted in ascending wise over here and the sending wise here.
Okay, so back over here, we have this m plus one.
And now we call one more function.
And that function is basically the combined function.
And the combined function is going to be pretty much something like this, we have an A array, we have the S which is the start, we have the middle value, which is m which is the last value, which is e and this combined will be defined over here somewhere.
So let's have this combined defined.
So now we're going to do is basically we're going to say void combine.
And if I have that specified here, I would say int a, and we have this array right here, we have an int s starting value, we have an int and which is the middle value. Forget that right.
And then I got the last element, which is end.
And what we could do here is that we want a temporary buffer.
And I'll tell you why just hold on a moment.
So let's just create a buffer over here.
And what it's going to do is basically going to get some value from the heap or is going to get some.
So it's going to be able, it's going to be a array from the heap that we're going to get.
And basically this is going to be representing the for the total size of the merged array, what we're talking about.
And what we're gonna do here is that we're gonna have a kz go to S and we're going to say while so while is over here, and because i k less than or equal to E and what we do here is buffer And we say buffer sub k is equal to a sub k.
And we could say k is equal to k plus one.
Now, what do you mean by this? Now, I'll tell you what, what this means.
The thing is that we're creating a temporary buffer that we're allocating from the heap.
And then we're going to deallocate it using the Delete keyword.
But before that we're using it because we don't want to reassign it in that existing array.
So we want it basically stored.
And then we want something over here.
So I'll just say this portion here, b, u, s, s, e r, this is the buffer, this portion, and this whole thing, I'm talking about the whole thing.
So this is buffer, and this is going to be our output array.
So this is going to be the sorted array, we're doing in two separate things.
Because if we swing just one single array, it's going to cause complexities, much more complexities as just copying the elements.
So suppose we have this array.
So just ignore this part, because it's not sorted right now.
And we just created a duplicate array that had all the values.
So it started from K, and it went, so it said, zero all the way to the value.
Last one.
So if I go back here, you could see that case started with a starting value, and it was less than equal to n value.
And it just said buffer sub k is equal buffer sub k.
So a sub k, whatever the value is, where it's going to store it in the buffer, so it just initialized all of them, and just k plus one all the way to the end.
So just copied, made a duplicate, right.
So now after that we could do is we're gonna have something specified here, right after this.
So once it's copied, bam, i is equal to s.
Now we're gonna have one thing over here, which is J, and we're gonna say m plus one.
Now, I'll tell you why we did this.
And we also have, which is K.
And we said that as S, i is equal to s, come back here, and we have this IO.
And it's going to be over here, which is the starting value, just give me another color over here, I'll just get a little darker.
Okay, so I have over here, which is right here.
And the second one, what we have is this mid, we know that, okay, so other one we have is j is equal to n plus one.
So if I go back here, we have this j is this over here.
And we know that this is endpoint right here, he so you can see that this AI has to go in commit all the way to the M, this is its last element.
And this j has to increment all the way to the end portion here.
So that's how we're going to compare the values like two and three, which one is similar to planted here, go and commit to two plus seven.
And then we're gonna say seven and three, what is smaller, three smaller planted here, and then put the rest.
So that's the process what I'm trying to implement to code, I have to map this out.
So that's why I'm using this diagram.
That's what we're doing.
So we're going to have indicated s, while let's have a while loop.
And this is how this process is going to go I which is that value, what I told you, This over here is less than or equal to m, and j is less than equal to E, this process is going to go on.
So if i less than equal to m, and we have j less than equal to E, we want some process going on.
So if that buffer, be you FF, er, FF er is E I, and then we have less than equal to bu FF er sub j, if this process is done, so if a buffer sub i is less than equal to buffer sub k, then what we're going to do is a sub k, that process what I was talking about, that if it's less or equal than just copy it inside of that, Kate, then the array which is over here, we want to sort it out, so we're just gonna copy here through buffer.
So it's a bu FF, er sub i.
So in the case, if it's less, right, if it's less or equal, and then we just increment is equal i plus one, just what we did over there, just what we did over there.
So if that's not the case, we'll just have an else.
And when I put something in here, so let me just put over here, the case here is that a sub k, a sub k is going to be over here, and it's going to equal to buffer.
So it's going to be buffer, and then we're going to have sub j over here.
So we're gonna have this j in here, which is a sub k, because if it's not the case, it's going to be less, right.
So it meaning if it's less, but if it's greater than the J is gonna be there.
And then obviously, we're gonna have j being incremented, instead of it being intermitted.
So we have that and we have k is equal to k plus one.
Let me just have that.
There you go.
And now we have the condition here.
So this is this case over here.
This is a while loop.
And we have another while after this condition.
Now, I'll tell you the reason why behind this.
So we have this while loop and after this, we have two wild loops.
Additionally, I'll tell you the reason why we need those two.
The thing is that if we compare these two, like, suppose we had this tool, and we had this three, we compare that to was less.
And then we incremented.
It, we're just doing plus plus don't we did, but the case one that we came here at this 19 and 21, how these come, this array just got full, all this was fully remember this portion, but then we just appended these last two inside of this, how do we do that automatic process that automatic process was going to be is going to be done through two wild loops, we're going to be including, and that condition is like if is less than good, or if j is less than equal to eat.
Now this is the two conditions and look at this carefully.
So while we say i is less than or equal to m, so if this condition is like, still there, like it's true, like it broke out.
So the process here is that these two will never become false together, it's always going to be one one of them and not the other.
Right.
So if that case like Jays listening, he that came and then after we still have is less than equal m, what we could do here is that a sub k, and this is the same scenario, what we did with the example, a sub k is equal to we're gonna say, buffer so that we got the thing from buffer, and we said that as J.
And what we do is basically, actually, we're gonna have that set with I because it's eye over here.
And we're going to set that with eye, and then we're going to do is, we're going to increment i plus one, and we're going to increment the K is equal to k plus one.
And if the other cases, they're like, while j less than equal to E, we're going to have a sub k is equal to buffer.
And we're gonna have that as J.
Sub, there you go.
And we have Jay Z going to j plus one.
And we have k is equal to k plus one, it's just going to increment the K value.
And you already know where k is starting.
This is k right here.
So this portion is K.
And j is going to go 1-234-567-8910. All the way when it's done.
So it just keep on incrementing, you can see that j is over here is over there.
And that's the process going behind it.
And then once we're done with it, we don't want this extra memory, we just delete it.
So we just delete our buffer and using this delete syntax, it's basically we're going to deallocate it from the memory.
And that's it.
Now let's just have this additional function that we need is basically, I think, so it's a printed, so Oh, I forgot my main logic here.
I mean, so this is mean, maybe I left it up on the top, yep, that's a common mistake.
Okay, so just delete that portion here.
And let's just have a display function at the bottom here.
So at the bottom value, right here, let's have a display function.
So it's going to be called void, we're gonna have a display, and we're doing is basically having an array, just like the small other ones, so have the size n.
And we're gonna have something which is going to be implementing, like we have temporary, and we're going to have that associated with a sub.
What am I doing x not actually that i is equal to zero, my dad.
So we're gonna have while i is less than n, and then we're gonna say, console, output the array value, array sub i, and put that comma here.
And then we have it just keep on incrementing plus plus.
And yeah, constant output here.
There you go.
And now what we'll do is basically run the code here.
So get a random array again.
So let me just get this array, which is right here, copy here, copy and paste it here.
And let's just change up the thing over here, which is insertion or sword, we're going to have Mr. G, Mr. G, Mr. g sort, merge sort. So let's go back to our c++ compiler, c++, Mr. g, s, o r t dot cpp, Ivan Oh, Mr. G, Mr. g, s, o r t, and a compiled Mr. g s.o RT.
There you go, viola, 110 and then 100 to whatever 293 and then all of that, and sorted in ascending order.
So that was it with merge sort.
And this is much, much more faster as compared to any of the sorting algorithms we've done so far.
So even selection sort bubble sort, Insertion Sort, even the problem that we did in the beginning, because those were of time complexity, old n squared over n squared over n squared over n squared.
But this merge sort is somehow faster, because it's doing the time complexity.
In all n log of n, so Oh, and then we have n, and then we have log, and then we have that n inside of it.
And this is much, much more faster as compared to any of the other sorting algorithms.
Now, if you get like a set of arrays from a text file that I could be doing in my other videos, so stay tuned.
For my next upcoming videos in my channel, you're going to be seeing that we're going to have a text file, and we're going to be looking at comparing how fast is this compared to other sorting algorithms.
Because if we have these O of n squared, sorting algorithms, these are going to take much, much more time as the input value increases, it's going to exponentially exponentially grow.
But as compared to merge sort is just going to be fast as lightning because it's in all and all n log of n whatever complexity.
So hope you enjoyed this video, hope you liked it.
And please make sure to visit my channel which is called coding cleverly, where I have so much content of c++, and I've done data structures and algorithms.
I have done object oriented programming, done the basics, beginner level, procedural programming, and I my my goal is to complete data structures.
And then after that, I advanced to other project based videos as well as new languages and technologies.
So make sure to subscribe to that channel.
And yes, thank you so much for watching.
I really appreciate the support.
So thank you so much, and thank you Free Code Camp for putting my video on their channel.
Really appreciate it.