Data Structures and Algorithms (DSA) in Java 2024

What are data structures the reason we are talking about this is because if you look at the internet everyone says if you want to get into this company or that company they will ask you a question Based on data structures and algorithms so first of all why such a hype and what exactly data structures are so before we get into data structures let's talk about data see the entire software industry is based on Data when you do a course on it which we call Information Technology it's not about technology it's about information because we work

with information so data is everything so it doesn't matter what technology you learn you basically learn or you work on it so that you can work with data example think about programming languages why do we use programming languages to process the data why do we use database to store the data why do we use AI to generate data Or to understand data right I mean just to bring it down everything is data now then question arise what is data structures now if we talk about any programming language we have something called primitive data types if

you want to store a number we store that in integer if you want to store a a text you store that in a string if you want to store a character you store that in a character of course depend upon different languages the term or the way You store it changes but ultimately you have some types to it where you store the data but what if you have bunch of data and if you want to to store them it's not just about storing data anyone can do that it's about how do you store data efficiently

and you can also save some memory the thing is if you simply dumb the data you are expanding the memory and if you want to search something from the data will be difficult and that's why storing that Data efficiently is very important and that's where data structures comes into picture so data structure is a way to organize and store data efficiently okay so when you say efficiently it means two things first in terms of performance and also in terms of the memory now what about performance now think about this if you if you talk about

any software application which we use it can be a normal calculator or it can be an application like Amazon website or any Application which we use a banking application as well now what we do in that application is we use some features using which you can compute something you can process something example on calculator you calculate on the banking website you transfer money so what you're doing is you are basically building an application which will do some processing and the way you build an application is through algorithms now what are algorithms set of instructions Let's

say if I want to uh add two numbers it's very simple you what you do is you say take two values from the user then perform the operation and give the value back to the user now those are the steps right those are instructions now what I have mentioned the instructions those are called pseudo code because we're not actually typing a code here we're not being specific to a language let's say C C++ Java python Java JavaScript what we are simply saying is These are the steps you have to follow and that's your algorithm right

but yes when you want to make it work you have to convert that into a code which will run on the computer right that's your actual software code and you can use any language doesn't matter right but the pseudo code will remain same now when it comes to processing of data for any task it's important for us to make it fast and also save memory now most of the companies are focusing on this concept Of data data structures is because they want to give a good experience to the user of course right if I'm using

some application I want it to be fast now you will say okay to to make the system faster you can increase the CPU speed you can increase the amount of ram you can do that but what if with the same amount of memory same amount of CPU power you can still make it more faster right and that can be done with the help of data structures now if you know how Do you store that data efficient l in a proper structure and by doing that you can make your application faster because in data structures we

have different type of data structures example let's say if you have bunch of data you can store that in an array but apart from array we have other types as well we have Set uh we have link list so when to use what it's not that this is best or that is best it's it's all about when to use what and to understand when to use What you have to first understand what those things are right how do you decide that this time you have to use at this time you have to use set and

that's where understanding these concepts are very important now these are not the only options we have we have tree we have graph when to use them so when you understand those Concepts then we can think about okay for this situation we will use this and this is why companies are preferring candidates who knows DSA It will help them in multiple ways first it helps them to reduce the cost is because every computation see I know you you might be thinking uh most of the application which we use are free right think about inst now when

we use Instagram of course we are not paying for it but then companies are paying for it right so the meta is paying for for you to use Instagram so because those computations will be happening somewhere maybe meta is using Some cloud service let's say Amazon in this case So Meta is basically paying to Amazon for every computation which you do okay of course they earn from ads but then they are paying for it so what they will do is they will try to optimize it they will say okay if one query takes let's say

$1 or maybe half a dollar can we just reduce it more can we just make it 10 cents so that's the thing they are trying to do and the way you can do that is by making sure you use a proper Algorithm with a proper data structure so why companies are doing it to reduce reduce the cost second to give a better customer experience so that it will run faster and if I search something it should be faster for me as well so as a customer next when companies want to hire people they have so

many candidates right how will they filter those candidates now data structures algorithm becomes one of the way to filter the candidates because if you know data Structures that means you have worked a lot on that particular language and you understand how how a particular system works on the other hand data structures are not the only thing you need to know if you want to be a good developer if you want to get hired there are multiple things needed example you need to have a good hold on a particular language a particular technology you should have

worked on few projects understanding the entire ecosystem not just one language Working with databases working with networking but then DSA becomes one of the important thing there so just to summarize what are data structures so data structures is basically a way to organize and store your data in the efficient way and there are multiple data structures option available there and you will understand that in the upcoming sessions we're going to talk about in the upcoming videos you will we will talk about what are the types of Data structures we have how to use them when

to use what and what are the algorithms available there so I hope you got some idea regarding data structures so of course entire series is important to understand that properly so I hope you're excited we'll talk about a DT which is abstract data type now before we move towards ADT let's talk about data here of course in the previous video when we talked about what are data structures we have talked about data and We also mentioned that in the software industry everything is about data so whatever you do you doing it for data right now

with this data basically you get the data from the user you process data you also give the output to the user or maybe you want to store this data in the database for the permanent storage but the thing is it's all about data and whenever you use any language doesn't matter which language you use what you do is you store that data in Your code somewhere and to store that data we use something called a variable now imagine variable as a box and you are keeping your data inside that box the problem is every box

need to have a type of course there are language which are dynamically typed language where you don't actually mention the type of the variable but in general this box will have a type so that means if you want to store the data you need a box which is your variable and this variable also Needs a type to it or this box needs a type to it now example let's say if you want to store a number so we can use something called an integer or if you have any other point values you can also use

float or double now it depends on the languages how they work but in most of the languages we have something in common we have integer for the normal numbers we have a float for the point values and what if you want to store a text that's why we have string and in Few languages we don't have all these types we have limited types and in other languages we have many but that doesn't matter right in general we'll be having a variable and a type to it now all these type are called data types and they

are system defined data types or you can also call them as primitive types is because it's there in the language itself you can directly use them but sometime you want to use some complex data type and we can create that With the help of some other Concepts example let's say if you want to represent a human or if you want to represent a phone now I love phone so I'll be using that example so if we talk about this phone here now this phone will have a name to it right so it will have a

name it will have a brand of course name is model number then brand then the configuration the amount of CPU Ram all this are your data right so if you want to represent any physical thing In the virtual world we use objects there right now in some languages which are object ored programming we do that with the help of objects example in C we use something called structures so we can define a structure name let's say phone and inside that you can specify what are the properties there in the same way in the objected languages

we use something called class in this class you create different variables with primitive type and then the Box itself Or the class itself is your complex data type or you can say user defined data type user defined because system is not giving you we are defining our own type right so that's about data and data types but let's say if you want to store a bunch of data how will you work with that and when it comes to data structure how will you store this data in a proper way see what happens is when you

talk about primitive types as well every type will have a way to store data of course That's why we getting them right so example examp if you are creating a variable called num now let's say this num is of type integer and then you are storing a value to it now with this variable num you can perform operations as well now what are the options you can do with integer you can add two values you can subtract two values you can divide multiply so you can perform those operations on the number but let's say you

have a string there now with string Of course you will not be adding two string that doesn't make sense right why you will add two names let say nav K you will get a new name okay a lot of parents are doing that for their kids but that's not the idea here right we can't add string we cannot subtract strings but yes with string you can do something else maybe you want to see the size of a string maybe you want to concatenate two strings maybe you want to cut two strings so string are Different

operations in the same way if you are creating your own type this will have data of course but also you have to you have to mention the operations which you're going to perform so we have two things right we have data and we have operations now let's say in data structures you want to store a bunch of data as we mentioned and you want to store so there's a concept of array so if you have multiple data instead of showing them in multiple variables let's Say you have five numbers uh 2 6 12 21 and

so on now if you have all these values you basically store that in five different variables or you can create a single array and you can store all the values there the advantage would be you have just have to use one variable name there so instead of saying a b c d e you can simply say nums you can use any variable do doesn't doesn't matter so what's important is you can use array here now when we use array we are not Basically using a primitive type here we are creating our own type here own

data type which is an array now in this array basically you should be also able to perform some operation example let's say what if you want to read some value you want to uh fetch a particular element you want to search the array maybe you want to add a element maybe you want to delete element so this operation should be possible on that time so in the concept way when you have a type where You can perform some operation we call them as abstract is because the implementation for array changes from language to language and

we don't just have array right so let's say if you want to store a bunch of values we can use list we can use set Q now when you talk about a que here let's say now inside Q we have I mean we have one more option for that which is tack they follow different concepts so let's say if you want to add element in the queue Which follows last in first out which means you have to insert from the end and you will get it from the first of course you can reverse it you

can insert from the start and you can take it from the end the thing is you have you will insert from one end and you will remove from the other end so that is first in first out in stack it is reverse you do last in first out example let's say U to an example let's say for Q we can say a queue which you follow right example if You want to buy a coffee from a a cafe shop of course there's a queue there you have to stand in a queue and then when your

number comes you will get the uh coffee so basically the first person who went there first will be getting the coffee first right in terms of Stack it is different so when you keep multiple books the first book which you can take out is the last book which you have kept there right which is last in first out that is your stack now we have different Way of implementing in different languages the concept remains same right so when you have a concept and the associated operations to it and of course with data which we call

them as abstract data type we also have map but we'll talk about those things later at this point the point to remember is we can create our own types and which is a concept and if you want to have data inside that and also you want to specify what operations you can perform that is Your abstract data type let's talk about arrays so let's say you have bunch of values let's say five values now instead of storing them in five different variables we can store that in one particular sequence right or one variable you can

say now in this array you can store fire values so let's say we have this array here and then this will have a name to it now of course this data will be stored in a memory right and every memory will have Something called a memory location so let's say we are storing this data in at a location 101 now what happens is every time you store a normal variable let's say A Primitive type let's say int and depend upon how much size it Tak so every type will have a different size to it depend

upon the language but let's say we have two bytes now inside your memory let's say if you create a normal variable which is int AAL to 5 five now this particular a variable will take Some space in the memory of course let's say 2 bytes and it will also have an address to it right so every time you in your programming language you say hey I want a value for a the program will jump to the mem location by searching for the address and it will get the value but the problem is when it comes

to array we have multiple values right and we only have one address now that's tricky of course each element here will take the same size if you say int take two bytes The complete array will take 10 bytes is because every element will take two bytes how will you allocate memory now that's an issue so what you do is the array will have a memory but that will that is only pointing to the first location right so if you say the the memory for this is 101 the first element is one01 what about the second

element now that's where we have to use something called a index values so let's say the first element is look is at one 1 so it will have a index value which is zero the second element is 1 then two then three then four right now for five values the index value starts from zero and ends at four now why zero is because we start we have a memory allocated right one1 which represent to the first element so we don't have to give one to it so what you do is the next element is +

one that's why 1 2 3 and then you can just get it right so one 1 let's say if you want to get the third element you Have to say plus two that's how you do it so you got the values you got the index and you also got a memory address to it now with this array as we already talked about ad which is abstract data type we should be able to perform some operations now what operation you can perform on this array now we can perform something called a read operation so what is

read so let's say you want to get the value of a index number three now what what you do in this case is you Say okay my array name is nums and then for this nums I want the value at index 3 so in different languages we have different representation for this but let's say this is common one so nums bracket of three now what your computer will do is it will directly jump to the memory address it's very simple for for that right so you will say 10 1 plus 3 you will get the

value so that's how you do it now reading is very easy and computer takes way less time to jump to That particular area is because the computer knows the memory right because you you are mentioning the index value reading is good it's fast also what about searching now this is tricky because when you're searching you're not searching for an index you are basically searching for a value now so let's say from this are I want to search very simp 17 now in this case your computer has no idea where 17 is because computer only knows

about the memory address of course The values are there but computer has no idea in which location we have that value and do we even have that value so what a computer will do is it will start from the first location so basically you have to write a code to search from the first location you have to check is the first one 17 if yes good we can exit no then have to jump to the next location is it matching if yes good if not next matching yes no next so basically you have to search

each element right and Let's say the element is at the end you are searching you are basically tracking to all the different locations so this is timeconsuming right what if you have a array of let's say th values to to move between these values it will take some time what about inserting now this will be tricky is because see if you want to insert a element what do you think will it will it take a lot of time see if you want to insert the element at the end that's simple you can get the Size

of the array because we also have to have that option of getting a size of the array right so let's say you have five values you you will simply jump to the sixth location which is index 5 and then you will say Okay I want to add a value here let's say the value value is 21 and you can add the value it's it's very fast but what if you want to add a value in between so let's say you want to add that value at the second location so after the first you want to

add the New value now what you will do is you don't have a space there right you can't simply create a new space you can create space at the end so what you do is you basically have to move all the elements and you it's not like you can simply move the elements what you do is create a new block so move the second last element now to the last block then again you have to move every element one by one then you can add your value to the second location so if you are inserting

At the end that's fine but if you're inserting in between that will take a lot of time and that depends upon the number of elements after the position which which you're adding what about deleting see deleting from the from the end is always welcome is because you're not affecting your array in total but what if you want to delete a particular element from between now you can't simply delete from the between right you have delete the end block but how will You move so again when you to when you want to delete this just replace

all the values right so that's that's tricky so it will take a lot of time depend upon how many elements you have after that index value now why we are talking about all this thing array was simple right we can perform the operations the important thing here is time taken for each operation and it's not about CPU time if you're thinking uh my computer is super fast it will be happening very fast There see in the world we have different computers and different computer have different CPU power different Ram Power different configuration and that's why

let's not calculate a speed of speed of a code or the algorithm by the actual runtime important is the number of steps it takes example let's say if you want to insert the element at the end that's good if you want to insert the element in between that will take lot of steps is because you want to move the elements Right now in the upcoming videos we we going to also talk about time complexity which is a very important concept something called Big Big O notation but yeah we'll talk about that in detail later I

know excited to hear that but important thing is when you write a code think about the number of steps your code takes because that defines your time complexity and if you say my algorithm is good it should be time efficient Okay so for the same Particular operation you can write two different codes example on the screen if you want to print let's say 10 numbers from 1 to 10 and maybe you just want to print the even numbers we have two options there which one is good of course you'll let me know in the comment

sections but the code which is not trating between all the values is good right so that's how you define how your algorithm is good now we can also expand the other example let's say if you have A sorted array so let's say you have an array and this is sorted by default so every time you insert the element it gets sorted by by default you don't have to mention where you want to insert this example let's say you have bunch of values here all are sorted and now you want to insert element which is 11

now if you want to insert 11 there where it will get inserted of course it will search for the location let's say we have a number nine it will get inserted After nine now the question is how do your code knows where is nine so you have to basically search you have to match is it greater than is it greater than is it greater than and then you have to insert so that will take a lot of time but what if you're inserting in between you have to shift all the elements so that's about the

array and a basic introduction of time complexity we'll discuss that in detail later in this video we'll talk about time Complexity see the thing is in the previous video we have talked about algorithms right now the thing is if you want to build an application basically we are trying to solve a problem right and every problem will have multiple Solutions so the steps which we write to solve that problem that's what we call algorithm example let's say if you want to cook something you follow some steps right now those steps are your algorithm example if

I want to record a video we Do multiple things we prepare the content we set up this camera mic and then we start recording then we edit the video so there are multiple things involved in the same way if you want to solve any problem we have to follow some steps which we call algorithms and the thing is for one particular problem we don't have one solution we have multiple Solutions and we have to pick the best one now question arise how will you choose the best one so when you say best One what exactly

it means means so let's say when I run this application I want my application to use less memory or maybe I want when I run this application I want it should take less time or maybe both and that's why we have this term called algorithm analysis so basically you have to analyze your algorithm so that you can make it more efficient right of course as a developer first focus is first the product should work and then you think about optimizing it But when you say optimizing you have to you can optimize in two ways one

think about the space comp lexity and second is the time complexity space complexity simply means can we use an algorithm which will take less memory and time complexity means it will it should take less time but there's one more problem here and the problem is how will you calculate the time or how do you specify the exact time because every machine will have a different output right so if You are testing the algorithm in your machine it might give you different time and then the moment you test the this in your office machine it will

give you a different time so that's not a best thing to calculate the number of seconds it takes but what you can do is there's a way you can calculate with the help of steps but before we go there let's focus on two algorithms here and then this will make much more sense so the algorith which we're talking about now Is the searching an element in a sorted array so in the previous video we have talked about array and then we have also talked about the sorted array so in sorted array by default all the

elements will be sorted right now what I want do is I want to search a particular element from this array now there are multiple ways of doing it let's talk about the two so basically we have an option of linear search binary search or many more but let's focus on This two so what exactly linear search and bny search is let's talk about that so what is linear search so let's say you have an array with you okay so this is your array and in this you have multiple values so let's say I'm going with

few values here let's say five values and then I'm going to write let's say 5 7 9 12 17 so we got this five values here right and then I want to search a particular element now this is sorted AR because you can see all the Elements are sorted we got 5 7 9 12 17 and I want to search a particular element let's say I want to search 12 okay I want to search this element so maybe there is a target value which I want to search in this case the target value is 12

so I want to search 12 right and then this is an array so what we do in the linear search is you go one by one so what you do is in fact we have talked about this in the previous video as well so we'll make it bit faster so What you do is whatever your target value value is you will compare that with the first element if it is matching great otherwise you will move to the next element otherwise you will move to the next element otherwise you will move to the next element and

I mean of course at this point we don't have to go to the next element so here we basically got the value and once you got the value you can return the value right now there's a problem here the problem is what if the Element is not there in the array so of course you have to reach till the end okay what could be the best way scenario here so let's say you are searching for element let's say element is five and now we know element five at the start itself so when you have the

element at the start it will take only one step but what if you have element at the end so it will take the steps depend upon the length of the array so let's say if you have five values it will take five steps When you have 10 values it will take 10 steps when you have 1 million values okay that's huge let's talk about thousand so let's say when you have 1,000 values it will take 1,000 steps that's tricky right now the problem is not it is taking 1,000 step the problem is as your size

increases it is also increasing the number of steps to search okay that's one parameter you have to remember so that's a theory right now let's understand that with the Help of a pseudo code here so you can see I'm writing a pseudo code why pseudo code why not some programing language uh syntax here is because we wanted to make it generic so that you can doesn't matter in which language you work maybe C C++ Java JavaScript python maybe cobal your choice this could IM right now this can be function procedure doesn't matter so what I'm

doing is doing here is we have a procedure right it can be a function and the name of the function Here is the linear search okay now we are accepting a list of items now this is your array the name of the array is a okay and then you are also passing a Target what you're searching so in this case we were searching for 12 but doesn't matter so you have an array with multiple values it can be one value 10 values thousand values doesn't matter and then you're also passing a Target what you want

to search now you will go inside this and then for the first thing You will do is you will want to find the length of the array because of course you should know right till when you have to search so you got a length which is stored in the n and then we are going to basically going from zero to n minus one because we when you start with zero you have to end with one less right so if you have 10 values you will go till 0 to 9 so you will go from the

first value to the last value and then you will search if the target with your searching is Equal to the current element where you are searching so when you're searching for the first element that's the first element here Target is matching if yes you're good you can simply return the value but what if you're not match it's not matching it will go for the next situation next value it is it matching yes good return what if it's not matching next value so basically you have to search each value till you're not finding it so that's

basically a Pseudo code here and what if there's no element example you have an you have have five values and you're searching for a value which is not there you can return minus one by specifying hey the value is not there this is simple linear search the code is small but then the time complexity which is the number amount of time it takes is huge okay now let's go for the second approach which is your binary search now what happens in binary search is it's very simple Basically it's not that simple but let's say so

what you do is you have a array again a sorted array and let's say we have multiple values here I'm not sure how many lines I'm going to draw so let's count it later so let's say we got five here again 6 8 9 11 13 17 okay so I maybe I love odd numbers so doesn't matter what values you have there uh so we got uh 1 2 3 4 5 6 7 so we got seven values right now what you do is in binary search now since this is sorted If you're searching for

a particular element let's say I'm searching for eight here okay and we know eight is here we know it but computer has no idea where it is so how how it is going to search now in linear search what we were doing is we were jumping basically from value to Value searching checking this checking this and then goes on so now why why this call as binary is because you divide your array into two parts that's the binary is now how you do it So basically what you do is you give a starting point and

then you give a ending point and of course every element here will have a index value so in total here we got uh seven values right which goes from 0 to six now what what you do is you first divide your array into two parts and to do that we have to find a mid value okay so even before you divide you find a midv value so how do you find a mid value so mid value is equal to the starting position plus ending position Divide by two okay now this is 6 / 2 which

is three okay so your your mid now is three and this is your mid okay now basically you check with the mid okay so you always check with the mid is the value which you searching for which is is here is it matching with the mid value which is nine no it's not matching but is it less than or greater than if the value which you're searching for is less than the value which you got as a mid value then the values after the M Mid value is of no importance right so this values here

has no importance you can directly skip them so you you can divide your array into two parts so you got the first section here which is 5 6 8 9 and then you got the second section here which is 11 13 17 so what you can do is you can basically skip this part or maybe I will just do that with a color now we can skip this part we don't need this value the value which you want to focus on is 5 6 8 9 so what you do Now is you make your mid

as the end okay because we have shifted to the left part of the array now when of of course when you shift to the right part of part of the array in case then you shift your starting value now here you got S and E again and then what you do is you again check check your ending you you will find your new new MID value so again s + e / 2 now s is 0 0 + 3 is 3 by 2 which is 1 uh of course you can say 1.5 but let's say

this is 1 equal to 1 we can Apply a float function to get the nearest integer okay so we got one here right so what you do is you check so this is your mid again you check is it matching with the value no it's not matching so8 is not matching with six then what you do then you again divide your array into two parts but then which which one you have to skip now now now we know that the mid is six so we have to jump to the next value I mean we have

to look at the right side value so 6 is Less than 8 right so I have to look at the right side so now what we're going to do is let's we have divided into two parts right so now we can skip this part and focus on the right side now so your starting position has been moved here now now this is your s and you got e so again you will find a new MID which is s + e / 2 which is 1 + 3 is 4 4 / 2 is equal 2 so

your mid now is 8 now is it matching yes okay and that's how you got the value now if you might be thinking We have done so many steps right not exactly basically at the start itself we have remov half of the array and which is very important right so let's say if you have at a size of 1,000 at the start of the first operation you have removed 500 values for the next operation when you do it you remove 250 values so the number of operation which are doing with ban search is less right

and that's how you know that this is better than the linear search of course in linear search If the value which you're searching for is the first value it's very fast right it will take a lot of time for binary search but in general binary search works faster but how do you do that so with this Theory let's talk about the Practical implementation here so let's look at the uh code here very fast because we have already done the theory here so what you do is you basically write a function let's say binary search and

then you passed a list of values Right and then you also pass a Target same thing we have done in the linear search and here then you go with the left and right so basically we have mentioned the start and the end here in this we are taking left and right left starts with zero as we mentioned the starting start with zero ending ends at the last value okay we have done that and then you run a loop till you find the value of course then what you do is you check the mid value so

this is the Mid value we have done that mid is the the starting point ending point divide by two and then you check is the midor matching with the target if yes you're done you can simply return the value otherwise we have to do something more then you check if the value which you got which is a mid value and the target if the mid value is less than the Target in this case you will focus on the right hand side side okay so basically you have to shift to right hand side so your Left

your starting point will shift and we have discussed that here right your starting point will shift and then what if the mid value is greater than the target value in that case you will shift to the right the left position okay so that's what we have doing here and then every time you do that you run the loop again you find a new MID value and that's what we have done multiple times right we found the mid value three times in the same way you're you're doing You're going to do here and then at the

end you will get a value if it is not getting if if this not there you will simply return minus one as we have done before so basically by doing this what we doing is we we have seen two algorithms right now we have to find the time complexity now what exactly time complexity is it's not about number of seconds it takes to run your code it's all about this so time complexity simply means the measure of how the running Time of an algorithm increases with the size of input data so basically let's say when

you are testing a particular algorithm you're t for let's say 10 values or 20 values but what if the values goes up what if you have thousand values how will it will affect your time will it increase the time in linear section let's say if it takes 5 seconds for 10 values will it take 10 seconds for 20 values or will it take more or will it take less okay or let's say you Have 1 million records will it take 1 million seconds that's the question we have to answer okay now how will you do

that and that's where we we have something called Big O notation now what happens in Big O notation is we use this particular concept to understand your time complexity of your algorithm if someone says hey your algorithm is not fast enough you have to first find the Big O notation of it uh so why Big O is because it is represented with the help Of O the Big O in bracket you mention the order of n or something so basically it is also called order of or Big O notation any will do so how do

you represent that you represent that with something like this so we have o off and then the value which is one will keep changing so there are multiple things here you can say we have O big O of log n we got Big O of n we got Big O of n log n we say Big O of n² which is quadratic time we got 2 to n we got n Factorial okay so we got all this notation but how do you find this okay now this is tricky so of course in this particular video

is not you will not understand everything but let's start with the basic now let's talk about the linear search now if you go back to linear search what we were doing there now in linear search when you have five values you take five steps when you have 10 values you take 10 steps you when you have 100 values you take 100 steps right But let's say that is for searching right what about reading if you want to read a particular element from the linear search or from the array it's very easy right you specify the

index value let's say the index value is z 0 1 2 3 4 and then you specify hey I want the value at index two so let's say you say nums which is the name of the array and when you say two basically what you get is nine it's very fast so it doesn't matter what is a size of your array it Can be 1 million records the time taken to get a particular element with the help of index value is constant right because computer knows where that memory is so in that case I can

say the Big O the time complexity for this is one because it is constant okay now see it's not about one step if you're thinking just because Ive mentioned that it is only one step it can be three steps as well so let's say if you reading a particular element and maybe behind the Scene it takes three steps doesn't matter it's constant right it can be one step three step 10 steps it should be constant if it is constant you can say o of one but what if you are searching element so if you have

an array size of let's say 10 it takes 10 steps now you'll be saying hey you know what if your element is at the start itself of course it will take one step but we have to go for the worst case scenario here the worst case Is what if the element is at the end what if the element is not even there it will take 10 steps and that's why we can say the order the Big O notation here will be n what is n here the number of elements in the array as it increases

the time also increases the time complexity I'm not talking about the actual seconds okay so that's your linear search now coming back to the ban search what could be the Big O notation for ban search see the thing is as the Number increases it will not directly increase the number of steps reason for that is let's say we have we have seven values how many T steps it takes let's say three steps because we have to find the mid value three times right what if the size increases to double so let's say from Seven we

got four 14 so what do you think how many steps will increase what if I say only one reason being even if you have let's say 14 values here let's say we have so many values at the Start itself it will be half right you will get seven values after one step and then you basically Inc increased one more step to find the maer so that means when your value increases it will also increase the number of steps taken but not exactly n because in the linear search if your number of values increases by 10

it will increase 10 steps here as the number of value increases it will not increase the steps in the same sequence so what we can say Is we can say it is something between constant it's not exactly constant but it is between the O of one and O of n so it is between this two and what comes between this two is O of log n now what is log n basically so log n basically means we have a base two here by default okay so number of steps it takes so what exactly this n

here so let's say we have eight values here so when you say log two of 8 it will give the value which is three okay now why it is three is Because uh log of 8 is simply means it will take two multiply itself three times to get eight okay so as the number increases let's say now instead of eight values we got 16 values it will give you four because it will take two to multiply itself four times to get 16 right uh so it will give you four that means as your number of

value increases from 8 to 16 it will only increase one step right and that's why the binary search is log n so your linear search is O of N and your binary search is O of log n so which will take less time the log of n okay and you can see the graph here as well so this is elements the number of number of elements you have in the array and this is the number of operation takes okay so number of steps so if your algorithm is following the constant time it means it's here

it doesn't matter how many values you increase it will be constant time log n is similar to it's almost same as Constant not exactly same as constant but it will take less time so you can see log n is mentioned here it's there the the wave is there you can't see it it's there uh so what if you go with Big O of n so as your value increases your time also increases is right but there can be some worse scenarios as well there can be some other algorithms which you implement which might take n

log of n which is worse than o of n there might be some algorithm which will take o of N² which is worse than the o n log n so basically if you want to build an algorithm try to make sure that you are here if you are here you're good okay if you are here it's okay if you are here try to make it better if you are here that's the worst scenario that means you're building an application which is not scalable the moment you have five users on your server your server says I'm

good the moment you have 1,000 users it will struggle okay so make sure that You when you whichever algorithm you write you follow this of course in the upcoming videos we'll work on some more algorithms we'll see which one matches there but you got the idea right so the time complexity simply means this definition the measure of how the Run of the algorithm increases with the size of the input data and to represent that we use Big O notation so I hope you got some idea in the upcoming videos we will focus more on different

algorithms and Also find the big or notation for that this video we'll talk about the Practical implementation of linear search and B search to understand the time complexity which we can represent with the help of Big O notation now basically we'll write two examples here in fact we will also do binary search into ways just to understand how thing works and then how will you find the amount of time it takes not in seconds of course but the number of steps right So we have discussed about Big O notation which is the Big O of

one big O of n Big O of login right but we also have multiple options but then at this point let's focus only on two with the help of two algorithms linear search which is Big O of N and B search which is Big O of log n okay so what I will do is I will write this code in Java and of course we'll not be doing very complex stuff in Java if you know any of the language you can follow this so I'm Using an IDE and again you can use any IDE I'm

using intell idea so in this I have a project I will simply create a file here and we'll name this file as demo so we got a file called demo. Java and this is where basically we'll also have our main method so if you're coming from different languages you know we also have main there so we have a main now let's start with the actual work imagine this as is just a template for to run the code we'll write Our code here now what we want to achieve now basically we will be having a list

of elements and we want to search a element out of it okay now the size can be anything it can be five it can be 10 it can be 20 100 doesn't matter initially we'll go for less number of values and then we'll also see how do you work with thousands of values and how do you find element and then how much steps it takes to search a particular element there so what I will Do is first of all I will create a simple array here and we'll say this array name as nums so let's

say we got an array and then I will also specify the initial values to it and since we are going for a sorted array of course when you talk about the linear search we don't have to specify a sorted array it can be applicable on any kind of array but when it comes to the binary search you need to pass a sorted element array or the least you can say so here I will Simply assign some values let's say we got five values here and then I'm I just want to keep it simple with those

values of course you can have any value doesn't matter I'm just trying to keep it simple or maybe if you want I can say 7 9 11 13 that's my love for odd numbers okay and I want to search a value so whatever value I want to search we can also specify here now we can use any variable name but we have already used Target as a variable right when we were discussing the theory so we'll say Target equal to and we'll mention the target let's say I want to search a element which is 11

okay so this is what I want to search from this particular list we can do this with multiple algorithms we can use linear search binary search or whatever you think about but let's go for linear search initially and then we'll look at the binary search now how do we do that so What we can do is we can say I want to get the result okay U I want to find this 11 in this list and give me the index number I don't want anything else just the index number where it belongs to okay so

who will give me that so what I can do is I can assign this star to someone else let's say linear search now this is another method which will give the value to us so I don't want to populate everything in this particular main main will simply say Hey you know I Got these two things I got the list I got the target value you tell me which Index this value belongs to or if you don't have this value in the list also let me know so linear search will say Okay um accepted the challenge

it will accept two things first nums and Target why you have to pass nums of course linear search will say I will search but tell me where to search and Target will say this is a value you want to search now the thing is we don't have this Method yet so what I will do is I will just use my IDE to generate okay so I will say more actions create this method and you can see we got this method I don't want this to be private I want this to be public and that's it

what you're doing is you are calling Under the method at this point since we are returning a value what we can say we can say return - one okay nothing fancy I just want this to work and that's why I'm ring minus one Okay and what if you get the result of course uh if there's no if this value is not there in the list it will return minus one otherwise we can return the index value so whatever value you get you can simply print here and you can say element found at index and then

you can specify the index value here so let me just give a space so I can specify the result here so whatever index is there okay and let's run this code just to see I just want to make sure that Everything is working let me just run this code and you can see we got the answer and also I want to move this to right hand side okay so it looks good so you can see the output says element found at index minus one that's weird it's just that we are rting minus one that's why

it's printing minus one what we should be doing is we should be checking if the result is not equal to one or not equal to minus one so this statement it should Print only when the result is not minus one in case it is minus one that means the element was not there so I can simply print element not found okay and now if on this code it will print element not found because we are not even searching right but we'll search now so how do you search it's very simple so what you can do

is you can use a simple Loop here okay nothing fancy again simple Loop and in this you're going to iterate so we have seen the Linear search right so if remember the theory we have talked about this uh so basically we'll search from the first element right so we are going to start from five and then we'll look for is it matching is it matching is it matching of course the values are different but we'll basically search for each element in the same way in linear search if you want to move you have to use

a loop so it will start from zero and will go till the nums of length so basically if you If the value number of values you have five you have to reach four okay so that's why we have saying less than and then I Plus Plus+ that's a for Loop right so in this for Loop you don't have to do much you simply have to check so whatever element you got the recent the current element which you're focusing on so in the list we have five values if you're focusing on five we'll check if five

which is our first element is it matching with the target if it is Matching with the target our job is done we can simply return the index the current index so let's say if you're searching for five and then you got five return zero your job is done that's what you're doing here okay and that's it okay it should work that's what we're expecting linear search is so simple if you run this code it says the element found at index 3 that's right so this is 0 1 2 3 and our job is done okay

uh what if you are searching for let's Say five in this case it will print at index zero and that's what we got so this is working but what if you're searching for something let's say 77 which is not there in the list if run this code it will say element not found so linear search is working right now we can do the same thing with the help of binary search now let's see how binary search works so what I will do is I will just write a code here which is public in fact I

will just copy paste the code Not a copy pasting but reusing the code I can simply copy this code and paste it here now if you're coming from java and if you're getting confused why I'm getting a starting method why not non starting methods it's because I don't want to deal with objects here okay just want to keep it simple so we got a static method and a binary search the thing is only method name will change the parameter will remain same in B search also you pass a list and you pass A Target the

algorithm will change of course it will return minus one that's not that is not something which is changing but what we will do inside this now if you go to the board here what we have done is if you have a list of values if you can see we have a list of values here now initially you have to specify the starting point and then you have to specify the ending point as well right so starting and ending you have to specify in this example we'll say left And and right okay because that's how that

makes much more sense right left and right starting point is left ending point is right and then you will find a mid every time you find a mid if it is matching that's great otherwise you have to uh basically skip the number of elements which is in the other section okay so how do we do that here so what I can simply do here is in fact I will just for my reference I will also have those values here so I will say 5 7 9 11 And 13 okay and the value let's say which

I'm searching for this time let's have the value so let's say I'm searching for 11 okay so what I will do is if when you're searching for 11 first of all you have to specify the starting point so I will say left in fact left int left is equal to now left is a starting point right which is zero then int right which is the ending point which could be four but then why to hardcode it what you can do is you can Say nums do length minus one because nums do length will give you

five you have to say minus one which will give you four so now we got the starting point ending point and then Our Journey Begins right so what are we going to do here so we'll use your y Loop here now inside this while loop what I'm going to do is I'm going to check if my left is less than equal to right we'll check if left is less than right because that's what we want right left should be on the Left hand side which is the which is smaller values and then here what we'll

do is we'll find the mid okay that's the journey we are going to start so mid is basically your starting point right which is left plus right and we want this to be in the bracket so that we can divide so left plus right divid by two okay that's how you find the mid right now once you got your mid you can basically check if the nums of mid is it matching with Target if it is matching That's great we can simply return the index which is mid of course right mid is represent representing a

index here if it is not matching then we have to change the value of left or right depend upon what you got in the mid so what we'll do is we'll say if else if now how do you check so we can check if nums of mid is less than the target so let me take this up as well yeah so if nums of mid is less than Target so let's say when you talk about this elements and Then we are searching for 11 right the mid which we got is nine if the nine is

less than the 11 we have to shift our left right so this left which was representing five will shift here now I mean not even nine we don't have to even consider nine right so what we can do is we can say left will shift to Mid + 1 okay so basically now we have two values 11 and 13 which we are going to focus in the next iteration but what if you're searching for something else which is on In this side let's say we were searching for seven in this case we have to shift

our right so right is mid minus one so basically let's say if you're searching for seven here you got a mid as 9 what you will do is you we say Okay so the value is less than the mid so we have to we have to skip this two the focus will be only on 5 and 7even that's what we have done here if you're searching for seven okay I think uh this looks cool we our job is done let's verify if things Are working out the only thing if we do is instead of searching

for a linear search this time we'll go for a binary search let's run it works you can see it says found index at three and what if you are searching for let's say 17 is not there run it says not found let's search for five and it says it works you can say index zero so that means you can use linear search or B search both works but what if you want to really see how many steps it is getting so what I will Do is let me just say this is result two which is

Ban search and let me also say Result One of course I'm not going to use both the things I'm just I just want to call both the methods okay I'm just going to use result one because if linear search is able to find it P search will also able to find it okay let's print result one here so I just want to call both the methods that's the reason I'm I'm using result two but result two we are not using it anywhere Else okay so let's do this with both the algorithms and you can see

both will print the same thing oh we are not printing the second part okay doesn't matter both will give the same result but what I'm really concerned about is the number of steps so what I'm going to do here is let's calculate the number of steps it takes so I will say for linear search steps is equal to zero initially and every time the loop iterates okay I will simply say steps number of steps Taken so steps Plus+ and then I'm going to print just so just before return I'm going to print steps taken by

linear colon and I will print steps the same thing I want to print here as well what if there's no element found so this will not never be executed right okay we have to put this into a curly brackets cool so we are printing the steps here the same thing I think we should do for bny search as well so here I will say Int steps is equal to zero and every time you iterate in this Loop you will say steps Plus+ and then basically here you will print the same statement so I will just

copy this so we'll print before returning the value but here we'll say binary and we also print this before returning just to cover all the cases okay let's see what it does run this Code and you can see for five elements linear search is searching in one okay reason being we are searching for five right I think we searching for five let's search for 11 okay in some cases linear search works well run and you can see the linear search takes four steps the binary search Takes Two Steps that's crazy run again of course you

will get the same output but what if the values are higher let's say I have more values here let me add 10 me add one 2 3 so now We have more values right I don't know how many values we have but let's say if I run this code the linear search takes eight steps B search takes three steps okay but what if you have thousand values now how do you check thousand values now that will be tricky so what I'm going to do is let's add some random values here let me create a array

of size thousand I don't want to specify my own values let's say thousand and the value which I searching for is let's say 500 okay somewhere between maybe I will say 900 let's see what happens so I have a value which is 1 to th000 I'm searching for I mean I have th000 values in the array and I'm searching for 900 but by default the value will be zero okay uh example if you search this it will say not found but look at the number of steps linear search takes thousand ban takes 10 and what

if you have more values here run linear search takes 10,000 ban takes four and look at The size example let's say if the size is eight and by default all the values on the array is zero so anyway it is sorted by default and you can see if I run this code uh which says eight for linear four for binary but the moment I double the values look at the steps taken by binary is only one extra linear all is double if I double the value again 32 so every time you double the value binary

search will take only one extra step and that's why we say it's a Bigger notation for this is log n okay so in this case the binary search works better than the linear search now the same code you can write with the help of B search as well example instead of using a loop here I can simply commment the entire section and we can replace this with a a recursive function the only thing is in recursive the the changes we will be doing is in recursive you're going to call the same function again again by

changing the values let's Say you have this big array and then you done your first search you find you found the mid now the moment you found this section let's say this part or this part whichever is matching you will remove the other half and again you will run the same B search on this list and then again you will break it down into two parts you will remove one and you will run the B search on on the other one so in B search basically if you want to make it recursive you have to

pass Two more things which is int left and okay not int left you to specify the left and right so I will say zero and nums do length minus one so basically you have to specify the start and the end and every time you call binary you will simply accept those two things you will say left and right so that you don't have to specify them here in fact you know instead of removing it maybe you want to refer this later I'll just come in this section now since this is a Recursive you don't need

a loop here right what you can do is you can check if the same step left is less than equal to right if this is a scenario what you will do is of course you have to find the mid I will just copy this code this is where you finding mid and after finding the mid you can basically also uh check the same logic this is a logic you're going to use the changes is we we going to change in the else part I mean the if else part let me uncommon the Entire section the

changes you're going to do let let's not print the steps now we know the steps right how many steps it takes but just trying to convert that into a recursive function so it will you will return mid here there's no problem with this the changes happens in the LF so in the else if instead of doing this we are going to basically call the binary search Once Again by passing the same nums and then you will change the target value now so you will pass Target Value so you have to pass nums and Target value

then you have to pass the left value now what is left so in this case we have to change the left right left will become mid + one and right will remain same right will remain right but here again we have to make the changes else part instead of this left will remain left and right becomes mid minus one so basically what you're doing is you are changing the values like this if you have this list of values you Break it down to two parts again after checking and then you're change you're again calling the

same B search with a new values okay that's what we doing here so let me remove the extra cly brackets just to make the codee look good or short basically and that's it this is your B search let's see if this works let's re restart I mean rerun and it says not found because yeah of course it's not found because we don't have That value but yeah this is a code for the uh B search with the help of recursive now there's one more thing uh you can try with different examples what you can do

is you can take a array of thousand values and add random values so in Java we have this random class you can add the values and see how much time it takes so yeah that's it from this so we understood the Big O notation for linear and B search and if you have any more questions let me know in the Comment section in this video we'll talk about the Sorting techniques now basically we have talked about the Big O notation right and now we know that if you want to judge the algorithm which you are

writing you have to make sure that you are using an algorithm which is efficient in terms of time and space as well we are focusing more on the time complexity where as your data increases it should not increase your time exponentially so we have seen different Levels of uh time complexity and we want to be into that lower Zone not on the upper zone right now when when it comes to understanding different algorithms we have to go for some inbu algorithms right or some old algorithm which normally we use so sorting so we have talked

about searching sorting is one of the way you can learn more about algorithms and how do you make it more efficient also in the real world we do use sorting a lot so let's say when you When you say you want to search something on the Internet or maybe you want you want to buy something on the Amazon you do that uh sort by Price sort by reviews right so you do that multiple times so sorting is majorly used so there are a lot of different sorting techniques available so we'll try to understand them not

everything or not every algorithm but let's try to understand few of them now if we talk about these algorithms some algorithms Are easy or simple to understand but they are not time efficient and then there are some algorithms which are good in terms of time so they are time efficient but they're not simple to understand okay uh so we have to do a tradeoff here now which is the best one that depends if you have less number of elements and if you're learning for the education purpose or to understand how sorting works then we can

talk about those algorithms like bubble sort Selection sort and then there are some algorithms which are bit difficult and they are very efficient when you have huge amount of data now what Al I'm talking about so when you talk about sorting there are different options available so we have bubble sort selection sort interance sort merge sort quick sort counting sort uh reic hip sort bucket sort and there are multiple sorting techniques the famous One are bubble sort quick sort Selection sort insertion and then M sort if I'm not repeated that multiple times so let's start

with the first one which is bubble sort now bubble sort is not efficient but it is simple to understand so that gives us a starting point when we talk about bubble sort why do we use it so let's say if you want to sort different elements so let's say we have this list in front of you the numbers are 8 6 9 2 4 5 now if you want to basically sort Them how will you do it now of course we don't have a magical way where you can find hey this is the first one

this is the second one so what you do is you basically try to use some algorithm like bubble sort to sort it in this what you do is you basically create a bubble now what exactly this bubble is take element put that into bubble and shift it to the end okay now that sounds weird right so let's let's do step by step now when you have this value let's say you have six Value in front of you you can put them in an array like this and then you have provided index values now if you

want to do this sorting on this of course we want a ascending sorting here so basically we want two at the start then four uh then five then six then 8 and then nine that's a sequence we want but how will you get it so what you do is you compare two values at a time so let's say if you put six people in front of you and you want to sort them According to their height so what you do of course you will compare two people at a time right that's how you sort and

then you will try to swap them so how it exactly it works so let's say we have these two values here eight and six and then what you do is you want to make sure that the biggest element from this particular array in the first iteration goes to the end okay so the way you do that is first you compare the first two values now these are the first two Values when you're comparing it if the first value is greater than the second value you basically need to swap okay swapping is very important here so

you have to first compare the first two values if the first value is greater than second value then you have to swap and then you basically shift your pointer to the next two values okay done we done with the six now let's go for the next two the next two is eight and N if the first value is greater than the Second value you have to swap in this case they are not they are so the first value is less than the second value so what you do is you simply say skip because there's no

swapping needed then you go for the next two values the first value is greater than second value so of course you have to swap and then again you shift your values next two values again you will compare the first value is greater than second swap then again you will compare the next two value the First value is get than second swap so basically after the first situation you got the biggest value at the end but is it sorted unfortunately not you need to do this operation one more more time actually not one more time multiple

times till you get this sorted now this also depends upon the size of your elements or array now in this case the first five values are still unsorted the last one is done so we don't have to touch the last element so in the first Iteration if you're going for six times the second iteration you can go for five times the third iteration you can go for four times so let's see how that works now after the first equation we got the nine value at the end now what you do is again you repeat the

same steps compare the first two values is it required to swap in this case no we can skip it next two values is the first value greater than second value yes swap it then again you go for this next two values is get Eight greater than four yes swap it is then again next two values 8 greater than 5 yes swap it now in this case what happened is after the two iterations you got the two biggest values which is 8 and 9 at the end now we know that those two values are sorted but

what about other values those are not sorted so let's sort them again you have to repeat the same steps so you have to say 6 2 which is 6 is greater than two again we have to swap it 6 and four greater than 6 is greater than four swap it 6 and five again swap it so now after this iteration you got three values 6 8 9 which is sorted but what about the other values they're still unsorted I mean we know they are sorted now but your algorithm has no idea if they're sorted okay

now this is tricky is because your Al them goes from start to end okay it will not check for do the other values are sorted or not so it will keep doing that so it will compare uh the first two Values not swap not needed next two values swap not needed done we have also confirm five still there's a confusion for two and four your algorithm has no idea those two are already sorted but still it will try to sort them it will compare the two values they are compared swapping not needed so by doing

that four is confirmed confed and since you only have one element now that itself is sorted and by doing this you got the entire sorted array so yes even if you It is sorted it will still check we are reducing One Step which is swapping but still you are checking and that's why bubble sort is not an efficient algorithm and the problem is the time complexity for this is O of n² because we have to use two Loops one for the iterations and the inner loop for each iteration you have to compare the values so

that's your n² not a good way of sorting the elements now think about six elements so That's good six square is not a big number it is actually but what about if you have a very big array or very big list let's say 20 values 30 values imagine the number of steps it will take so not an efficient algorithm but easy to understand now it's time to convert this into a code okay now let's try to implement the concept of bubble sort in the code so we are going to use Java as a language so

if if you want to sort of course you have to store the Valu Somewhere first so what I will do is I will create an array of integers and let me just name this as nums and then I will assign some values of course I can go for this new array and then assign the value one by one or we can give them the static values so here let's say we go with values 6A 5A 2 comma 8A 9A 4 I don't remember the sequence in the previous video which we talked about the theory but

let's go with this values and I want to sort them okay so what I will Do is even before sorting let me print all the values the way you can print the values of an array in Java is you of course you can use a normal Loop or we can use enhanced for Loop so let me just use enhanced for Loop here so I will say for in Num in nums and then we can print the values right so I'm printing num here so I will say this is before sorting and then I will I

will do the same thing I will execute the same code but after sorting here so let's say this Is after sorting okay now if I run this code of course you will get the same value two times so if I and one more thing I will not be I want to print this on the same line because Len will print on a new line I don't want it and maybe after every printing I want to give some space as well to differentiate the values and let me do that here as well so that it will

it will print on the same line with spaces right click here and say run and you can see uh we got Before sorting after sorting I think uh this should be printed on a new line so what I can do is just before this I'll say out and run okay so this is before sorting and this is after sorting at this point is not getting sorted of course right we have not written any logic here now this is where in between you have to write the logic for sorting now in bubble sort what you do

is you compare the values two Val at a time and then you swap so you compare this two Values if the first one is greater than second one just swap app and then likewise you will do for all the elements now for sure if you want to move to the iterations now we have to do two Loops here the nested Loop basically the outer loop is responsible for the number of iterations or the number of passes and the inner loop is actually responsible for swapping so what I mean by that is I need a first

variable I which start from zero and where are we Going to end it so of course I can end it at less than six so you can say six or you can say say nums do length Okay so basically we can use the added length you know the better way would be to store this value somewhere so I can say size nums do length so I'm just storing that value in a variable called size it will be easier to work with so I will simply say size and then I will say i++ so it will

go from uh start to end so this is only for passing right we have To do this multiple times you have seen that in the animations but now let's do the inner Loop which will do the actual swapping so here I will say int J is equal to Zer because we going to start from zero the real question is where are we going to end it at this point I will say size and let's see what happens if you do do with size okay so both the loop the outer loop and the inner loop are

starting from zero and ending at size the size of the array and now we Have to basically compare two values now how will you compare two values uh and how do we even swap them so it will check if the first value now how do you know the first value so nums of six or nums of zero basically six is nums of zero so nums of zero compared with nums of one that's how you compare again you can compare nums of one with nums of two then nums of two with nums of three then nums

of three with nums of four that Means the current number when you say 0 1 2 it is represented by J so I can say nums of J but this will be compared with the next value and how do I know the next value which is your nums of J + 1 as simple as that so we are comparing two values now how we are comparing them which operator we are going to use here so we are going to use greater than if the first value is greater than the second value then you have to

swap simple technique right now how do you Swap there are different ways of which you can swap the values uh I'm going to use a traditional way let me use a temp variable uh in fact you can also declare a temp variable here so I can say int you know it's better to have all the variables on top so I will say int temp equal to Z initially and then using the third variable I can simply swap them so I can say temp is equal to nums of J and then nums of J is equal

to nums of J + 1 and then nums of J + 1 is equal to time so basically what we are doing is with these three lines we are just swapping them nothing complex just swapping the two values okay and that's what we have done here so every time you find this the first value greater than the second value just swap them and you do this multiple times because we are keeping this in a loop and that's it the Sorting is done uh since it will be happening multiple times it will make Sure that you

keep the values at the end the bigger value at the end after each iteration so if you run this okay we got an error it says out of bound now there's one problem here don't you think when we are going for J + 1 what about the last value so we need to make sure that we don't go to the last value so it should end minus one right uh because when you're comparing the last two values the value for J will be here and this will be J + 1 so we have to make

Sure that your J ends before the last value that was the error and run and you can see sorting done and you got the sorted values this this is how basically you sort them again we have seen this explanation the theory how things are working out but here we just try to sort it with the help of this logic now there's one problem here uh every time you do this in the animation if you remember every after every pass we don't have to go for all the values because The last value is sorted in the

next pass two values are sorted in the next pass three values are sorted so we don't have to sort them again or even check them again so here J should be not going to size minus one in fact it should go size Min - I -1 is because after every iteration so let's say we have the first iteration where I is zero it will go till the second second last value because we are saying minus one in the second iteration where the I value will Be one it will go till the second last position or

third last position because the last value is sorted you don't have to check that again it will not affect the output but it will affect the speed because we are saving some time by not checking the same sorted value again and again okay that's how you basically you do it in fact if you want what we can also do is we can print this in every iteration so I can just copy this and after every iteration of the outer loop We can print the values and see what is happening there right so in fact I

will also print a new line here so that it will come on new line let's run this so this this is what basically is happening initially you have this value and then this is where the Sorting starts if you can see after the first iteration the biggest value 9 just went till the end then after the next for the next iteration the biggest value which is uh eight is at the end a Second biggest value third iteration we got three value sorted fourth iteration we got four value sorted fifth iteration we got four value sorted

of five value sorted and last iteration we got all the value sorted so that's how basically it does of course here too we got at the start itself we don't have to sort them again but that's algorithm works right how will you even check if the array is sorted if before you compare all the values so that's the thing about the Bubble sort where you compare the values swap them and you're done in this video we'll talk about selection sort so basically we'll talk about the theory in this and then in the next video we'll

talk about the Practical of it the thing is when you talk about sorting we have different techniques available in the previous video we have talked about bubble sort and it was working right but also the amount of time it takes basically the time complexity of the Bubble sort is n squ now that's not the main issue of course that's a main issue but then in this video we are not going to solve that quadratic uh time complexity but at least we can reduce the number of steps now in bubble sort we are going from start

to end multiple times that's not the big issue the big issue is swapping because every time in the Inner Loop we were doing this swapping multiple times and it consumes a lot of time and memory so what if we Can reduce that and that's where selection sort comes into picture now what we do in selection sort is we don't actually swap every time when you compare to values but what you do is from the entire array or at least you find the minimum or the maximum value depend upon how you want to implement it so

let's say we go we are going for the minimum value so what you do is from the entire array you find the minimum value and then you make sure that the minimum Value stays at the start now once that is done now that is your sorted part so from the entire list you create two sections the sorted section and the UN sorted section so once you find two that goes into the sorted section which is at the start and then you scan more values now let's say when you scan you find hey we have three

which is the minimum value in the unsorted areay then what you do is you pick up that three and replace it with the second location now what Happens to the value of the second location now that will be swapped where the value of three was so what you're doing here is you are swapping by selecting the minimum value So when you say selecting that's your selection sort now what it does is you're not basically swapping value inside the inner loop you are doing that in the outer loop which means the number of swapping in a

code will reduce now to understand this mode Let's look an example so let's say we Have six values here which is 65 2 8 3 7 and we want to sort them so how will you do it first of all going from all the values now of course as I mentioned before you can go for the minimum value or you can go for the maximum value so let's go for maximum value okay so ultimately you will get get the same output but the way you do do the code will be different so let's say we

are going for a maximum value now from all these values we have to find the maximum Value now of course at the start we don't have any idea which value is a maximum so let's say you make six as the maximum value because at this point we don't know right so let's assume that six is the biggest value from the from all these values and then you start comparing six with all the values so you will compare six with five if six is still bigger no issue go with the next value is six is still

bigger no issue go with the next value now at this point we Are comparing six with 8 and We Know now8 is the biggest value so now what you do is you change your variable or your you change your biggest value from six to eight and then you start comparing eight with the other remaining value which is three and seven so you compare with three eight is still the big biggest you compare it with seven seven eight is still the biggest now once you go through all the values now you know the eight is the

biggest value So what you do is you make sure that eight goes at the end now if you're doing this with for the minium value what you do is you take the value two which is a minium value and you put that at the start but since we are going for a different approach where you're finding the biggest value you will make sure that eight goes at the end now when you move eight to the end what happens to seven now seven will say okay I don't have a place so eight will say don't Worry

I will come to your place you come to my place that is swapping of the values but if you remember we are not doing it in every iteration of the inner loop we are doing that in the outer loop so once you complete one pass that's where you do the swapping so only once for the entire iteration okay now by doing this we have made sure that you have the biggest value at the end and you got a sorted at the end which is the eight and then the First five values are still unsorted so

what you do is you repeat the steps again start with six now we'll say Okay six is the biggest value let's assume that and then you start comparing six with five if it is a biggest six is still bigger no need to change the value of biggest value then you compare it with two no need to change but then when when seven comes to picture seven says hey you know I'm the big I'm bigger than you so six says okay you're the biggest Value so now the current value will be seven the biggest value is

seven now again we have to compare seven with three now seven is still the biggest so we have to make sure that after all this situation we move seven at the place of three and that's what we going to do now by doing the second iteration so we have completed the second iteration in which you got two values S and8 at the end and the first four values are same so again you do the same thing next iteration so You have to do this till the till you complete all the Sorting so you again go

with six and say Hey you know I'm the biggest now let's compare six with five so still the biggest compare with two still the biggest compared with three still the biggest now once you complete that unsorted iteration you will make sure that you move your six to the location of three because that's where the six should be so it will swap with three and then the last three values 6 7 8 are sorted the first three values are not sorted so again if You observe what we are doing is we are making sure that you

got two different sections of sorted values and unsorted values now goes for the first three Valu so three let's assume three is the biggest and then compare it with five now we know that five is the biggest of all or at least bigger than three and then you compare you you make the bigger value as five now three is gone then you compare five With two still five is biggest and now we know that five need to go at the location of two so you have to swap it now comes the first two values again

the same thing you will keep doing this till you reach to the end of your array and you move move to three and since we only have one value don't need to sort it that's already sorted and by doing this you basically got a sorted array now again compared to the bubble sort we are still going from start to end you have a Outer loop you have a inner loop but we are doing swapping only once in every big iteration or in every pass so that's the advantage of using selection sort over the bubble sort

about the overall the time complexity is still o of n² but at least it is better better than the bubble sort in terms of swapping now it's time to implement selection sort in Java so in the previous video we have talked about the bubble sort right and this is how it works now one thing to Remember in the Inner Loop and you see this Loop in this Loop we are basically doing the swapping so it increases the time as well so in selection what you do is you basically Swap this of course you do that

swapping but outside the inner loop somewhere here so it reduces the number of swap you're doing how will you do it so what I will do is I will just remove the entire code from here because this is the bubble sort I don't need this and what we have here is we have The array which is which has six elements we got a size variable where we are storing the length of an array and then we also have a temp variable for swapping then we are printing the array before sorting then and we are printing

the array after sorting okay so if you run this you will get the values before sorting after sorting but at this point they are same is because the logic of sorting is missing here so let's write the logic for selection sort here the Thing is in the theory we have said that we'll go for the maximum value the biggest value to swap or we'll put the biggest value at the end let's say in the Practical let's try to implement with the smallest value and we'll we have seen both the approach then so what we're going

to do is we'll look at the entire array and then we'll find the smallest value which is two of course you have to iterate between all the values and then once you got the Smallest value you will Swap this six with two because two should be the first value and that's how we can start and for doing that we have to use two Loops the outer loop and inner loop we'll start out loop with zero and then we'll say I less than uh size right okay so we'll say I ++ but also we can make

it more efficient by saying that size minus one is because if you remember when we were doing the sorting and once once you got all the values sorted except the First value or the last value you don't basically sort the one right so you can reduce the number of equations you go for so we can say size minus one and we'll see if that works or not and if it works then we are happy we'll also go for the inner loop now for the inner loop we'll go for J equal to now where do are

going to start J so basically if you putting the starting the biggest value or the smallest value at the start what it means is after for every Iteration the inner loop we we can skip the first value right so for the for the second iteration we can skip the first value for the third itation we can skip the first two values because they are sorted right so we have two sections right sorted array and unsorted array so here we can start with J equal to I yeah in fact uh when your I value is zero

J should start from zero so we can say Jal to I and J less than size and j++ so basically we have to end we have to go To the end okay so that's the for we have now what you do inside this so we have to find the minimum value to start with we can take take Min value variable here so I can say int Min is equal to Z in fact we want the Min index not the minan value because we have to work with the index right and we'll say the index is

by default minus one and here to start with we'll start with Min uh index equal to I and then what you do you basically check if the array which is Nums of Min index now we want this to be smallest value right so I assume that this is the smallest but what if this is not the smallest compared to the value which we are considering the value which is considering here is nums of J so example if this six is the smallest which we are thinking in fact you know we should be saying I +

1 the reason being when you are saying that six is the minimum value we are assuming that and then we are comparing with five now You will get five when you say J starts with i + 1 because in the first iteration the value of I will be zero and this five is one right so we'll compare these two values okay if six is smaller than five then everything works but what if six is greater than five in that case we have to swap now okay we don't have to swap we basically have to change

the minan index to J because the new index you will get is J so the new index here is one okay uh so that's the Main main index so what we doing by doing this is after the entire iteration you will get the minimum value from this array okay so that means after this situation you will you will know that two is the minimum value now once you know the minimum value what you do is you swap two with six is that simple how do you swap two and six how do you know we have

to swap six because I is referring to six and the mid index is referring to two so we can simply swap Them so we can use a temp variable here and we can put nums of uh Min index and we can say nums of Min index is equal to nums of I and terms of I is equal to 10 so basically we just have to swap them so what we are doing is in the Inner Loop we are just finding the minimum value and then once you find it you simply swap it with the Min

value which you're considering which is the first value and as the I value goes up first you will compare with this then you Compare with the five and you compare then you make two as a minimum after of course of after the swiping and I what what I will do is I will also print this values after each itation so I can just copy this and paste it here and we also print a new line to get it on the new line so now if you run this let's see what happens so you can see

if this is okay uh I will after printing this also I will just say new line or maybe I will just skip this new Line before the for Lo printing okay let's run and you can see this is before swapping and then once and this is after swapping so let's compare the value is it properly sorted uh yes 2 4 5 6 8 9 those are the values we have and then see the steps in the first iteration before swapping uh so this is the first iteration what you do is you know that two is

a minimum value so you swap six with two and that's done then in the second iteration you find the minimum Value so the minimum value from this is four so you swap four with five and that is done here then you consider six then you say you find the minimum value from this which is five you will swap five with six so in this you'll say uh six is the minimum so you will swap it with eight comparing this two this is 8 and N so you'll swap eight with nine and in last value you

don't have to even sort it because it's always sorted and that's what we are doing here and that's why we Say it's size minus one we don't even sort here in fact if you don't put this minus one what will happen is if you run this code you will get one more iteration and there's no change there it doesn't matter how many values you have you're not going to have any change in the large itation so you simply save it by saying minus one here so that's how we use selection sort basically find the minimum

value and swipe it with the location where it should be so we have Talked about different sorting techniques we have talked about bubble sort and selection sort in this video we'll talk about insertion sort so what you do in this technique is basically you take the elements and then you put the elements at the right position that is your insertion so you have to put at the right location now in this you don't normally do swapping yes we do swapping but we don't use word swapping what you use is something called shifting okay so Example

if you are playing uh if you playing cards so if you if you have a random cards on your table so basically in this example we to not going to use cards we are going to use this uh characters I I found these characters in my uh in my drawer I think I got it for my kids's birthday but it doesn't matter so I got this and we'll try to sort this values here so so let's say if you randomly get these values and if you want to sort them uh what you do is you

Pick up the value and then you you know imagine these are cards playing cards so what you do is you take the first value you take the second value and then you keep it like this I don't know if how many of you play cards I used to love them not for money uh but I us should love them then you take a next card and then you put it before this then you take a card then you know that this card goes between a and o you put it here so this is called insertion

but how exactly You're going to do that that will say within example on this table and with this with this cards so now let's sort this values now these are not values but characters so let's try so what we have here is we'll start with the first location as you can see on the screen we have different values here and I'll pull this down a bit so that we can have some place to keep this so the first value is O now I'm assuming the the O goes here the first location because it's always Sorted

and then you take the next value which is is e let's say now we know that e comes before o so what we need to do is this need to go at the start so you have to move this to the next location so that you will have some space for e now the point to remember here is it's all about shifting okay so we don't use a word swapping here you'll understand that in sometime why don't we say swapping uh let's go for the next one which is s now we know that s is

greater Than so we'll compare s with all the values so we compare s with e okay it goes after that it goes after o so s goes here okay I'm not promoting any camera model here but that's the sequence then you go for the next one which is D now d goes at the start so what you do is you basically have to move all the elements right so if you compare with s here D is uh less than S so you compare so you have to shift s you have to make some space for

d then You take o and you move o here so that you can make some space for D then you compare D with E and you have to make some space of course you have to swap you have to move this you will make some space for D and D goes here right so now it is in sequence then what about the last value which is a now a we all know we have to I mean of course it goes at the start but we have to compare from start or last so this goes here

which is s if it is less than that will shift This this to make space for a but then we have to also check with o this also have to shift we check with e this also have to check shift we compare with d this also has to shift and then a goes at the start by doing this what you're doing is you're basically inserting value at their location so this is how you do the insertion sort now let's say this was randomly we were picking values right but what if you have things already in

the array so what we'll do is We'll keep it here we'll keep this here we'll keep this here this goes here and let's say this goes here in fact I will also move this okay I'm not trying to make any city name but let's say we have this sequence we have this five values and now you want to sort them so what you do is you don't start from the first value you start with the second value and then because we assuming that the first value Is already sorted okay so what you do in this

technique is basically you divide your list or array into two segments the sorted and unsorted at this point all are unsorted Al so this is unsorted array but when you start you have to assume that your s is already sorted then you start with E then you see hey do do we have e at the right position the way you do that is you compare e with s and this and you say Hey you know e is not at the right position so you Will take e out uh in programming you what you do is

you save the value of e in the temporary location okay so exactly you're not moving e you're just making a copy of it maybe there will be a copy of e here as well but you have extra copy with you saved in a temporary variable so let's say this is the temporary space then you move your s here so that you can make space for e and that's sorted now now if you see this two it looks sorted now what you do Is you check E before do we have any value so of course we

don't have any value before E now that is sorted then you go for the next value so we started here in the next you basically start with o now o will compare with the previous value which is s now is it to the right position no so we have to copy o in the temporary variable and move your s so that you can make some space for o and O of course you can move o here you have to also Check if o really goes here you have to compare o with the previous value which

is e and we know that o is greater than e so you can keep o here so that's how you basically sorted the third element then you go for the next element which is D so what you do is you compare D with s here and then you know that D is smaller than S or S is greater than D so what you do is you have to move so you take into temporary variable move s here of course you don't move D directly There you have to compare D with the other other elements which

is O is it smaller than that yes we have to move this here we have to make space for d right again the before that also we have one more element which is e so you move e here it's all about shift shifting values and then your D goes here and if you compare uh it it looks sorted right compared to the other other values so it looks sorted but then we have to complete one more iteration so you take A you compare a with s now a here is compared with s so again we

have to shift so what you do is you take a in the temporary location then you move your s you will check a with o again you have to move O then you check a with e again you have to move e so remember you have to only move when you know that a will not be at the right position and then you compare a with d again D has to move so that you can make some space with for A so this is how basically you do this sorting technique now question arise how will

you do in programming so what you need is you need two Loops one for the number of passes you are doing right moving from different element and you need a inner loop which will responsible to find the key and uh shift the values and also you need a temporary variable so that you can store it somewhere so you have to you need a key which will go into a temporary variable on something Now how do we do this that Implement in the code so let's try to implement insertion sort using Java now basically even before

we Implement that before we write the code let's write the algorithm on the board and then we'll try to convert that into code so what we'll do is first of all let's create some let's get some values okay so we also need a array so let's say I will name this as array itself AR R and then it will have some values so let's let me create a Array here and we'll take few values let's say we got five values of course you can go for more values here and then let me just say these

values are three 6 2 1 5 okay so we got this five values now I want some variables as well so as I mentioned before we don't swap here right we do shifting of the values so of course to achieve that we need Inner Loop and the out outer loop so let's say we got the outer loop which will will go for for Loop so let's say we have a for Loop here and then we have to take a variable which is I for the outer loop counter and then inside this we are going to

have a while loop which will have let's say some condition of course you can also go for four and four but then when you talk about insertion using Y Loop inside makes much more sense because we want to B we want to run this based on the condition not on the number of equations okay so this is your outer loop let let's finish it here this is Your inner loop let's finish it here and let's write the code there now we need two variables as I mentioned of course in the wild Loop we are not

going to create a variable we are going to use one variable but let's also go for J so we need a i variable let me just write I here we need a j variable and we need a key as well so that you can store this value somewhere so at one point you will compare and you will save it now from where we are going to start this now if You want to understand what what you're going to do is it's very simple so initially you will take your six as a key so when you

write this variable we'll say key is initially six okay now how you're going to get six so let's say we take a variable I here and then we'll keep the J here okay so we're not going to start I from the first one we're going to start I from the second one and then J will be the first value now I will represent the outer loop and J will Change in the inner loop as well okay so that's why we are going for I and J we could have gone for different variable name but we

got used to I and J for the Outer Loop and inner loop okay so now uh what you're going to do so the idea is very simple once you got a key which is six in this case now how you got six maybe we can do something like this we'll say a r r of I whatever I represents we'll save that in the variable K or key and then we're going To start J by saying J is equal to IUS 1 so I is starting from 1 so J is i - 1 that means the

value for J initially will be zero and I is 1 now what you're going to do with this it's very simple you will simply compare the value of J which is this the first value so you'll compare J with the key if this value is greater than the key then you will do the shifting part at this point we don't need that right because the value of J Where the J represents is less than the key then you don't have to do any shifting part so this is already sorted okay but let's go for the

next situation now when you say next situation it's very simple what you simply do is so you shift your value of I here and you shift your value of J here because we know that the three and six if you compare this two they are sorted let's go for the next one now in this what you will do is you will check again you will Change certain things right if you can see this will change because now a r r of I is not six a r r of I is basically two okay so key

is two now what about the value of I even I is changed I is now two so index is two so let me also write index so that it will make much more sense right so that those are the index value so I value is two now what about J so J is I minus one so J will start from one that's done and now you will apply a condition so what basically Condition we are checking for so of course if you write the code here so I is initially starting with one we're not starting

with zero and then we'll go till I less than n if the Val if the length of this array is n and then we'll say I ++ okay and then we'll assign the value okay we let's not write the actual code let's write some dummy code so let's say we got a key variable the value for key is basically a r r which is the array of I and that's what we are Doing here that's one thing next we also need J variable so we'll say J is equal to I minus one okay that's how

we going to start now what you're going to compare in the while loop so in the while loop it's very simple you will check for the a r r so a r r of J let me just say complete this here here so this if this is greater than the key because the shifting part will come only when whatever is represented by J is greater than the key so if you can see the key Is two here and in this case yes it is greater so six is greater than two so what you do is

you basically perform some operation now what operation I'm going to perform so basically first of all I will take this key somewhere of course we are stowing that key two in the key variable and then you do the shifting shifting of what so you will first compare this two with six and and now we know that we have to shift six so you will shift six here then that's one Done right can you put two here we can actually we can put two here but the problem is we also know that we have to compare

two with the previous value which is three in this case so you will not shift two there but will shift three here but then to shift three here what we have to also do is we have to first shift our J here on the first location that means we are also going to perform J minus minus right so what I'm saying is the first option you're going to Perform is Shifting the values right so how do you shift you simply take the next value so initially J was here right so this value six is going

here so that means what we can do is we can say a r r of J + 1 which is in this case two is a r r of J by doing this what you're doing is you're shifting so the J initially was here which is one so index of J was one or the value of J was 1 then you're saying J of two I mean J becomes two then what we saying is we are saying J J + 1 which is 2 so the value of six which was here will move here that's

what we are doing on this line that's a shifting part and then you will say jusus so you can say jusus or you can say J minus one even both works so this is the entire logic you have right but this Loop will repeat right now when it will repeat look at the condition here the condition is whatever J so we are shifting J backwards right J is now here so we'll check if a r out of J is greater than Key in this case yes you can see the key is to a rror of

J is three so it is greater so we will shift so how do you shift basically you do the same operation which is there inside the while loop so if you compare this operation this is what it is doing the shifting part right and then we know that of course if you can see here we have one more step you will do J minus one which means your J basically moves one here because when you reduce the Value of J it become it became zero right and then again you're doing it so it will become

J J becomes minus one so we have to stop it here when the J becomes less than zero we have to stop but don't you think we have to also add that condition in the while loop so we'll do that we'll say and J should be greater than equal to zero okay this is one condition we have to add if this is false if J is not less than or equal to zero then you will do the last last step The last step is very simple you move your two here and the way you can

do that is by saying a r r of J + 1 because J became minus one we don't one minus one we want zero is equal to K is equal to key so basically this is where the value goes first now by doing this we were able to sort the first three values now what next of of course you will increment the value of I so when you say increment that means the value of the I variable goes here and again for the Next iteration J goes I minus one right because of this basically for

the outer loop the I value is incrementing but the J value is just before I and again you you do the same things what are the same things you first check if the key okay we have to update the key as well now how do you update the key now the key value is a of I which is in this case should be one so the new key is one and j i is what I is three and J is two okay new key value is one you will compare if The a r r of

J this is the condition we're checking now if a r of J which is in this case is six is greater than the key in this case yes you perform this operation what is the operation it's very simple let's keep this value somewhere you start shifting six here six goes there and then you J comes back J comes here right because of this step here right and then you you again check if a out of J is greater than key yes three is greater than one again you will Shift three here then you shift J

here then again you shift two here then you shift J here and then now J becomes minus one Let's Stop the Loop and shift one here you can do the same thing for five let's do that quickly so what you will do is you will shift the value of I here which means certain things are going to change change now this I becomes 4 uh this J becomes three the key value now is five right again you do the same things uh you keep your J here Because J is just I minus one then you

compare if the a r r of J which is six in this case is greater than the key yes let's do the shifting now how do we do that let's move that here and then we have to shift six here J goes here now again you check is the a AR of J is greater than key no it's not there so you will just simply come out of the loop and then you will keep five here and if you can see it's all sorted so this is the logic let's implement this Logic in the code

now so you have the logic in your in front of you what you will do is you you got the same values in fact we can go with the values which we have so let's say okay I now I just re return the values let's go for this values and let's see if this works instead of array we are going for nums that perfectly works I don't want a Time variable so we can remove this portion here this is basically the older code which we had for selection sort if I'm Not wrong and this is

the before sorting elements this logic is going to change for sure okay so let's try the logic it's very simple you create a array so let's say this array is a RR is equal to let's have some default values to it let's say 5 6 2 3 1 this time we're going for only five values and this is an array okay what next now basically as we have WR in the board let's take a for Loop now the for Loop is going to start with i i is equal to 1 and we can do That

quickly now it will finish at n but we don't know what n is so we can say add. length and we can say i++ right that's one done and now okay let me just remove some space in between okay now what are the extra variables we need basically we need two variables right we need key the value for key will be a r r of I which we have done earlier and then we also need J and we know J is J minus know this this is what happens when you know the algorithm on the

on the board Right I have a I have a board with me so okay those are the things we need okay not J minus one it should be IUS one and then you do a while loop because this is where you do the iteration we have to make sure that J is greater than zero that's one thing and we need to also check if a r r of J is greater than key in that case you will execute the while loop so you will do certain things here now what you are going to do inside

this while loop so basically you have to do The shifting right if it goes inside you will say a r of J + 1 is equal to a r r of J right and also you have to reduce the value of J so you will say J we can even say J minus minus syntatic that works and for the outer loop you will assign the value for key for that particular empty location and the empty location is defined by J itself so J + 1 is equal to key and I think we are done so

so the code is so short uh let me check if that works what I will do is I will just print the values here so I will take a for Loop and I will say int num from array and let's print the values let's print num I don't want the new line I would just want a space here and let's see if that works right click run and boom you can see we got the output and the values are sorted it doesn't matter what type of values you add here let's say 8 four and run

you can see this is sorted yeah so that's your insertion sort in This video let's talk about another sorting algorithm which is called a quick sort the thing is when you talk about sorting algorithms the idea here is to explore different algorithm and we'll see how efficient it is now when we talked about the other algorithms which we talked about till now bubble s selection sort they have a big or notation of n Square which we don't want right we want to make it faster or efficient now in that case we have to Explore some

other algorithms and one of them is quick sort now in the best case the quick sort goes for n log n which is much better compared to the n n squ but in the worst case also it goes for n Square so in the worst case yes it is almost there but uh on average it is n log n or you can see the best case so at least we are happy in the best case and in the average case now let's see what is quick sort so actually it uses multiple things so let's talk

about About that first the first thing is divide and conquer so basically till this point when we talked about bubble sort or selection sort we were doing the algorithm on the entire collection so let's say if you have a a list of values which is six values so what you do is you perform the operation of bubble s and all the Sorting techniques which we have done before applied on the entire list but what quick sort says let's do divide and conquer which simply means Divide your problem into multiple things and solve the problem of

sub problems individually so what you're doing is you're dividing it you're solving it and at the end you will combine it so that's your divide and conquer so in this case if you have six values let's divide the values into multiple sub problems and then sort it and then combine it so that is your divide and conquer next it it uses something called a recursion of course you can also use recursion in the Other other algorithms but here it works with recursion now basically what is equion so when you call the same function by itself

so example let's say the function name or the method name is show and if you're calling show inside show that's your recursion right and next we have to understand the concept of pivot now basically pivot is something called a central point of a problem okay so let's say you have this entire list here or the array now you Have to find a pivot and then based on that you will perform the operation of course it will make much more sense when we start but remember we have to work with the pivot so those are the

things you have to remember divide conquer recursion and pivot there's one more thing which is the tree now basically when you say you are dividing your entire list into subsections or sub problems what you're doing is you are creating a tree structure okay so once We start with the diagrams it will make it will make much more sense but these are the things we have to remember so let's see how your quick sort works and then we'll try to convert that into algorithm and then we'll see how to write a code for it now B

the basic idea here is let's say you have a list of values so we are discussing about quick sort uh so let's say we have a list of values so let's go for six values here and I will say this is 5 this is 3 6 1 4 And 2 so let's say we have the six values I'm not sure will it really make sense to use this example but let's get started now with this six values what you normally do is you do divide and conquer here so the basic idea is break the entire

list into sub problems okay something like this maybe can we can create uh two two different arrays here we'll be having three uh I mean 5 3 six here you can have 1 4 2 and then you can again divide this maybe you can have one And four here and divide this into two here also we can have five and then we can have another array which is three and six so we got these two arrays from the big array and then you create the shorter format of it so at the end what you're doing

is you're creating the small chunks now this is what your tree structure is so we have divide we talked about divide so we are dividing it we'll sort the array and then we'll combine it and then since we are performing this Sorting on each section in sub problem that is your recursion but is it the real thing no so basically we talked about the idea but how do you divide the array randomly I just divided the array but that's not the main idea but we have to divide but not this way so how we are

going to divide this that's the question let's remove this and let's go with the values here the idea is you want to divide for sure you will divide this into two parts but you need to find a Point from where you will divide this and that point is basically your pivot now how do you find a pivot now basically uh the reason we get this parti or pivot to do the partitions of the array right now should we pick up one now that depends so even before you divide you have to do one more thing

so I'm saying pivot but then that pivot should be a point which is at the right position let me repeat the pivot is a point in this array which is at the Right location now if you see this after this sorting what the values you will get so you will get values like let's say I will just write it in shorter format now so you will get 1 2 3 4 5 6 this is the output I want okay just went for the sequence of numbers here but this is the output so this is the

output which we want from this input which which we have the bigger array here or the big size which I mentioned okay so if you talk about the value one Here so one should be at the first position two should be at the second position three on the third position fourth fourth position fifth fifth and sixth right so they should be at that position now since we have taken those values and that's why it might be confusing but you got the point right doesn't matter what your values you have it should be in the ascending

order so the first value the smallest value should be first and then least goes on Okay now we have to make sure that at least you you find one point from here or one value which is at the right position example if I say uh let let me take four now four is it at the right position the answer is no four should be here right so instead of one it should be four then we can say four is at the right position now if you want to understand this with an example so let's say

you in a classroom and then you have multiple students there okay and then You want to sort them based on their height there's one way as a trainer I can be there and I can say okay you go there you go there and that's what we have done in the bubble sort right I was controlling it but what if student can sort themsel so they can compare each other and they say okay I should be here or I should be here and they they will move now one way is one person can sort them but

then we don't want it so what we want is what if the students Themselves can get into the right position that that will solve the problem right okay but how we are going to do here how they will reach to a right position now what you do is initially we don't know the position right so you can take any value normally we can uh we can find the pivot so for the first iteration we what we are trying to do is we want to make sure at least one value is at the right position so

that we can divide the array now Which value should we take technically if you take the average value or if you take the middle value example if you if you go from 1 to six the mid value is three or four right so if I can take three as my Pivot it will be much easier for me to divide the array so what will happen is if I take three as my Pivot then three should be coming here right so three this is the right position for three right but it's not if you start with

the area this is not at the right Position but if you get to the right position we can divide into two parts right okay so that's the main idea how will you get that there so normally what you do is if you can find a good pivot and that's very difficult to find because how do you know the mid value since we know the values here I can find the mid value but as a program or as a software they don't they don't have any idea what are those values are so what we do is

we randomly pick the pivot Maybe you can pick up the pivot let's say one in between somewhere anywhere if you want so you can pick up this one you can pick up this six or you can pick up the first value or you can pick up the last value or what you can do is you can you can just add all these values and divide by six whatever value you will get so try to find the average of it that's what we we can do but again that's a lengthy process normally which I have seen

is they go for the big the Last value not the biggest value last value because we don't have any idea what's the biggest value is so we will go for the last value okay so this is this becomes your pivot that means we need multiple variables here now what varable we need so I will just write variables here so the first variable we need is a pivot variable so we'll say Pi okay and then uh you need few more variables you need a variable I for the positioning again we'll discuss what This positioning is uh

then we'll need J which will track which will go through each element and we have done that in the Sorting right so when when you jump from each value that will be done by J and then of course we also need array here so let's say this is a r r this is your array okay and let's have the index value so we say this is zero 1 2 3 4 5 those are the index values we have apart from this we also need a low and a high variable okay so we'll say l and

H so Let's say this is L and this is H now normally we can say h is the last value or we can say it's a length minus one so we can say that so we have a low and we have a high so low starts from the first and H is the last value now how do you perform the operation it's very simple first you find the pivit now we know that we we are going for pivot which is two in this case so what you will do is let's take this two as the

pivot so I will say this is p so this is Referencing this is uh referring this to so Pi variable at this point is referring to so I will say this is two in this case and then we need two variables so let's take variable I now by default the value for I will be the lowest value minus one so let's say the I value is here at this point you know what I will do let me just remove this portion at this point because let's keep this slate clean so we need a i variable

and then we need a j variable so J will Be here to start with so I will be here at the minus one position J will be here at the zeroth position and then what you do is you basically run a loop where of course the I will also increment but the main Loop here we want is for J okay uh so we'll take a for Loop for J okay so let me write the code here so what we want is of course the rough code so I will say for J will be starting with

low okay that's what we are doing here and then J should go till n but then we are Not using n variable right we are using variable high so let's say J less than high and j++ now what you are going to do in this inside this Loop so basically you will first make sure that you get the PT value right so you will I mean of course you have a PT value here which is two and then you also got I I is still minus one now inside this Loop what you will do is

you will check if the a r r which is in this case we have an array if a r of J if it is less than the pivot So pivit we have a variable here if it is less than pivot you will perform some operation now if you compare the values here do you think uh the a r r of J which is five in this case uh is it less than the pivot because pivot value is two no it is not less than pivot so we'll not do anything but we have to find the

value Which is less than two right so if the value of five is less than two you will perform some operation since it is is not true we are not going To perform any operation here so basically you're going to shift your J here okay now how while we are doing it of course we are running a loop right so J starts with low and then we have to increment so J goes there it will compare itself with the pivot is it small no so again you will shift your J then you compare 6 with

two then is it smaller no then you shift your J here then you check is it smaller yes what if it is smaller then what you will do in This case if it is smaller you perform some operation first thing you do is you increment the value of I basically what you're doing is you are shifting your I here okay that's done next we have to make sure that you swap the value of I and J okay so whatever value you have with I and J you basically swap them so what I'm saying is take

this value here move this value five here and move this one here okay now how do we do that of course we have used it before so we can Use a temp variable or maybe at this point I will simply say Swap and then we'll write the logic later so I want to swap basically the value of a r r of I with a r r of J okay so we need to do the swapping that's it this are the thing we are doing inside the if condition now once that is done of course you

have to move your J again because we are in a loop so J will go here now again you will compare if the four is less than two no and that's it J will move here because if it is not less then we not doing any operation then your J goes to the last value because your J ends at high right so J reaches here and of course the pi and J is same then you don't you don't have to I mean of course it is false the condition this condition will be false which is

a r r of J is not less than PT so in this case it will not swap but what happens after that even if you complete the entire Loop do you think Two is at the right position no two should be here right so this three need to go there so what you do is you perform one more operation after the loop so after the loop you what you will do is you will basically swap the a RR of I + 1 with the a RR of I okay now this is the operation you have

to perform now what will be happening here so what is the value of I value of I is z which is index you're picking the next value which is three so you have to swap This three with this two because that's what your ARR of high is so you will move here and you will move this side now by doing this we made sure that the pivot value which you choosed is at the right position can you confirm is it the right position yes it's at right position now what you do is you divide I

mean if you if you observe the array if you look at the pi which is p here now if you see the left hand side of it this is always lower than two and this value Is always greater than the two so yes two is the right position now what's the next step the next step is very simple you divide this array based on the pivot value so what you do is you create another array here and in this you'll be having only one value which is coming from here right in fact we can also

draw an arrow there so this is coming here two will remain there itself we can write two here we don't have to work with two because it's already sorted and Then you take this particular section into another array not another array but let's say logical partition we are doing here so we'll get another array here so we are doing divide and conquer so here you're going to have 6 5 4 3 If You observe they're not sorted but at least we got the partition right now what you do is you again perform the same operation

which we have done here in the first example now you help me should we start with this yes we can start but Don't you think we only have one value and whenever you have one value it is always sorted let's work with this so what you do is you again take the same thing so you take the low you take the high and then you of course you again have this P all these values here so all these variables are still exit because you are going to apply quick sort again on this particular values so

let's get started let's take P which P we are choosing of course we are choosing Always the last value so this is your Pi pivot then you got I here you got J here then what you do is you start running your algorithm which is first you compare the value of J which is six in this case is six smaller than three look at the algorithm which we have done is six smaller than the payit the answer is no so you will simply so you will simply move your J here again check is it uh

small no shift is it small no is it then again goes Here is it small no then what you do is you have not you have not done any spping but at the end we got one more logic right so once you complete this for Loop you will do something with this which is swapping the I + 1 so I is at minus one so you have to basically swap the six with the array of high which is three so this goes here and this goes here now if you look at the pivot this is

sorted right so now what you do is You write three here which is your PT value and then you divide your array into two parts but since the pivit was the first value what you will do is you will get the new array now from this which is is 5 4 6 and then you start performing operation here now what operation the same operation which we have done again you will apply quick sort so this is L this is H so Pi is referring six here and then you start so you got I here you

Got J then you start comparing is the first value the value of J is it smaller than the PT yes now when you say yes what you will simply do is you will increment the value of I first if you look at the code that's that's what what the logic we have and then you swap the value of I and J now in this case I and J are deferring to the same value so swapping doesn't make sense of course they will get the same value then you increment the value of J J goes here

Check is 4 less than 6 yes in that case you will move I here and then you will swap the value of I and J again it remains same so nothing to do here then you shift your J here of course the aray of J is not less than p because they the same value then this Loops end the for Loop ends then you perform this operation which is a r r which is + one this will be replaced by high and that remains same right so there's no swapping I know it it all depend

upon The value type of values you're getting so at this point there's no swapping happened so this remain as it is six but then you will get a new array here which only has five and four and then you start applying the same operation let's get started in fact I will just write this bit up so that I will have some space and this is coming from this particular section then what you do is you will take the same value you say and if You observe we doing recursion right The same steps we are repeating

multiple times so LH we got Pi here we got the variable I referring to minus one position or in fact notus one position it is one less than the low so in this case the low is this position right now what is this position this is in fact we should have maintained the index value right right so this is zero this is 1 this is 2 3 4 5 then we got three here which is this one this is 3 4 5 what we got here is 3 4 so these are the index Values for

them okay so we got I referring to the index value two and J is here then what you do is you simply compare the same steps we have which we have done so the array of J is it less than four no so all this operation this spping is not needed you will simply move your J here again do we need to swap of course not because the array of J is not less than pivot so it will remain same but then you will perform the last operation which is this one What it says it

says Swap this value with the high value so this will be swapped so five goes here this goes here and this goes here now if You observe we divided and we conquered so if you merge this in fact we're not merging physically we are merging logically right because nowh we were breaking the array but if you see if you try to merge logically what you will get so you will get this one first which is one goes here then two goes here then by sequence Three goes here then by sequence this 45 goes here and

then this six goes at the end so if I want to write this this will go here so let me write one then this goes here that's two then three goes here that's three then if you can see in the binary tree we always goes from the left to right so if you see the left because six is there on the right hand side you will say four and five and at the end you will get six now this is sorted so after all this explanation This is how basically you sort them now this logic

which we have written here is actually a part of a partition method so this is a partition method so the entire thing goes there but we also need to return the pivot value right so which is the privot value so we return I + 1 because that's what the pivot is but this particular function will be called by home so we have a concept of quick sort here so quick sort is going to call this Partition how that we're going to see in the code itself so you got the idea basically you divide sort each

values and you will get the output now this will make much more sense once you start coding and I hope it will get clear so let's try to implement the quick sort logic so what we going to do here is we got this values here so this is the logic for the insertion so what I will do is I will just remove the entire part here we got this array and we are going To perform the operation now of course you can write the entire logic here but then remember quick sort goes for recursion So

when you say recursion you have to create a function or a method which will get called so what I will do is I will create a function here and let's call them so we'll say a quick sort as a function name or the method name which will take three parameters now what are the three parameters the first one is the array itself on which You want to perform the operation next next is the starting point and the ending point of each section example you start it will be the entire array but remember when we have

to break it down so that is your each section okay so we have to specify the low and then you have to specify the high now in this case what is low so low is zero and the high is basically the array do length minus one right that's the value you have to send now basically we don't have This function so we can just right click here and say okay I want the IDE to create this method for me may just using some inbu methods okay let's create our own so what I will do here

is I will create a method called public I don't want to get the object I will say static void quick sort and it will take these three values so first it will take a int array in fact one of the syntax of array you can write it on this side because it will make much more sense you got array And then you got int low then you got int high so these are the variables you need and then you can start performing the operation so basically from the main you're calling quicksort only once but quicksort

will be calling itself okay but based on what now basically I want quicksort to call itself only till when your low is less than high we don't want it right so that's what it makes sense right low should be low high should be high and if it is true then keep calling The quick sort so I will I will keep calling the quick sort but the question is what values I have to pass now think about this if you have one big AR and then you are saying that we'll be breaking this into two parts

so don't you think you have to call quick sort two times times for two different arrays that's right so I have to call two times but the question is what are the values for sure the first variable will be array because that's what we are sending Right we have to sort the array the question is what will be the low what will be the high because when you divide your array into two parts what should be the starting point of the second array and the ending point of the second array that's what you have to

mention but how will you know the starting point it is easy actually here the starting is always low for the first array and the ending is always high for the second array okay even that is solved the Problem is with the ending of the first array and the starting of the second array that's what we need to find now how do you find this for this we have to run a partition okay so this is the logic which we have to refer to so what I will do is I will just reduce the ID size

so that I can see those values I mean this logic so this is what we have to implement in the partition so basically to get this value the pivot value what you will do is you will say Int pi equal to and you will create a method called Partition in which you will pass three values the same three values array low and high so basically in the logic I have not mentioned it but we want this value as well okay so we need to create this method so what I will do is I will just

go back here more actions create a method okay so we got the method let's perform operation on this method we can make it private because we're not going to use partition Outside this class so private works but what should be the logic here and we have to return something remember we have to return the pi value okay so we can write the same logic which we have WR here and once you get this Pi you can basically pass pass the pi and we don't want to include the pi so we can say Pi minus one

and here we have to pass Pi + 1 because every partition when you create you don't consider the PI right Pi stays there you create two parts and Then those are your two partitions but we have to find this Pi that's the main task and for that we have to write this logic which is mentioned here so we need some variables the first one is temporary pivot variable and we have to assume pivot for the first time so the pivot here is always high so that's the algorithm we are using but we can pick up

the starting value or randomly any pick any value that works so let's say we got pivot high and then we also need One more variable which is I remember we have to use this I which will return so I is basically your low minus one remember if the if the array starts with zero the I will be at minus one next we need a loop so we can get the entire loop from here or maybe we can type so we can say for INT J is equal to Z in not zero right it should be

always low because when you create different partitions not every partition will start with zero but they will start with Low so J less than equal to high and j++ I'm just referring to my algorithm which I mentioned here and then the logic we have to write is if a r r of J if it is less than pivot then you start doing some operation what operation first you increment the value of I and then you swap but how will you swap we don't have a swap function actually we can create one but instead of that

what we can also do is we can write the logic so I can say int temp is equal to a r r of I then A r r of I will be replaced by a r r of J and then a r r of J will be replaced by the temp okay that's the values you have to swap and that's it this will run and you will do the partitioning part but once you complete the for loop again we have to swap the value of I Plus one with high so you can actually use the

same logic here or same statements so I'm not copy pasting I'm just reusing the code sounds better right so here we can say this will be replaced by I + 1 And I +1 will replaced by high and this high is going to replace by temp spping done and at the end we need to return I + 1 because that's what is referring to the pivot okay uh looks like a right logic we just conver that into here so by doing the partition we are saying replace one in fact once you get this algorithm also

try the same thing which I've done on the board okay then it will make much more sense okay I hope this will work what do you think let's run And let's see run and yes looks like sorted 1 2 3 4 5 6 8 let's change some values let's say this is 81 this is 62 and this is 11 one 1 let's try with this values and let's see if they sorted so 2 3 4 5 62 81 1111 so it works so those this is your quick sort now why we are saying this is

n log of n is because we only have one Loop here which is for Loop plus we are doing the partitions of it right so they can run parall yeah so This is n log n but in the worst case it can go for n squ but better than the other sorting techniques in this video we talk about divide and conquer technique the thing is in the upcoming algorithms which you're going to learn we are going to use this technique so it makes sense to talk about this technique separately the thing is when you talk

about any algorithm what we are trying to do is we are trying to solve a particular problem now of course when You learn a particular algorithm we normally work with limited set of values right let's say five values six values or maybe 10 values but still these are small numbers what if you are working with huge amount of data now that's where one of the issue which comes which is your time complexity right so basically whatever algorithm we are learning we are trying to understand which algorithm goes for what time complexity so basically when we

talk About bubble sort when you talk about selection sort they have a different uh time complexity which is much higher and on the other hand when we talk about quick sort it is much more time efficient so how exactly they work so what they do is they basically take a big task now it can be for small numbers as well you take a task you take a problem and you try to find a solution of it of course every Alor does that so we we have a problem and we find a Solution for it now

in divide and conquer as a name suggest what you do is you divide first and then you conquer and then you combine now what it means let's say we have a big problem called P now what you will do is you will break it down into subsections so you will say P1 P2 and least goes on and then what you will do is you will apply the algorithm on each subsection so on P1 P2 P3 and then what you will get is a solution for that particular sub problem So by doing this you're trying to

solve a big problem by breaking it down into small parts and then what you will do is you will simply solve it each sub problem and then you will merge you will combine them and that's where you will get a solution or a big solution for a big problem right now what if the subsection itself is huge so let's say when when you say p that's a big problem P1 P2 what if even they are huge now in that case what you will do is you will Again divide them into sub parts something like P1

1 and p21 or maybe you can have P P1 goes for P11 p12 so those are the sub problems and then you try to solve them so that it will be easier to solve now that's what we call divide and of course when you divide and conquer don't forget to combine and we have to also make sure that after dividing this problem after solving them when you combine you get a desired result maybe when you solve a particular problem the Subsection they are working you got the output which is desired for a sub problem but

what about when you come combine it you got some different answer even that will not work so you have to make sure that when you combine the work you will get your designed results now most of the people have this confusion when you talk about divide and conquer that we can div the task the way we want right uh no so basically whatever algorithm you're going to apply on the Big problem the same algorithm should work on the each subsection so let's take an example let's say if I want to paint the entire house let's

say we have four rooms there and I want to paint each room so basically painting the entire house is a big problem so what you will do is you will divide the task now if you're thinking dividing task simply means that someone will buy the paint someone will apply the paint someone will clean the flows now that's Not the task what we can do is instead of painting the entire house instead of I mean of course you have to paint the entire house but you can divide the problem you can say okay we have four

house let's divide the four rooms into two four separate parts paint each room of course in each room you will buy the paint you will apply the paint you will clean the floor I I only remember those three steps so basically you will do it for each room so what you what you have Done is you have divided the big problem solve it and then you combine of course you have to also combine those four rooms to get a house right that's what divide and conquerors now let's talk about tree structure of course we'll be

having a separate section for trees because it's a it's a huge topic but I just want to introduce it now basically when you talk about Leist or ar those are your linear structure because you store data one by one now in the Upcoming algorithm somewhere we are going to use something like a tree structure now what exactly tree is in English term what is tree basically you have a root and then you have branches in the same way what we are going to have here is we'll be having a root element so we can say

let's say we have a list of values so these values are your root and then what you do is you do certain things with these values and you get some new branches okay so those Maybe you get some subsections or maybe you clone it doesn't matter the logic doesn't matter here understand the structure so what you do is you got a root element and then from that you create a branch maybe you can create one branch two Branch three branch 10 Branch doesn't matter you create the branches so from that particular Branch maybe you can

create more branches and when you do that you get a tree structure of course we have different type of tree structure We also have something called a binary tree where the number of branches for each node of the element will be only two okay so when you have multiple branches that's not normal tree but when you have two branches that's your banet tree so don't get surprised when we see this of structure in the upcoming algorithms and don't even worry if you not understood the entire tree concept is because we will be having a separate

section on it so you just wanted to Introduce tree so when you see a structure when you see branches and different nodes that's your tree structure and then we are going to use banet tree somewhere where each node so the part the branches ends that's your that's what your node is or you can say leave but that will be having only two branches so that's the B Tre in this video let's talk about recursion now when you talk about different programming language we use methods or Functions right irrespective of the programming language we do have

this concept of course in some languages we do call them methods but calling them functions is not a crime so let's talk about functions here now why do we write functions if you want to achieve a particular task you write a function maybe you want to print something maybe you want to add two numbers maybe you want to find a factorial maybe you want to process the Payment maybe you want to search something on Google everything happens with the help of functions most of the time we call a function from a function let's say we

got two functions here let's call them F1 and FS2 so fub1 is calling FS2 yes we can call the functions even FS2 can call some other function let's say F3 F3 is calling some other function now let's say you're calling F2 from fub1 now what happens is F1 cannot complete its execution before You complete the execution of FS2 because if F1 is not calling anyone F1 will complete its work and then that's done but then what if F1 is calling FS2 in that case fub1 cannot be completed till you complete FS2 so F F2 will

complete and then you can complete F1 but what if F2 is calling F3 in that case FS2 has to wait for F3 and mind you F1 is still waiting for F2 to complete what if F3 is calling F4 now of course everything goes into stack so F1 is Waiting for F2 F2 is waiting for F3 F3 is waiting for F4 once you complete F4 four the pointer goes back to F3 F3 says okay I can complete my work now once F3 is complete you can complete the F2 once F2 F2 is complete you can complete

the F1 and if everything is done you can stop the execution but mind you when F1 is calling F2 F2 is calling F3 F calling F4 there is the dependency so I have to wait for F4 to complete so that F3 can complete so that F2 can complete and Then F1 can complete now here we are calling some other functions right what if a function is calling itself example let's say we have function F1 and F1 is not calling F2 what is F1 is calling itself F1 is calling F1 now now in that case F1

is calling F1 and it can go multiple times so we don't have a different name but you can imagine a stack so F1 is calling F1 F1 is calling F1 F1 is calling F1 F1 is calling F1 the last F1 need to complete first for the Second last F1 to complete the second last F1 need to complete then only we can complete the third last F1 in fact if you want to complete the F1 the first F1 you have to make sure that you complete the entire stack so when you to say a function is

calling itself that is called recursion but why you will do that because if you don't apply a condition it is never ending process right it's like f is calling itself and then ultimately when your stack is full Your computer will give you a error most of the time they're called stack Overflow error and that's why you got this famous website right stack Overflow so we have to apply some condition as well now where it will be useful so let me show you that with an example so let's say this is a very simple Java code

where you got a main function we got demo and from this main let me call a function but before you call a function you have to first Define a Function right so I will say public static I don't want to create function so I will go for static and this function is basically calling uh let's say F1 let's call this function F1 because we're going with that now and then here I want to print something so I will what I will say I will print the value of I but what is I so what we

can do is we can create a variable I here and initially let's say the value of I is zero okay and then we are printing I Here but of course you have to call this function so let me call F1 one here okay simple task we're just calling a function F1 nothing fancy in F1 we are saying int I equal to Z and then we are printing it let's run this code to see what happens when you run this code you will get zero of course that is what we're expecting but what happens after printing

I let me call F1 once again now what do you think what will happen I'm not sure if my system will crash but Let's try the moment I run this code okay we got an error so if you can go up and up and up okay b b okay so we go got somewhere here so I got a huge stack here so you can see we got another which it says stack Overflow error so basically there's a stack and it has a limited memory right and that's why you can see we got all this printing

of zero because that's what they're doing and then once they complete their work they're coming back so that's what is Happening here okay but then there should be a condition as well so what I will do is I will simply pass this I here and let's say the value of I is one and then I'm also passing I here so you have to accept I and what if you don't declare the variable inside okay let's not declare that inside let's say I'm passing the the value from here or maybe I can say 10 even that

makes sense so let's say we are passing 10 which goes here and then if I run this code now it Will not be printing zero because we passing a value it it is printing 10 but of course you have to apply some condition as well so what I can do is before calling I what I want to do is I want to check if the value of I is greater than zero then only I will call fub1 so that means the value of I should decrease somewhere but we are not decreasing it but what if

you do this instead of passing I when you're calling for the next time let's Pass i - one now by doing this what we will be doing is we got all these values now if you're thinking what we have done is basically when you're calling F1 for the first time you're passing 10 the F1 the first F which got called here it is calling F1 itself but not with the same value 10 it is passing with the value nine so next time it is executed it is passing the value which is 8 then seven then

six till where we are going the moment you say I is not greater than Zero then you stop so basically at there will be a point where it goes into minus or negative values now that's why you have to stop and that's why it's stopping at zero if you change this condition it will change change of course example let's say if I say it is one now in this case it will stop at one okay this is what is happening you can do the same thing with of for Loop right so you can start the

for Loop by 10 with the same condition and then you can say I minus minus you that works so instead of using a loop we are using recursion here that means there are certain things you can do with for Loop which which you can also do with recursion example finding a factorial normally what you do is if you want to find a factorial with recursion let's say I want to change this I want to find the fact of five which is 120 if I'm not wrong or 6 is 120 doesn't matter so let's say I'm

finding finding the factorial of five so What will be the logic of factorial basically let's say it gives you a result we'll store it in result and then I will simply print result so let me print result now since we are expecting a value it should also return something so it will return int but what will be the actual logic here now what if I'm finding a factorial of 0o so for 0 and one the factorial value is one right so factorial of 0 is one so I can simply return here one okay at least

we can get This code running let's run this code oh we got an error because we have not changed the function name it should be fact let's run this and you can see we got one so this is working me minimize this okay but what if I want to find the factorial of one even for one it will return one that actually makes sense but what if you say this is two now in this case it should print two which is 2 into 1 we all know what is factorial is right so example if I

say factorial of five or Five factorial is actually equal to 5 into 4 into 3 into 2 into 1 this is actually the logic of factorial so it should give you 5 into 4 is 20 20 into 3 is 60 60 into 2 is 120 so the output I'm expecting is 120 how will I do this so don't you think this is matching with the previous example which we have done we are just lowering the number right so first if you can find the factorial of okay can we do this when when someone is asking

for factorial of five can I say 5 Into 4 factorial because if I can get four factorial and you know what is 4 factorial 4 factorial is 4 into 3 into 2 into 1 okay so if I can get this I can simply multiply it for five and our job is done so here what we can do is we can call the same function by passing the value one less than the actual value so what I'm saying is if I got the factorial of five I can simply return I into fact of I - 1

don't you think that's what we Doing here so when I say I want five factorial we are saying five which is I in this case into 4 factorial which is fact of I - 1 but the question is it will call itself but till how many time it will call and that's why we have to put a condition so we have to reach till I is equal to Z so if I is not equal to 0 you do this otherwise you return one yeah so by doing this you are returning the factorial let's try if

this works and you can see we got two because That's the value is two let's say I'm finding a factorial of five run and you can see we got 120 when you say six we got 720 and if you can go for 10 there's a limit for integer as well okay we got some value but what if you go for a bigger value this is where it will fail I think you can say we got negative value because integer has its own range but you got the idea right what is recursion so the idea is

not about factorial here okay the idea is about Recursion so when a function is calling itself that is recursion in this video we'll talk about merge sort now basically let's talk about the theory first and then we'll focus on the implementation now when we talk about sorting techniques we have worked with multiple sorting technique and when we talked about the quick sort which was going for a Time complexity of n log n now we have one more there which is called a merge sort which also has a Time complexity of n log n now both

quick sort and merge sort follows a technique called divide and conquer so basically what you do is you break down the problem into sub problems and apply the algorithm on those particular sub problems and once you get the solution for each sub problem then you combine the solutions or Subs solutions to get a final solution that's what we are going to do here which is divide and conquer okay so how we are going to do this now Basically it is actually easier to understand so if you can be with me it will make much more

sense so what we're going to do is we'll take a array initially okay so let's say I'm taking a list of values here so let's say we are going for six values here and what are these six values so let's say I have a value which is 8 5 9 1 6 7 let's say so we got this values here and then I want to sort them so what you do is you you will apply a merge sort now basically Here as I mentioned before you will do two things you will in fact three things

first you will divide this problem into sub problems and then you will conquer them and then you will simply merge them now since it is called a merge sort the important step here is merging so when I say important I'm also I'm also saying it is complex part the easier part is to break down this into small parts merging will be time consuming so let's understand this so when you have this Values here what you will do is first of all you will break down into two parts now the question is how will you break

it down in different sorting algorithm we have a different way of breaking the entire list in fact in quick sort we use a pivot but here let's make it very simple we use something called a median now what is a median or maybe a midpoint so here what we can do is as we know that in if you talk about this particular array here the mid is here Right we can see and we can tell that but how an algorithm will know that this is a mid and that's why we will do some calculation now

what kind of calculation it's very easy so what we can do is let's say this is your left and this is your right so what we will do is we'll simply use index values so this the index values for this is 0 1 2 3 4 5 so that depends upon the values you have and then if you want to find a median so basically L represents the first index Value and R represents the last index value so you have to find a median and the formula for median is very simple so what you will

simply do is you will say median is equal to left + right IDE by two that's how you get the median right now in this case the median is what is l l is zero R is five and this divid by 2 is equal to 5 by 2 now since in different languages we get different outputs so let's say this is two in this case uh because in most of the languages We go for the floor value so we got two here now two is your median so this is your median so whatever is there

on this side will go into a different array and whatever is there in this side will go into different array so when I say array I'm talking about the least so what we can do is we can divide into two parts and then we can create a different section so we got a section here which has three values we got a section here which get three values and then the Values will be 8 5 99 here and 1 6 7 here okay and again the job is not done again you have to divide into two

parts now how we're going to do that it's very simple the same steps which you have followed again you will take L and R here L and R here let's find the median of the first point here or the first array now how do you get the median again you will say m is equal to l + r / 2 so now we can do it quickly so what is l in this case so if you go with the Index value index value is 0 1 2 in this case and 3 4 5 now if

you talk about the first array the L is Zer R is 2 so you will say 0 + 2 is 2 and 2/ 2 is 1 so M for this is 1 so m is z now if you want to calculate for the next array or the next values so again the same value so what is l l is three R is five so 3 + 5 is 8 8 / by 2 is 4 so four is here so median is here of course when you look at the values you will find the median just

by looking at it but let's talk About the algorithm and we don't have a limited set of values what if you have 500 values you will not simply search for the median right so that's how we can get the median again you will divide into two parts so we can divide something like this you will get two sections here for this and two sections for this we can say the first section will have two values which is 8 and five the second section will have a value which is n here the first section since We

only have one value here nine we got nine but let's say here we got 1 and six and here we got s so basically that's how you divide again the job is not done so you have to go till the end so what we going to do again you you will divide the first one so can we divide the second one the nine we don't we don't need to divide this part right because when you get one value you can you cannot divide that so let's divide the first part here so if you divide this

You will get again two values which is 8 and five and again you will divide this you will get two values which is one and six so that's how you can divide and at the end you will get the individual values now still we can persist the index value because we are not physically dividing them we are just virtually dividing it right so index value for this is 0 1 2 3 4 5 the index number remains same and if you compare with the actual list we got the index Value and the values are same

right so to this point we have not done any sorting part we just did The Divide part and now it's time for the conquer now when you say conquer it's simply means that you need to sort this value so whatever value you got at the end sort them but if You observe they are already sorted because each element if you compare if you say eight this list is sorted when you have only one value It Is by default sorted okay so sorting is Done so conquering is done basically the next step is actually is to

merge them and the actual fund starts here now when you when you say merge what it means so basically what you do is you start with the first two values and then you merge merge them now merging is important so when you say we are merging 8 and five of course you will get a list and you can again say 8 and five but no this is not how you will merge it so the way you will merge it is this so you will take These two values and merge them into another block you will

get two values but when you are merging it you will compare these two values so which is less here so if five is less you will put five here and then you'll put eight here because that's the only remaining element then you you think about merging so you will you will merge this two now when you're merging this two of course you will get three values right so you will take it take three values here and This is coming from here so this two values and this one value now how will you merge now since

we have two different list or two different values here or two different ARS we can say when you want to merge that's where the actual algorithm starts because when you when you merging two values you can simply compare smaller or get greater but now we have three values in first we have two in second we have only one so what you do here is you basically Compare these values before adding them so what should be the first value now we know that the previous array is sorted right and then in fact both the values are

sorted both the arrays are sorted when you combine them what you can do is you can compare the first two values only the first two values not eight only five and nine so which is smaller five so you will put five here now since five is done you can simply say okay I'm done with five now let me focus on eight and Nine so which is smaller eight and then the only thing remaining here is nine so we will put nine here now that's done now let's combine this three which is 1 6 and 7

now first you have to com combine this two so you will get another box here which is 1 and six so we will compare so it is 1 and six because they are sorted so now you'll combine the next part you will get three values here now when you get three values what we are doing is we are basically combining This section and this section section same steps you will compare the first two values so one compared with seven so one will come here this is done then compare six and seven six will come here

this is done then seven will come here okay and then now the major work starts we have to combine this two now when you're combining this two you will get a bigger array of six elements so 1 2 3 four five six so we got six box now what you will do is you you have you got two ARs and we know that those two areas are actually sorted when you combine them again you will start with the first two values so when I say first two values let's let's compare 5 and 1 so what

you will do is you will compare okay five and one which will come here so it is one so this is done then you compare six and five because five is still remaining right so five and six is five then 8 and six which is six so five done six done then eight and seven so which is seven So seven done then eight again now we don't have anything comp to compare from the next array so you can simply take these two values as it is here this is merge sort okay so you get the

SED value I hope yeah you got the SED value so this is how basically the merge sort works that's how you basically divide and you combine but if you want to do this in programming how will you do it and we'll keep this as a reference so we can divide we can write the section here So we can compare with this now if you want to write an algorithm for this first of all uh you will get an array of course now in this array you will have some values and we can take the same

values which we have here right so let's say we have an array with some values here the same values which we have and then the next step is you basically need to create a function let's say merge sort and this is where you will do this sorting part so when I say merge sort The first thing you will do is you will say divide now when you say divide you have to pass two three things first you have to pass the array then you have to pass the L value R value right and then if

You observe we are dividing again you're dividing again you're dividing so don't you think this is a concept of recursion when you do the same thing multiple times so we have to do recursion here so basically here we have to pass three values right so you will Pass an array you will pass the left value and right value for each array now as this will be called multiple times in recursion every time you have to pass the array the left and the right remember one thing we are not dividing the array physically we are dividing

it logically so even if you divide this array ultimately the values will remain same okay now when I say divide what it means the first thing you will do is you have to find the median or the mid value So I can say mid but then since this okay so let's find mid here so we got mid is equal to we know the formula r l + r / 2 now once we got the median what we're going to do is once you got the median you will break down into two parts and you will

apply the merge sort in each section so what I'm saying is when I'm pass when I'm calling this for the first time I'm passing the entire array with the L value as zero and R value as five which is the last index But again I'm going to call the merge sort by passing different values so I'm going to pass a RR next I need to pass the first array uh index value so the first array here starts from 0 to two which is the median so starting is L ending is median or M middle value

or mid value we can say again I will call merge sort for this second array again I have to pass ARR but this time you have to pass if you look at the values we have to pass three and Five now where do we have three we don't have three anywhere so we can say mid + one so mid is two so mid plus one is three and the ending is right okay so that's how you call the merge sort we have to remember one one more thing after doing merge sort which will break it

we have to merge them as well so when you say merge you have to pass four things here first the are the left value the mid value and you have to also pass the right value again we'll see the Logic later but this is the merge you have to pass but if you call the function by itself you can you can see merge is calling itself but don't you think there should be a limit when it should end so of course there should be a condition as well when your left is less than right then

only you do this otherwise stop okay this is your merge sort so by doing this what you will get is you will get the values divided but where is the concept of merge we are Calling merge but we are not defined the merge function yet now this is where things gets complicated not exactly complicated but it's a lengthy process so what we need to do is when you say merge of course you have to pass all these values here now in this merge what we are going to do now basically the first thing here is

you need to create two arrays I will not write the logic exact logic here but let me just draw something what we need is we we Basically need two arrays here when you say merge at one time you need two arrays example so when we are combining this two we got one array so at one point you need two arrays to combine so that you will get one big array same goes here when you got two arrays here we need to combine them to get a big array so that means every time I call merge

I need two arrays we'll call them let's say left array and right array okay so we got two arrays here the next Thing we need to do is we need to copy the elements of the left array and the right array this is empty at this point so we need to copy this values from the actual array okay now so we need to write a for Loop which will copy data from the array so basically it will copy data from the array and put them in this list okay so maybe I just I will just

write copy values again we'll see the actual logic in the code itself okay next thing we have to do is once we have Done with the copying part you will simply use these two arrays to combine to get a bigger array now how will you do this so of course there should be partition here there should be some values so what we will do is let's compare let's work with the last values here so we got the last value as 5 8 9 and 1 6 7 so the logic of combining this is you will

need multiple variables here you need a variable I you need a variable J now why we need this two Variables one to represents this particular array and one to represent this particular array to it trate then we also need a k which will use which will be used for the big array which you're going to create so out of from this three values or three three values you're going to create an array of six right so K will be handling this part now every time you copy one element so let's say when you compare five

and one and you know that you're going to copy One here so basically the J value will shift here right because this is done the same thing goes here so once you got one next time you will get five here then you have to increment this here so I goes here and of course every time you copy element in the bigger array you will increment the value of okay that's a logic okay so this is how you are going to complete the merge sort now how exactly you have to write the code that will say

in the Practical video so I Hope merge sort makes sense where you basically break down the entire array into small chunks and then you combine them to get the sorted values so now let's implement this logic with the help of java now the thing is first we need a array right so let's create an array here so I will say int a RR and this will have certain values so let's let's have some values here we'll say 3 5 1 4 6 2 so we got this values here and let's apply the Sorting techniques on

this so Before sorting I will print some values I'll say for in n in Array and let's print this values so I will say print n but I will also make sure that I will put a space I will not print on new line and once it is done I'll print on print a new line and then after sorting also so I will set this I will just write it here after sorting so here let's let's do the same thing and let's say after sorting it should print some value but at this Point if you

run this code let's run this and you can see in the output they both are unsorted so because that's why we have to do some sorting here right so let's apply the Sorting logic so what I will do is I will simply call a merge sort method which will basically accept three values the ARR the L now L here is zero and then you have to also pass the array do length minus one basically you have to pass the R value as well remember we have to pass three variables Now since we don't have this

method I will simply say more action create this method and you can see we got this method here and let me just put this method not here but on top now this is where the actual logic is going to happen so you can see we got two variables this should be L and this should be R so left and right okay now as for the logic if you can see in our logic we have already mentioned this logic so basically what we have to do is We have to first check if the L value is

less than R then only you do certain things and what are things you have to do basically you have to find the middle value so I will say int mid is equal to l + r / 2 and then you have to call M sort two times again I'm just going with the logic which I written in the code or in the board here so you have to pass ARR and then you have to pass the L and then you have to pass mid that's how you create two different arrays so mid + 1 And

R okay and then you will simply say merge of course right after doing the Sorting after breaking it down you have to also merge but while doing merge you have to pass three values AR r r uh you have to pass the left mid and right you have to pass the three values so this is the only logic you have to write inside merge sort method but then we have to also complete merging because dividing is very easy this is how basically you dividing the values the difficult part Is merging them so let's Implement merge

here so I will just go back here more actions uh create a method merge yes so I got a method at this point there are private methods is because I'm going to call from the same class but depending upon your requirement you can just change them and now the actual logic goes here the merge okay now as I mentioned you need to create two arrays here right so if you can see the logic we need two arrays let's name this as Lrr which is the left array and this will be an array but the question

is what will be size of it because when I create this are I have to mention the size I don't know what is the size here now based on when it is getting called it will be different size but the question is how we are going to know the size and that's why this l m all this thing comes or l r comes into picture so let's use that and let's get the size so if you want the size of the first array The first section basically you can simply say mid minus L because for

the first array it starts with L if you can see here it starts with L and ends with mid so if you say mid minus L you will get the length right but the problem is since this is zero indexing we have to also add plus one because mid is not representing the size of the array it represents the index value so you have to say plus one then you will get the second are a length with the help of R Minus met so we just put some space here so that it will be much

more visible okay so you can see we got these two values and this is the size you have to mention here the first array will be of size N1 the second array will be of size N2 that's done the next step is actually to copy the values if you can see we are mentioning the copy values here right in the in the notes now how do you copy value we can use a for Loop and let's use two different variables I will say X And Y this time x is equal to Z and depending on

the size of the array so for the first array the size is N1 and x++ not used to using X and Y inside a for Loop but let's try so how do you copy so a RR this values which is X now how will you get the values so from AR RR from the main array we have to start from the left so you have to say left plus X that's how you get the values so whatever value of the L is example if you look at here uh for the first array The index is

012 but let's say if you merging the second array this one the index value is 3 4 5 right so whatever value of L is which is the left which is three in this case it is 3 + x that's how you will copy and thenone so this is for the first one let's do the same thing but your different uh values so I will just copy this for the second array okay we can also use x here no problem we can say N2 and this will go into the right array but the question is

what Will be the value here now any guess so when you say on the right hand side it is your mid + 1 because we are not considering the mid value for the next example if you go up the mid here was two but we started with three so you have to say 2 + 1 mid + 1 so that you will get three okay so we copied what the next step and now the actual work starts of merging and already mentioned we need two variables one is I equal to Z uh we also Need

J for the second array so first array will be counted with I and second array will be handling will be handled by J but we also need one more counter which will represents the main array right and this value will start with L because you have to start from the left hand side now once we get these three values let's start merging them so we have to do multiple times right when you say merge you have to take my value from here example when we were doing this we Would compare the first two values compare

the next two values that's how we were doing right so when to end this if your I value is less than N1 and not this hand and J value is less than N2 we'll we'll continue till this point if they are not true then we'll have to stop because that means we have to we have actually reached the end but now question arise how will you merge and that's where you have to start comparing values now when you say compare what it Means compare five and one so basically the first element of this array and

the first element of this array let's compare them how will you do that so let simply check if the L array of I because that's what is representing the L array which is the I variable if it is less then and we can also say equal to what if they're equal then we have to compare this with the r array of J if the left one is smaller in this case the R1 is smaller not the left one but let's say If the left left one is smaller in that case you will put that into

the main array so array K is equal to l array not length L array of I now since we have used so let's say this was a smaller value and once we have used this we have to cancel this right I mean this is done so we can shift our pointer to the next next element how do you shift your not the pointer but the reference you will simply say i++ here in this case but what if it is not same or not is what if It is not true in that case you will go

to else part you will do the same thing but not with the left array you will this time you will do with the right array and then the J variable and you will say j++ and every time you run this Loop because see after one of this Loop basically you will get the first value of the array right main array you will simply say k++ because you have to also increment this so once I is done because K is here once once I is done you have To move K here okay and that's why you're

doing k++ and that's it this is your merge sort let's see if that works let's refresh this or this rerun and we got an error something went wrong you can see everything was going well but this four is not at the right place we got one there because sometime what may happen is when you copying two arrays what if the values are left in one of the array example if you look at our example when we were copying this Remember when we were completing the entire task these two element were remaining from the first array

which goes at the end so that thing is not covered yet so what you do is for the remaining elements of the particular array you will again run a while loop here so you will say if I is still not equal or still not less than N1 you will simply copy the remaining elements whatever is left because after this Loop at least one array will be ended okay so We have to work for the second of the remaining element of one of the array maybe left hand side or right hand side first we'll try and

to understand left hand side let's see what happens on the left hand side simply copy all the values so you will say AR of K is equal to we have to copy from the left array and let's use I here now every time you do this you you will increment both the elements I and K both so this is for the left hand side left out left out values The same thing should be done for the right hand side so this time I will say J is less than N2 in that case you will copy

but not from the right left hand side you will do it from the right hand side the variable is J and the increment you'll do for j++ okay and let's run this and you can see now it is sorted and now it doesn't matter what values you have let's say let's take the values which we haveed on the board which was 8 what was the value 8 5 9 1 6 7 and if You run this you can see we got sorted values let's add some more values here just to remove the confusion with different

values let's say 111 this is 57 and now let's see 6 7 8 9 57 75111 so this is your merge sort so the steps basically you have to first do the breakdown of you have to break the array down into small chunks and then you have to also merge them the only thing you have to remember is when we were drawing this we were going in two sections right Something like this we were saying okay we will create two different section and then first section will break into two parts and second section will break

into two parts no that's not how it is working If You observe what it will do is it will break down the entire section into two parts yes but then first only you will get the first part then you you're not going to the second part okay you're not looking at here this is not there yet you're still into the first Part then this will divide into a section you will get this 85 then you're dividing into two sections which you will get 85 and then you will merge them then you will start break breaking

down the second part which is nine okay nine was still not there then then once this is also merged once you get this it will start working on the next part then it will work on this it will work on this this merge and merge I mean sorry break down then you get seven then you merge This two and then once you have merged then it will go for the next to so it's not exactly breaking down the entire section equally it's basically going from left to right so yeah that's how things are working out

and this is your merge sort with the help of java code and I hope this makes sense let me know the section in this video we'll talk about link list but then why do we need to go for another data structure now to this point we have talked about arrays Right so whatever examples we did we did with the array concept now array is great so basically what is array just to rrate if you have a sequence of values which you want to store together we can basically use an array so this here is an

array so basically array will have different values and then every value here will have a index number as well so basically this is index zero index one index 2 index 3 and inside this you can have any value let's say if the value is 5 8 1 6 so these are the values you have there right now if you want to search or if you want to get any element from this it is very easy right example if you want a third value you can simply say okay I have an array and I want the

third value that means you have to use the index value too so basically getting a element from an array is very easy you just have to specify the index number and you will get the value and if you want to understand the time complexity For this this will be Big O of one is because you simply specify a index number you will get the value it is so fast but there's some problems as well the problem with array is the size of the array is fixed that's the basic property of an array now once you

create the array of four elements you can maximum have four elements you can't go beyond it so let's say if I want to add one more value here it is not possible is because the size is Fixed the solution could be there are two solutions here actually one uh what if you can create another big array something like this and store all the four variables here so you have to basically copy all the variables and then you have to copy all the values and then you can add the extra value let's say you want to

add seven so basically you'll be having 5 8 1 and six and then you can have seven so what we did is create a a new array copy all the Elements and then add a new value what if you want to add more values the same process goes on one more thing you can do is when you created the new array let's not have a size of five maybe the new array which you create will be of size eight so that you can accommodate four more values but again the problem is if you go beyond

it again you have to create new array again you have to copy the elements and then uh save it I know what you're thinking you might thinking Okay what if you can create a array a big array of s 1,000 okay two problems the first one is what if you don't have that much of amount of values to store maybe you want you just have five to six values or 10 values and the size of the array is th basically you are wasting the memory that's one issue the second issue is what if the value

goes beyond 1,000 again you have to get a new array so array is good in terms of searching in Terms of I mean fetching the value but it's not good in terms of you want to insert the value and if you want to expand it also there's one more problem which I want to point point out is let's say if I want to insert a value in between of course adding the value at the end is very easy U let's say let's do that with this particular second array here so let's say well let's work

with this what if you want to insert a value somewhere here so I want to say 58 And maybe I want to insert two in between now when I insert a value two in between what we have to do is we have to move all this value on the right hand side again a complex process and also it will take a lot of time so basically doing anything updating with the array is a headache yes if you add the value at the end not a problem but if you want to add a value at the

start or in between it creates issue and that's where we can look at something called a Linked list now what we do in link list is we don't store the value in sequence it has a different data structure Al together so you don't store the values in sequence so how do we do it so what I will do is I will just use another page here to talk about it so when you talk about a concept like link list in this what you do is you do a very simple thing you if you want to

store values let's say I want to store 5 8 1 3 Let's I have this values here I want to store This values somewhere one way you can use array but we have talked about the problem with it so what we can do is we can store the values in something called node so when you talk about link list we have certain terms which have to remember the terms are node the terms are reference or you can also say address in some of the languages we call them address let's start with this to so basically

what you do is you create the values so you store the values in a node So this is how the node looks like okay this will be a node and in this node you will store the value five you will take another node and in this in this you will store eight uh you will take another node where you will store one you will take another node where you will store three so basically what we doing is we are storing all the values in the node so these are nodes but the problem is how will

you maintain the sequence because these are sto Lo Somewhere they're not a sequenced memory because in Array what you do is you use index values right uh so example if I name this array as n basically the address of n represents the first value which is five in this case now if you want the next value what you can do is you will take the address of and let's say 101 if you want the first value you can say Okay I want something which is at the address 101 but if you want the next value

you can say okay the next Value will be at the address 101 + 1 the next value will be available at 101 +2 and that's why we have this index value something like this but in link list we have we don't have that scenario of course this nodes will be having some address to it uh let's say the address for this is 105 uh the address for this is 206 and the address for this is 512 this address for this is 68 now all these are addresses okay nothing fancy Just simple addresses now if I

want to fetch a value let's say five then of course I should know the address of five which is 105 if you know it that's great you will get the value if you want the second value of for link list now we have no idea what is a second value but if you know the address you can find it but if you say hey I got a link list I want the second value there is a second value so what you have to do is if you want to chain them if you want to Specify

the sequence in a node basically you can have two things the first thing you will have is data and the second thing you will have is reference or maybe you can say address address so here a node will have one more section every node will have one extra section here let me draw it here and then what you'll be having in this SE section it's very simple in this section basically you will have the address or the reference of the next node so for the First node when you talk about this node this node should

have the reference of this particular node now how will you do it it's very simple the second box in the node will have the address which is 206 okay now by doing this what you're doing is you are creating a logical linking between these two then what about this next element so we are saying that this one here is the third element so of course what you will do is you Will say 512 here by doing this you are creating a link here again what about the next value so of course it should be 68

so that you can create a link here and what about the last value nothing we don't have any ments after that so you will simply say null because we don't have anything after it now this is your link list okay now why it is called a link list because we have a list of values and they are linked they are linked with the address of the reference Okay so the first section here is called the data or you can say the info the second section here is basically called the reference and same goes for the

each node which you have okay that's how you can basically add the values now you'll be saying okay what if I want to insert a value in between or maybe let's add the value at the end first what if you want to insert a new value very simple what you will do is the moment you say you want to insert a new value every Time you want to say insert new value you have to create a node and node will have two things as we know now the first thing it will have the data let's

say the new value you want to insert is maybe three three is already there let's say six you want to insert six create a new node and in this node you will assign the value which is six and by default the reference will be null okay but then we want to make sure that this element is the last element in your list In that case you have to make some changes now what are the changes basically we have to create a link between these two how will you create the link the way you do that

is by changing this value of null so you will simply remove this null from here and change the value to the address now we don't have the address yet so let's say the address for this is 126 so basically you will insert 126 here and that's how you can create a list and you can append The values so the first value is this so this is your first value second value third value fourth value and fifth value now how do we know the sequence is because you start from the first element and then you jump

to the next element then next so basically you go from here to here third element fourth element and Fifth Element is that simple but again the question is how do you know that this is a first element so basically we need to have one more concept here which Is called the head okay so every link list will have a head as well so head is just a reference which is pointing to the first location okay so you'll be having an extra variable which will point to the first location is that simple okay now what if

you want to insert more noes but not at the end this time maybe you want to insert in between what you do in Array is you basically shift all the values time consuming process right so here what you do is Again when I say you want to insert a new value in between I me let's say in between later you want to insert a new value you want to you want to have a new node so what you basically do is you create a new node so maybe I want to insert the value in between

these two okay so after eight I want to have another value maybe I will just write the value here so let me just shift all this values on this side and the value I want to insert here in between is let's Say two okay so I want to insert two in between so between 8 and one so the steps are very simple you create a new node that's what we always do create new node and assign the value which is two but we have no idea what should be the reference so by default the reference

will be null as always but now we are saying that we got a new node and this should be coming between 8 and one so what you do is you make some changes the changes which you will make is this First you will remove this part because this should be now referring not to one value should refer to this particular location and for that you have to change this address from whatever value initially it was maybe 512 you have to change this to a new location so new address for this it should be it should

be having some address let's say 136 now this is a new address so you will insert this address here okay now by doing this what we have also done is now this this Particular arrow is not pointing here so this need to be removed so there's no more AR Arrow here the arrow will be pointing to this location and then we have to also make sure that this two next location is this one so again you will make some changes you have to make this particular uh link and to do that the same step which

you have to follow change this address from this value 2 512 by doing this we are we have added a new value a new Node in between the list okay so we have add new value which is two it's that simple this is how basically link list works now can we remove a value so I want to remove this one how do you remove one so you think about this pause the video think about this and then we can continue okay so I hope you have paused you have thought about this for some time now

let's understand now when I say you want to remove this one it's very simple the only change you have to Make is this address okay if you can change that your job is done right so you can simply change this address from 512 to 68 by doing this what we are doing is we are referring this here so basically we'll be referring this here so that is referred what happens to this one this will get garbage SED if you are using a garbage values because there there's nothing which is referring it right so now we

are referring this that means we have to remove this arrow and This Arrow this will be deleted there will be a link here but it doesn't make sense right it will not be used so if you want you can delete this reference also and in fact this will be garbage selected so this values is gone now if you see the list we only have 1 2 3 4 5 values so this is how basically link list works so now this type of Link list is called the singly link list reason being you can only go

one way so if you know the first value which is this so by Using this you can go to the next value you can go to the next value you can go to the next value and next value but the question is can you come back let's say we are here it is easier to go forward because because you know the next value but can you go back can you Traverse in the reverse Direction no you can't do that and that's why if you want to achieve it we have to use something called a w

link list now what it means is W link will not just have one address It will have two addresses so every node will have two address so something like this so this will have one more address here this will have one more address this will have one more address this will have one more address and one more address now in this new address or reference what you will have is uh let me just remove this particular Arrow from here so what you will have in the first one is null because you don't have anything before

this so before five you Don't have anything in the eight in this particular value you will have 206 by doing this what we doing is we are specifying that the previous value for this 8 is five so that is in 206 now what you will mention here is 105 is because the previous value for this 8 is which is the address is 105 now what will happen here this will have 206 the previous address what will have this it will have 136 the previous address now it doesn't matter where you are okay we Have to

change make change here as well which is 68 now it doesn't matter where you are you can actually Trace back so if you want to go forward you will use this particular address for going forward if you want to come back you have to use this particular address okay and that's how basically you use linkl which you have single link list double link list and that's how it Travers what if you want to print values it's very simple you Traverse between the elements And print the values now let's try to implement link list using Java

so what we'll do is first of all let's open the ID and you can see we have an ID here and then here let me create a file and we'll name this file as let's say main. Java this is where I we'll write our Java code I mean the main code so let's have a main method here now the thing is when you talk about link list of course we'll try to implement link list by ourself but then in Java we have a inbu Class called link list so if I say linked list of java

which is inbuild so let me just use this class you can see this class belongs to a package called util and if I jump to this class there are lot of methods inside this already present so if you can see we got link first which will give you the first element uh then we got link before link last there are different methods available but if I want to explore it let me create object of Link list first And I will say the link list is nums so let's say we are going creating a list of

numbers here and then of course it is giving you a warning because when you use collection basically it belongs to a package called collections or a concept of collection and when you work with collection we have to also specify the type of elements we are working with but at this point let's keep it very simple let's say numbers if you want to remove this warning and if you know collection API on generics we can specify integer you can see the warning is gone but just to simplify stuff let's not do that ignore this uh error

or warning till this point now if I want to use this nums I can add some values here so let's say if I want to insert a value I can insert value which is five so that's my first value U add one more element let's say nine and all this actually we are creating the elements and then every element will have the reference as well So basically when you create five it will have a reference of 9 as well okay can we print all the values here so if I say nums dot I think it

should print nums should print all the values run and you can see we got five and nine uh and the sequence also you can see they are in sequence basically they are following the concept which we have done here so there's element and there is also a reference so every element will have a data and the reference as well for the Next element okay uh do we have some other methods here can I add at first you can see we have a method for that which is ADD first and we can have an element which

is nine so now or not nine nine is already there let say six so now what will happen is it will add five and nine and then we are adding six later but then the method which we are using is ADD first which means this six will go at the start run this and you can see we got 659 other methods we'll say nums Dot what else we can use we can also get an element with the help of index value now when I say index two it should return 9 so in fact I need

to print this first so printing it here and run and you can see it is printing nine so that's element at the last and it's index value two now the funny part is link list data structure which is an abstract data structure does not work with index values now even if you mention two here what is happening is it Is B basically tracking between the elements and this can be time consuming okay so when you talk about AR list or array they are fast is because they follow index numbers here we don't have index value

basically we are jumping between the elements so it goes to head first head is pointing to five then it go oh sorry head is pointing to six because that's the first element and then five then nine it finds nine and it is printing nine do we have a way to Print the head so basically we have a method called Peak first which which should give you the head uh but when when you say Peak Peak will give you the head element okay so we can also use this uh to get the head head element okay

so this is how the inbuild link list works but then we don't want to use inbu we want to do this by using our own code and I don't want to use this name which is ADD of course we can actually use add and add first or maybe let's use This so what I will do is I will remove this package from here the moment you remove this package now we have no idea where this link list is so for our Java code this link list does not exist so let's create one of course you

can use the in build one but let's create our own link list so I will click on more action and I will create a class called link list I want this to be in same package so you can see link list class is created now and if you try to see the Code side by side so this is how this is how the code looks like side by side or maybe I will also put this in the bottom so move this to left bottom so now you can see it is in the bottom so we

can actually have the view of two screen here to code so basically what we are doing is we are calling lingl right so class is created and you can see there's no error on this line now but there is an error on this line so what we need is we basically need a method which will Add so I will say public void add which will take a number so I will say integer I and we are only working with numbers so let's stick to it and you can see there's no problem now so these two

lines are clear but the question is how will you add now if you remember every time you add an element basically we have to create a node or you can say element but let's say let's be specific node and we don't have a node yet so what I will do is I will Create a node so I will say class node that's the class I want which will represents two things so every node has I mentioned before so this was the example for w link list let's create one more again so basically every time you

create a node a node will have two things so this is your node node will have two things the value and the address let's say the address for the next one is 216 but at this point we don't know the address so initially it Will be null here so this is your data and this is your reference or we can say address here so how do we do that in Java so of course if you want to store data we can directly say data but what about the reference how will you get the reference now

in Java if you want to refer something we basically create a reference of it now reference of what the reference of the next node so whatever next node you are going to create of course this is also a node Right so type of this particular element here is node So when you say you're getting a reference you have to get a reference of node and we'll say next just name name for it so what we are doing is instead of using a name reference we are going going to say this as next okay uh so

we got data and we got next okay so those are two things and maybe just to simplify this more every time I create a node maybe I want to assign data as well so maybe we can Do that with the help of Constructor or maybe not let's try that next time or after some time now let's add a value how will you add the value now what exactly adding value means and first of all let me just change this to data itself it makes much more sense to use data as a variable name now uh

what I will do is I will create a new node basically every time you say you want to create add element we have to create new node right for example if I say I want To add eight I have to create a new node basically right so let's create a node here and I will call this as new node equal to new node okay so we're getting a new node here and I want to assign a value to it so of course you can say new node. data is equal to data so whatever data you're

receiving from here is getting assigned to this new node data so data is there but what about the next element so by default the next element will be null so instead of specifying That two things here we can do one more thing you know so we can create a Constructor here for this node and this Constructor will take the data as the parameter and then we can say this and I hope you know the concept of this now at this point so this do data is equal to data and next is equal to null by

default so every time I create a node the next will be null so by doing this the advantage you will get is you can directly pass your data here so you Don't have to write one more line okay so if you're thinking this is done yes we got a new node so let's say uh let's keep this empty so uh let me just clear the entire stuff from here let's say the the entire link list is empty now when you say link list of course there should be a variable called header right so every time

you create a node and this if this node is your first element then you have to make sure that your head is pointing to that element okay also what If this is not your first element in that case you have to add uh you have to make sure that this new node gets added at the end okay so when you're saying nums do add five basically it is it is creating a new node but there we're not pointing it to head how do you refer that head it's very simple you come back here and don't

you think the head itself is a node so you will say node head is equal I mean node head which will by default equal to null because it's not Pointing to anything and now what you can do is now when you are adding five of course it will create a new node for you which will have two things it will be having a value which is five that's what you're adding here and then the by default value for reference is null but you have to also make sure that your head is referring to this particular

node we're not doing that yet head is still referring to null now if you want to make sure that your head refers there What we can do is we can say head is equal to new node okay our job is done now your head is actually referring to new node but what if here if you see line number nine what we are doing we are adding a new element which is nine so that means we are creating a new node here which will be nine and by default the value for reference is null which is

next null next is null but you have to also make sure that when you add nine it should so five should refer here but Looking at our code even if you add nine even we are making nine as a header don't you think that is wrong nine is not header right so that means we need to do this only when your head is null if your head is null then only you will write this line of code otherwise what if your head is not null that means you have to make sure that your next element

which is nine in this case is the next part of five is the next element of five but how do you know which is the last Element so in this case five is the last element but we have no idea five is the last element how do we know in the code so what we can do here is we have to basically track we have to basically track from the first element till the last element and when you say you want to track basically we need one more variable here which is which we call as

current it is referring to something that's what we are saying by default is null or maybe by default we can say this Is head but if the head is null okay so we can say by default is head so what we can do is we can Traverse and the way you Traverse is with the help of while loop so we can say while current do next is not equal to null so what we doing is if current is referring to head by default so current is here initially and we want to know which is the

last element so n so in this case five is the last element right so that's what we are checking if the current next which is Here is not null so basically just to change the value for five the reference for what you can do is you can say current. next is equal to new node the moment you do that what we are doing is the new node here is this nine right nine has the address let's say 121 and five has the address let's say 101 so what we are doing is we are replacing the

value of null here with 121 that's what we are doing in lse Block here okay uh so current do next Next is this particular value or this particular box and we are replacing that with 121 but then what if you are adding one more element here uh in the code are we doing that no so let me add one more element not add first let's say add six so now this is six by default the value here will be null and let's say the address is 212 now we have to make sure that the 212

address is specified here now how will you do this how will you create This link so basically the code which we have written by doing this code every time you create a new node basically it will change the address of the first node we don't want to change that because in the else block that's what we are doing we are not traversing to the last element now how do you Traverse to the last element so to Traverse you will simply say if current. next is not equal to null you will simply change your current value

now how do you change the Current value so you will say current do current do next by doing this what we are doing is initially current will be here right and then we are saying this current is referring to the head next that means it is referring here so this is what we are doing here so current equal to current. next so it will refer to the next element okay and then again if this is not null it will go for the next one so that's how we are traversing and by Doing this basically we

have done with the adding part let's see if this works let me just rerun this okay so we will do we will get the eror because we have not done get and Peak at this point let's comment it and run this once again and you can see it is printing the address of Link list okay so the thing is link list is our own class so instead of saying nums printing nums what we should do is we say nums do print values so basically it should print it it Should call Print values but how will

you print so what we need is we need a method which will print the values okay so it should print all the values vales of this list now how do you print the values now that's a tricky point now when you say print it's actually easy what you have to do is you have to start from the first element print the value then move to the next element print the value move to the next element and print the value that means you need a counter Okay not counter is because this is not a array you

basically need a reference of node and let's say again current because at one point you're referring to only one node right so let's say current and current will start from head and the only thing you have to do is since we are jumping between the elements multiple times we'll use a while loop and we just have to verify if current is not equal to null then of course you have to print what if the uh link list Is empty in that case the head will be null so we'll say while current is not equal to

null you will simply print current. data and then you have to move your current so basically once you print data of the first element which is this then you will say next and we know how to do next now so we have to say current is equal to current dot next and that's it it will print all the values the only thing is it will print on new line I want to print on the same line so I will Give a space here and once the while loop is over I'll print a new line and

let's run this and you can see we got 5 9 6 and we got all the values in sequence so yeah this is how basically we use Link list to add the values but we have more things to do right what if you want to add the value at the start what if you want to uh delete a value from between now that will see in the upcoming video so till this point we were able to add the elements in the Link list right so basically what we did is we have added three values if

you can see here uh we got five 9 6 those are the values we have added uh let's not work with this to okay so you can see we have added these three values and then when you run this code this is the output we will which we were getting right so we got 5 99 six and it's working now basically we have to do one more one I in fact two more operations one is to add the element at the start And then the second one is basically to delete an element so whatever we

have done in the Practical is basically we have created three nodes so when the first node was created so this was basically your first node which has two section the data of course the data is five here and of course there's some value here some uh some reference which will be by default null but we'll change this later and this will also have the address uh let's say this is 121 and then we got another element here so this is another element in a box and let's the values we have is N9 and this will

be null by default and then we have one more element here let's say let me just draw that here and then the value we got is six and it will be null and everything thing will be having an address let's say this is 301 this is 101 but what we are doing is since they are in a link and with the help of this code which is ADD we have also made sure That every time you add the element you basically get the address of the new element and add it in the previous one right

so basically uh the value which was null here will be replaced by uh the new value which is 301 which is referring this and then this will refer here the the way it will do that is by removing this null and this will have have 1 1 this is what we have done right the last element will be null because we have we don't have any element after That now we also have one more variable which is your head and head is basically pointing to the first element right that's what we have done when we

created this uh link list so every time you add the value it will check if the head is null it will assign the new node there but for other elements it will simply add the element by tracing where these are last element now what I want to do is I want to also have a function here let's say if I say do add I want to say Add first so that it will add at the start so the element I want to add here is let's say seven so I want the seven to be the

first element here now how do we do that first of all we don't have this method so what I can do is I can just click here now based on which ID you use you will get this option so create a method and that's the method we have so this is responsible to add the element and let's say this is not I this is data now how do you add the element At the first now this is tricky so when I say I want to add the element at the first the first thing you you

do is you need a node so we have to get a node and this node will have two things the data which we are adding is seven so that's pretty clear but what about the address which will be on reference which will be null which is the next value basically and then of course this will also have some address let's say this is 206 that's the address we have now when you Say you this is your first element don't you think the only thing thing you have to do is was create the node and just

shift your head here so instead of having your head here let's shift it so the way you do that is first youate create a node so I will say new in fact you can just reuse the code right so whenever you add the element this is something you will be doing for sure so not cut I don't want to cut that so let's reuse the code so copy paste now That's done so we have created created the new uh node the next thing you have to do is you have to change your head I mean

not your head the head from the uh from the link list now there's one problem if you directly change your head here we also want to know that this if this is the first element then if you move your head here this element should be the second element right so we have to make this a second element that also Means that this should know the first element so basically we are moving our ahead here and then we have to refer this okay so how do we do this so one thing you can do here is

so this new node do next will be referring to the first element but how do we know the first element the first element is actually referring to the head as well right so if you want to create this link here basically we have to get this address which is 102 and that's what we Are doing here so we are saying new node do next is equal to head that's where head was pointing and now once you got it you just have to shift your head so you have to say head is equal to new node

and that's it we are just shifting the things here so head is referring here and this is referring to the SEC the first element which was previous element and now we got a new new element which is at the start let's see if this works and I will just run this code we Should see 7 the start and you can see we got seven at the start so adding the element at the start is done what's next maybe I want to delete an element so here let's say I want to delete nums do delete I

want to delete let's say nine okay this is the element I want to delete how do we delete nine so basically we need a method first of all which will do this so I will say create delete method and in this I want to delete a particular Data now we don't first of all we don't have any idea that where is the element because this element anywhere uh so basically we have to travel to that particular node right and we have to start from head so basically we'll we'll start searching for head so we'll go

here is it nine no is it nine no is it nine yes so once we get nine we we'll delete it now when you say you want to delete the only thing you have to do is okay first of all let's go to That nine okay so the way you can go to the nine first you have to take a reference let's say current and current will start with head so that's how you you're starting now from head so how do we basically travel between the nodes so we can use a while loop because we

want to travel and we can simply say current do next we have to verify is the next element empty because of course you have to stop right we have to stop somewhere so the moment you you get null we'll Stop it otherwise we will continue and also we have to check one more condition that the data which you are searching for is not there because once you get the data you will stop but when I have to stop so basically the moment I go here then so initially we are at the head so we'll check

if is this this uh element we are searching for if no then we'll shift here and we'll check for this data when we reach here we'll check for this data that means when you are Here then you are checking the database nine but when you are here how will you check the data of the next node so we can say current dot next dot data right so currently we are at five and then we are checking for the next element data so the way you can do that is by saying current next. dat should not

be equal to data which you're searching for because if it is equal then you have to stop that's what you're stopping but if it is not there then you have to keep going The way you keep going is by saying current is equal to current do next so what what we are doing in this T in this step is basically we are shifting so if you are here then we are shifting here how do we are shifting here so we we have to saying current is equal to current do next which is this element oh

I forgot to change this data here so this should not be null this should be be 121 right yeah so let's say we have we Have reached here now once you reach here when you know that the next element is nine what is a step you will do so the only step which you have to do is if you want to delete this what if you can simply change your next element to this element don't you think N9 will be removed so how do we do that so first of all we have to check if

current do next is not equal to null you have to make sure that the next value is not null and then you can perform the operation so The only thing if you do is if you are here so this do next should not be this element this do next should be this element how do we do that so we have to say current. next is equal to current. nextt do next because current. nextt will give you so if you are here current. next will give you this I mean this value will be referring to this

element we just have to say this value should be 101 so the only thing you have to do is Change this value from 3 1 to one1 and the way you're doing that is with the help of this line and that's deleted okay let's see if this works let's run this and you can see nine gone okay this is that simple it's just that traveling to that point and changing the node of the previous one because the moment you change this value you're done you don't have to actually delete the value or delete the node

because it is now now we don't have a reference for this one this Will be garbage collected especially in Java we we do garbage collection so that's about link list where we were able to add element at the end at the start and also delete in this video we'll talk about stack now stack is basically a linear data structure so we can use it to store data now the question arise why it is different the thing is stack follows something called last in first out so as you have seen basically we were able to stack

data on Top of other so here we were using devices but we can also store data in the same format so basically what happens is you can create a stack but then stack looks something like this basically you have uh this type of memory where you only have one entry point and the same entry point is also an exit point so let's say if you have some list of values which you want to store so maybe I want to store 5 8 6 three so I want to store this four Values now what happens is

when you want to store this five this five basically goes into the stack but the question is where it will be stored so it it will be stored somewhere here so five will be here okay and now once you store five now you want to store uh eight it goes on top of five so eight goes here now what happens here is it follows as I mentioned it follows leao which is last in first out basically the last element which you have entered will be the first Element which will come out just like stack of

books or stack of devices or stack of plates so the last thing which which went inside which is eight is the first thing to come out okay so we use a concept called push and pop so when you want to insert data we use push when you want to get data out we use pop so at this point if I say hey this is my stack let's say stack is nums and if I say hey nums pop so what nums will do is it will give you the last element entered which Is eight in this

case but let's say you enter some more data you want to insert six as well so six goes here now when six goes there basically when you say hey I want to pop now so you have it will give you six so if you want to insert data you will say push when you want to get data out we use pop uh basically we have certain terms you have to remember what if the stack is full so let's say the size of this stag is four or maybe three itself let's say this tag The size

of this tag is three and now you have entered three values but what if you are entering a new value so instead of three let's have some other value so that you will not get confused with the size of the stack and the values let's the value is nine here so when you are inserting nine now now we don't have a space right so nine when you try to push nine it will give you an error called overflow and you might have seen this error right which is called Stack Overflow the website it came from

this word which is Overflow so the stack overflowing so nine is not able to save there also there's one more term called underflow now what is underl let's say you have a stack which is empty so we are getting a new stack here which is empty in this case and when you you say hey I have empty stack here I want to pop now we can only pop the elements when they are there it's not there so we don't have an element there so it will Give you an ER which is underflow so overflow when

you have a stack full but still you're trying to insert data and underflow is basically where you don't have any elements there but you still try to fetch data or remove data so one thing to remember with pop pop is basically a function or a way to get the element out so of course it will give you the element that also means that the element is coming out so example let's say at this Point I want to do a pop on this stack basically what I'm also doing is I'm popping this six out so now

if you say how many elements I have in this stack only two okay and again if you say pop on this particular nums it will take this eight out which came with the underscore but that's not how it works let me just do that again so eight will come out again when you say pop the five will come out again when you say pop it will give you An error which is the underflow error or underflow exception so basically pop means getting the data out but let's say you don't want to get the data out

you just want to see what is the last element so we use one more thing for that which is called Peak now Peak will give you the last value but it will not remove the value from this tag so if you just want to check you want to Peak you can use Peak but if you want to get the element out you use a pop when you want To insert data you say push so this is your last in first out inside stack now question arise how we are going to implement this so there are

two ways of implementing this one you can use normal array in fact in Array itself we can use uh fixed size array or we can use Dynamic array now in fixed size basically by default in most of the languages when you say array it's a it's a fixed size but you can make it Dynamic so you can expand the stack or the array The way you want so overall stack is a concept okay so if you want to implement that we have to use array the another way you can do that is with link list

we have already seen link list so we can also Implement stack with help of Link list the advantage would be there's no problem of the size there because in link list you can expand the link list the drawback is it will a bit slow but that's fine anyway you are going to remove the data from the last right so You can Implement stack with the help of linklist as well so yeah that's about stack and how do we are going to implement that so we are going to write a code for array u i mean

using array for stack okay so let's try to implement the stack in Java so what you do is basically you know we have talked about the theory right now if you want to use stack in Java basically we can simply say stack and it's a inbu class available in Java so I can simply say Stack and if you can see this is the package where you find stack so if I click on stack you can see it's a class and basically it provides you the methods which we have talked about we have talked about push

uh be we also have a pop here then we can see also Peak so everything is there right uh but then I don't want to use inil but even if you're using inil let's see what happens so if I say uh stack nums is equal to new stack I don't want to use Any specific type of data which we want let's go for objects and if I want to add data I can simply say push and when I say push data let's say 10 now what happens is in this stack we only have one value

which is 10 okay so if I try to print this stack which is nums let's see what happens I right click this and I say run and in the output you can see it says 10 so you have one data but what happens when you push more data here so I can just simply copy paste this one More time so we got four values now and let's say this is 30 this is 70 this is 20 and when you add all the values here if you run this you will get the output of all the

values you got 10 30 70 20 now yes it looks like sequence the way you have added but in stack is goes in first in first out basically the 10 got insert first 30 get insert later then 70 then 20 let me prove my point what I will do is I will simply say nums do popop now what pop will do is it will Remove the last element or maybe I can also do this not here but after 30 so when I say pop pop will remove the element the first element okay so when I

say first element uh not exactly first element it will remove the last element last element which got added so the first element which you can access is the last element and know that sounds weird but that's how it works so if I run this again it will remove 30 so that's where it got popped in fact pop Will give you the value if you want so you can store that value somewhere maybe you can print that value somewhere if you want let me just print it here so I'm printing that value which we popped out

of this and you can see the value is 30 so we can do these things in fact we can also use speak but I don't want to use the inbuild class let's create our own so the what thing you have to do is when you see this stack let's create our own Stack so if I say okay give me a suggestion okay so more action depend upon which IDE you are using it will have the same thing click here I want to go for the default package and you can see we got a stack class

so we have two stack on the top but one is coming from the util package which is inbuilt I don't want to use it this is the tack I want to use let me separate the code somewhere so that you can see both okay so right hand side we have our own class And on this side we have the main okay so I want to achieve the same thing but at this point let me just comment the pop part let me Al only work with push unfortunately we don't have push here so let me create

one method which is public void push and this will take a value from you so I will say int data let's say and okay not declaring it defining it okay but then where you will push it of course you need an array here right so as I mentioned there are different Way of implementing stack one of the way is you can use array so let me use an array here so I will use a private int array so let's name this as array itself of course you can use any any variable name doesn't matter and

then I can assign some size to it so let's say the size of this array is only five so the max value you can have is five okay now apart from this if you remember the theory we have talked about some variables one of the variable you have To remember is top now top will refer to which is the last ele which you have added I mean the index value so let's say added you have inserted three values so the top will be representing three okay but then by default the value for top would be

minus one because we want to start from minus one because we don't have any values yet so it's minus one uh we can take one more variable here which will Define the size of the array so I can say int size but then I can't assign The value here we should take the value of the size of the array so we can take that in a stack Constructor so I can say stack and inside this I can say size is equal to the size of the array do length so that's my size that's a maximum

size I can have uh in fact let's also declare Define the size of top inside the Constructor and that's done if you want you can also Define this array creation inside the Constructor okay so you can have a declaration here assignment you Can do it in the Constructor but again that's that's your implementation way okay so once we got that how do you push element there so pushing is actually very easy you take your array and say okay I want to insert at the first location which is zero because add starts with zero and you

can save the data the job is done you are able to push it okay let's see how it works but also we can't say nums here because we are creating our own class so if you Want this to work you have to implement two string method but instead of doing that I will say public void print string or print stack not print string print stack so it will print the entire stack for me and the way you can do that you can use enhanced for Loop here which is int n in Array and we can

print all the values so we can say without Len I want to print all the values we can print n and I can give a space in between and at the end I will print the new line so That it will come on the new line after printing okay so here I cannot say nums I I can say nums do print okay let's see if this works we have added two values 10 and 30 and then I'm trying to say print stack let's run this code and you can see it is printing only one value

which is 30 not the other values why the reason is every time you say push don't you think you're pushing at the same location zero it should change right so the first value should Go at the first location the second value should go second location so how do we know where to push so we can use something called top here so every time you basically push a value we have to increment the value of top but also there's one more problem the top value is minus one that means we need to do the increment before

we do we assign the value so once you do this the Top Value which is by default minus one will go to zero and then you are assigning it here Next time when you do that when you insert 30 here what it will do is it will again increment the value of top which is zero which will become one and then you're inserting at the second location let's see if this works and yes it works you can see we got 10 30 or we can have some more values here in fact I can just uncomment

this section and maybe add two more values or maybe let's try one more value let's say this is uh 50 with 50 it also works we can see we Got all this values I can have one more here and let's say this is uh 90 and the moment I do that you can see we will get an error which is a array index out of bound exception so this this is not what we wanted right uh basically this this is going uh out of the box because we only have five values we're inserting six values

not good so that means when you are pushing data we have to also check if the stack is full how do we do that so here we can actually check if so Before doing all the operation we can check if the size of the stack now how do we know the size of the stack I mean the values which have inserted we know the size but the values inserted will be stored in top so we can simply check with top if top is greater than equal to size we should not be doing this or we

should do this only when the top is less than the size then it makes sense right so this two section should be a part of this a condition now I think there's no Issue let's run this okay we still have an issue that means we are not okay because we are incrementing this should be outside because how it will check if it is not incrementing and since we only have one statement we can remove this cly brackets let's try and yeah it worked you can see the last element which you have added is not inserted

but also you can do one more thing here in the else part you can Check or maybe you can print stack Overflow okay the famous website run and you can see just printing stack Overflow for the last element okay so you can see now we are getting stack Overflow okay so that means uh this is working so push is working what about pop and Peak let's see that so we are done with push now it's time for pop and Peak so let's write a method for push let's say at this point I want to say

pop so that when you p the last element so in total What do you think when I say pop here and if it works how many elements will be getting added of course we'll add six elements but then ultimately you'll be having five is because after pushing 10 and 30 so basically at this point you are removing 30 right the last element then you only have 10 and then you inserting four so in total you'll be having five how we are going to implement pop so thing to remember when you say pop it returns a

value right so I have to say public int pop we don't have to pass any parameter we just have to implement now now we have to return something right now what we have to return remember when you talk about the stack there is one variable which is pointing to the last element and that is your top so if you can simply get the value from the array of top your job is done don't you think okay so this is how it works you can simply return the pop and when you run this code and we

are Printing pop as well let's run this and you can see it is printing 30 so that's right we are getting the value what it is not doing is removing the element because see in the output 30 is still there so that means we have to remove as well so how do we remove so one we can do one thing we can say minus minus what it will do is it will return the value of top and then it will decrement this is post decrement right so post decrement means it will give you the Value

first then it will decrement and let's see if that works run and yes it worked you can see it is giving you 30 that's the right output but in the entire stack we don't have 30 now so pop is working don't you think the same thing can be done in push as well so instead of incrementing it here what if you increment here I think that should work let's run and yeah push is still working so we can also we can also reduce one line here now here we have to Do pre uh increment is

because first we have incrementing then we are assigning a value so this this was pop now since we have worked with pop we can also work with Peak here so here if I say it's Peak the only thing you have to do is don't remove the value okay so now if I at any given point let's say at this point if I say system.out.print nums dop PE it will basically give the value but it will not remove that value so you can see the Value it is giving you is 20 it is not removing 20

so that's a main difference between pop and Peak you can do some more things here example we are checking for the size here we still have something to do with pop so let me just talk about that but you can modify this and you can create another method called is full is empty that also makes sense because then you don't have to compare in this you can simply say is full then you don't do this otherwise You can do this so you can have another method okay so now why I'm saying that this pop is

not complete let me show you something what if I just uncomment everything and here now since we don't have any value what if I say nums do pop what will happen is it will give you an error it is again saying in this out of bound exception because by default the top is minus one okay so we don't want to do that so when should we return so what you can do is if the top is more Than minus1 then only return otherwise don't return that's what we're going to say but then we cannot put

return inside if I can simply say return here as well let's return with some value say zero okay what if it is the stack is empty in that case I can print stack underflow so at this point it should print stack underflow so one you can see there's no problem it is printing stack underlow okay that's how we can we can add this again if you can simplify this you can Also use is empty method that should also work so this is all about stack in Java in this video video we'll talk about Q the

thing is we have talked about stack right which is last in first out but what if you don't want to do that you don't want to do last in first out because in the real world when you go to shopping when you have a checkout counter basically the first person who goes there is the first person to go out right you don't want to have stack in That situation and that's where we also have a word called Q in English so we use a concept called Q there which simply means that it will not follow

last and first out it will follow first in first out something like this so let's say you got an array here and this array has multiple values let's say four values in this case so 1 2 3 4 and then if you want to insert some value basically it will go from one end and it will come out from the other end so what I want is let's say I have different values here which is 5 8 two and three so let's say I have these four values which I want to insert so basically it

will go from one and it will come out from the other end so we can say this is my front and this is my RAR so basically the values will get inside from the rare So example if I want to insert five five will come from here but then it will check where we can place it basically it will always try to place at the other End so five basically goes here what about the next value so eight comes and eight goes here two comes and two goes here and three comes and three goes here

it makes sense right of course that's how we will P the value what makes this different from stack is first in first out basically which is the first value which which we have entered of course five right now if I want to remove the value or take out the value which which should be the first one it is your five So five will come out from here so first in first out so this is how basically Q works okay but there are certain terms which you have to remember so when you say you are inserting

the data we normally call that as NQ so NQ means you are inserting data then we have a word called DQ DQ means removing the data so example whenever you insert the value that's your NQ whenever you remove the value that's your DQ so what happens in DQ is the first element basically comes Out so the first element comes out that's your DQ and when you insert the next value that is your NQ but then the problem is the size of this Q of course we can Implement that with multiple things you can use array

or link list but let's say if you have if you're using array the size of this is four right which means you cannot insert another value so let's say someone says Hey I want to insert one more value which is let's say nine now you cannot Insert nine there because we don't have a space but logically we do have a space right we have a space at the start but unfortunately we can only insert from the rare end now that's one of the tricky Point how do you do that so one solution could be move

all the elements you know move eight on this side two on this side and three on this side so you can have a space there but don't you think that will consume a lot of computation because shifting values is a Timec consuming process but yeah that's a problem we are trying to face and let's try to solve that uh in some time but important thing is there's a concept of NQ which is inserting DQ is removing the elements so let's say we have removed five now five is gone now again when I say DQ on

this Q what happens is it will go for the next element so the first element from that Q so eight will come out now remaining is only two and three so basically every time you say DQ You are reducing the size of your Q every time you say NQ you are increasing the size of your Q now apart from these two methods we can also use something called uh a peak now we have talked about Peak before so Peak what it does is it gives you the value but it will not remove the value from

the from the Q so example let's say if I want to do Peak now on this particular Q it will give you two which is the value here but it will not remove the value so Difference between DQ and Peak is both will give you the value but DQ will remove the value and Peak will just give you the value okay not remove it okay let's get back this value inside because I want to use them so let's get five and 8 so let's say we have a scenario where you have all the four values

how you're going to implement this how you're going to implement Q so what we do is we take two variables we have already used those two variables we have front and we have Rare So basically every time you insert the value you increase your rare value which means initially the value of rare will not be at the end so so how do we implement this let's take a example here so let's say again I want to insert the same values which is 5 8 2 and 3 so I want to insert this values so what

you do is you take a q basically this is your Q here which will have four values let me create box and let's insert the values here but before inserting we have To take those variables right so the four two variables we have is we have front and we have rare the value for them by default the front will make it zero and rare will minus one so that means rare is basically pointing somewhere here and front is here in fact do just to simplify this I will not be using rare or front I will

be using R and F so R will be here and F will be here right now when you insert the first value so let's say if you want to insert Five now five basically comes here we got the value five now what you do is you move your rare here okay and then let's say you want to insert eight so eight goes here but don't you think even before you insert five you should move your rare So what I meant to say is we try to make sense but then before even before you insert five

because we have no idea from where to put this so what you do is you basically move your rare here first and then you know okay whever You have R basically you put your value there so five goes here then when you want to insert eight again you move your R next let's put it here and then you say okay eight goes here now again when you want to insert two you basically move your rare once again here so whenever you want to insert value you move your rare there so basically you have to just

increment rare every time you insert the value okay this makes sense right but what about the front now Basically when you say front it will be used for deqing so let's say now we when you're deqing it how will you do it so when you say DQ basically first you will remove the value and then you have to make sure that you move your front here why we have to move is because now eight is the first element right so which one to remove is done with the help of front where to insert that will

be handled by the rare now do you want to move rare first before I mean that depends upon Your implementation we need one more variable here which is called size so to know where we are okay okay now there's one problem as I mentioned let's say if I want to insert three so three will come here no problem but let's say after that if I want to insert nine where will nine go we do have a space here at the start we can insert nine here but then don't you think till this point when you

inserted your three your R is here how will you make sure that R goes back here The only way you can do that because see okay first of all why we cannot do that because we are using index number right we have 1 2 three these are the index numbers we have so every time you can increment you can say from 1 2 2 3 but we cannot say 3 to0 again but if you can do that the problem will be solved so what I want is after R goes to three maybe I just want

to make sure that this comes back here okay and the way you can do that provided youed to know that There's a box empty here that can be handled with the size variable this will solve that problem but if you can move this if you can come back from 3 to zero don't you think that is we are going in in a circle and that's why there's one special type of Q which is called uh circular Q now what is circular Q uh again the same we have done before so R moves basically from the

last element to the first element and if you want to imagine this uh maybe you can imagine a Circle so you can say we have two Circle here and we have four values okay so we got four values now so basically what we will do is let's have a index number here so this is index zero index one index 2 and index 3 same index which we have used for the array on the top and now when you want to insert basically we we need those variables right the rare and the front so what we

can do is I can make this as front and this is rare both are pointing to the same value now so Let's say okay actually I'm pointing to the wrong point so this variable basically should Point here so this is your front and this is your rear right and now when you want to insert the value the first value will insert is at the rear so let's say we have uh five here and then uh let's say again you're inserting 8 3 and then now let's say you have also inserted one I think those are

the values doesn't matter actually two or Three but let's say we have this value here and now when I say DQ now from where you will remove the value so you will remove the value from okay so when you're inserting all the value you have to make sure one more thing your rare goes here when you inserted all the values and now when you say you want to DQ basically what we can do is we can remove this particular five value from here that goes out now this is empty right and of course you will

move your Front to the next location front is here ignore this Arrow I can't change the location of it doesn't matter so your front is here but then we have an empty space here so we just have to make this circular so when you insert a new value which is nine your rare goes here and that's how we can achieve a circular Que Now basically to do this of course if you want to increment the value of rare we can do that right so we can say rare + one it will increment the value but

if You want to go in circle what we can do is we can use something called mod of five oh sorry mod of size of your AR which is four so we can say mod of four now what it will do is let's say your red value is usally zero so we know that 0 mod 4 is 0 mod is basically remainder 1 mod 4 is 1 2 mod 4 is 2 and then let me just write it here 3 mod 4 is 3 4 mod four is zero so after three it will come back

to zero that's how we can perform this thing we can use this thing to Achieve that you know the circular thing now how we are going to do in the code that we'll see in the next video but point to remember Q is first in first out and it is getting used in most of the places example let's say if you want to schedule a task so which task should happen first you know you maintain that to-do list so the first T you mention that should be the first one to complete but there's multiple types

as well for the queue there's one more thing called Priority que where even if you mention the task in sequence you can mention the priority for it so the highest priority element or the task will be the first to pick it up but then we'll not be talking about priority Q let's say we have a simple Q and A circular Q so now let's try to implement Q in Java now basically we do have the inbuild interface of Q we not be using that we can directly create a q class for us and let's say

this is Q equal to New Q but as you can see we Don't have the class so what we can do is we can just go back here and say more action I want to create my own class called Q in the same package which should go somewhere here okay so this is your main method and on the hand side you can see we have a Q so in Q basically what we can do so we want to insert value we want to delete value so let's try with inserting first so with the help of

Q I should be able to add values so let's say I want to NQ a value So of course we can use add or other methods but let's stick to the convention so we have NQ NQ basically means inserting the value let's I want to insert 10 but as you can see it's not working the reason we don't have that method so let's create that so I will say public void and Q and it should take a parameter so I will say int data and that's how we inserting it so let's see how do we

Define this now we know that whenever you work with the Q we need to Use certain variables we have talked about that in theory as well so the first variable we need here is let's say private int front that's what we need and then private in rare that's the variable we need and also we need to know uh the current size of the array or the que so I will say size and of course the array itself so I will say private in Array uh this should be an array so I will say specify type

as aray so we got four variables and let's try to use it Initially the value of front which I want is zero I mean there different ways of defining this values we can also use Constructor but let me just do that here itself size by default will be zero because that's a size default size is zero and then I want to create the array of size let's say four so the size maximum size I have four and yeah let's try to use it now so every time you want to insert data the only thing you

will do is you will insert data in the que Right so you will say I mean the array so you will say array okay what should be the uh variable so should I insert at the zero yes we can do that so I can whatever data I receive I will insert that at zero position but don't you think every time I add a new value it will go to the same location so this is not a correct way I will use a variable called rare So Rare will Define where to insert data okay because you

insert data from the rare end but initially rail Will be at minus one we don't want it we want to insert at the zero location so before you do that before you assign the value you will simply say rare Plus+ our job is done okay and let's see if that works even if it works how will how will we know so what we will do is let me also create a method called print all values so I will say private or maybe I can say public void show it should print all the values nothing much

not an ideal way of uh Printing the size but let's say let's do that so I will say int n from array I want to print but not here on the same line basically so I will just print the value and give a space and at the end I want a new line so I will do that and from this let me print or not this I want to call the show method so it's a q do show it will print all the values right click and run and you can see we got 10 0

0 0 this is 0 0 because the size of this array is four so basically It will print all the values so maybe this is not a correct way of doing this what if you can use int I I will start with zero and I less than size okay so basically we want to print till the size of the q and then I will say I ++ okay and then I'm going to print a r r of I so what it will do is it will only print those Elements which are there in the list

if I run this code it's printing nothing reason when you inserted the data in the que don't you think we have To also increment the size so now initially before running the NQ the size of this Q is zero but then when you insert the value we got a new element which is one I mean we've got one element which is 10 and now if done this you will only see one element yes if you do this two times now let's try to do NQ again with a different value let's say 20 in this case

now what will happen is it will print two values so even if your array size is four the Q in that array Is still two so the size of the Q is two so that's how we can basically use the NQ but what about DQ let's try to do that so what I will do is I will say public void okay the DQ will not be wi DQ will be int because you are getting the value as well so I will say DQ of int okay when you say DQ you don't specify the value you

just get the first element right now question arise how will what you will return it's very simple actually what you return is the Value from the array but the variable will be front which will be referring it our job is done we are returning the front and if you want to see that what we can do is we can print by saying Q DQ so DQ will give you the value the first value from this uh Q now if you run this you will see it is printing 10 reason because that's the first value we

have inserted but also when you say DQ don't you think we have to remove this 20 or remove this 10 sorry so the output of This show should be only 20 it's not working okay reason we have not done that code in DQ So when you say you want to reduce it so how do we reduce it it's very simple you simply say front Plus+ now when you do front Plus+ what we are doing is when you have this array let me just draw that here so this is your basically a queue which you have

created uh with four values and in fact four I mean the is size is four but by default the Q size is zero but when when you Insert 10 the Q size becomes one when you insert 20 the the Q size becomes two now what we doing is here at this point we are saying DQ which means we have to take this 10 out so if you take this 10 out the size should be only 20 I size should be only one the value should be 20 how do we remove this 10 see initially the

front was here right front was here what if instead of removing the value just move your front if you do that your job is done right and so That's what we're doing we are saying front Plus+ but then where should we do it should we do front Plus+ before of course it should be after this right uh but then there will be a confusion so what we can do is we can take a temporary variable called data and in this data you store your value first so you simply say cut and paste so you store

your value in data then you front Plus+ and return data not the array or the add element because the add element Is stored inside data then you do front Plus+ so that you will get data now if you're on this code you can see 10 is here okay but there's one problem it is printing 10 as well actually in Q we only have one but still it is printing 10 as well reason we are printing all the values of the array it should not start with zero should start with front then it will make sense

right so run and you can see we only got 20 so this 10 is actually DQ printing so this DQ is Printing 10 this 20 is actually printed because of the Q let me insert some more values here then it will make much more sense uh let's say I'm inserting five and 99 so we got four values now and when you say run this you got four values but now when you set DQ it will remove the first value which is 10 remaining value is 25 and 9 so that's how basically it works right so

we are able to DQ as well but the problem is what happens when you do NQ not four Times or maybe something like this uh you are inserting four values and then you are saying DQ after DQ how many elements are there in the que only three right uh you can see here but then that also means that if I do NQ once again after doing the DQ let's say the element which I'm adding here is 12 it should work right it should print 25 and 9 99 and 12 but it's not working it it

has given you the error which is array index out of bounds exception that means we Have not implemented the circular Q so let's try to solve this problem of AR index out of bounds exception so why we are getting this because even if your size of your Q is less than the size of the array it is still giving you that problem right so we have inserted four values that's right but then we have also done the DQ So when you say DQ the size of the Q is only three now I should be able

to add this and it can only be added in the circular way right so it Should be added at the end how will you do that so what we can do is when you're doing the NQ instead of using r++ we can say rare is equal to rare + one but you will say that's the same thing right but by doing this what we can also do is we can do a more operation remember in the theory we have talked about if I do a more of four our job will be done I think let's

try let me just rerun this and okay now again we got the problem but this time I think the problem is With the show because in show we are not doing the mod operation so what I will do is I will start from front I can't go to sizes because size is higher now when I do DQ I to also decrease the size right so let's run and this is actually not a good way of printing it will not print the way we should be getting the output but at least we will get the output

okay we are adding 12 it's going one less than the size Okay this is not this is not actually the right way of printing it so let's ignore the printing part at this point let's skip this show and let's run this so now you can see there's no problem it is working basically I can do DQ multiple times now let me just do the DQ here so after inserting these four values when you when you say DQ the 10 goes right but then we have 25 99 and 12 let's try to do DQ here so

then we will know what are the elements we have so 1 2 three and four so again I'm doing DQ four times run this and we got an error okay anyway so we got 10 we got 20 because that was the first element then five then 99 and then DQ is giving a problem because what we have done is in the NQ right this thing the same thing need to be done in the front so I have to say front is equal to front + 1 and what if I just mod it by four again

I'm using a harded values because I know the size of the array but if you want to Make it Dynamic if you want this value to be changed maybe you can just take one more variable called Max size and we can put it here okay let's see if this works restart or rerun and now it is working we can see we were able to add the values and we were able to delete the values yeah so let me just make it floating so that I can see the all the outputs yeah so you can see

we got 10 20 5 99 and 12 so we were able to go into that circular way and it's it's not like When we have added 12 so it will be first once you remove 10 then 20 becomes the first element and we'll able to do that here we can actually use two more methods here for full and empty uh if you want to check if if your Q is full or it is empty so I can create a bull bullion method or the method which returns a bullan value I will say is full is

it full let's check how do you know if it is full or not it's very simple if your size is equal to equal to Four it is full right uh and how do you know if it is uh empty in fact you know why we should use this method let me show you something what if I want to add one more value here so I'm inserting five six times and removing only once it should give a problem but unfortunately if I rerun this look at this it's not working the way I want it okay let's

have a different value because it is giving 12 12 two times let's rerun and you can see this is not what expected Where is 20 20 just went off so we have some bugs here so don't you think this should not work 32 should not be added because the Q was full so we can implement this method is full and before you do this NQ we can check if is full in fact in fact it is if it is not full then do this otherwise don't do this things else if you want to do something

you can throw the exception or you can print if you want U maybe you can say Q is full okay okay so now what will Happen with this is if you run this now it will not add the last value you can see it says Q is full so you cannot add 32 and that's why you only the only elements you have is 25 99 and 12 the same thing should be done for DQ what if your array itself is empty now let's say if I want to DQ once again here it should give you

a problem you can see it will okay it's not doing anything it's just that it's printing 20 again I don't want to do that I want to say DQ the Q Is empty so what we can do is we can have one more method here which is public Boolean is empty we can check if the size is equal to zero that means is empty and then that means before doing the DQ part we can check if it's not empty then only you have to do this part and I should return this data I will take

the data variable outside there's one more way you can do that instead of sending dummy data because if I do this it will send dummy data what I can also Do is if it is empty I can simply throw an exception or maybe you can also print something but throwing exception will also make sure that it will stop the execution right so I print Q is empty okay let me just move it down so Q is empty now if you done this it will give you an error but error which we have created and it

says Q is empty yeah that's how basically we can do this we can also use the exception part here for the Q is full if you want again that's The way we can Implement one more you can also use something called Peak but Peak matches with DQ so let me write it here now in Peak what you do is you only return the value but you don't decrement the value or increment the front value so what you will do is you will have the same code here the difference is you don't remove the size and

you don't do Plus+ this is not there it's just that get the data and return in fact you're not performing the operation you can Simply write the array here so that you can can reduce one line of code and since in the if condition we have only one statement we can remove that codly brackets this code looks shorter so that's how we can use Peak let's see if I if I can use Peak here so I maybe I want to print Peak Plus Q dot Peak and let's see if this works run and yeah Peak

was 20 so yeah it is not removing the value but it gives you the value so this is your Q so the logic which we Have implemented here is actually circular Q okay so that's it from Q I hope you enjoyed this entire uh Q concept see you in the next Topic in this video we'll talk about three data structure the thing is we have talked about linklist right and now we know that how do you connect different nodes so basically node is somewhere you will put your data and also it will have a reference

for the next element so basically you can create a link l Something like this so this is a linear structure right is because we have everything in one line I mean of course you can change the shape of it but ultimately it will be a line right right referring to the next point the other type we have is hierarchical structure now basically there's a concept of tree I mean something like a real life tree which we have so in this you have a root you have a branch and you have Leaf right or leaves so

we can do the same Thing in data structure so basically what we have is concept of tree so what we do is we basically create different nodes or nodes with tree structure so something like this we have a node here let's say this is node a and then this particular node will have sub nodes or we can say child nodes so here we can have another node here we can have another node again a node and even this can have different nodes one or many or zero doesn't matter so this is how tree Structure looks

like so you can have values as well so let's say instead of a I have value which is 5 6 8 2 1 8 again and three now this is a tree structure okay so it is not linear it is hierarchical because we are getting hierarchy here to understand this mode first we have to understand uh different terms which we're going to use so if you see here we have different terms which you have to remember the first term here is node so what exactly node is so every Element or a part where you save

data these are your nodes okay and the same thing we have done in linklist as well next we have something called root now every tree in real life also we have a root so in this structure the node which is on the top level is your root node so we have one more concept or two more Concepts here which is parent and child so example we have a node here now this B is actually a child of a okay same goes for c c is also child of a and of Course by doing this we

are saying a is a parent I mean it's almost similar to your family tree which you create we have grandparents then we have our parents and then the Le goes on right so same goes here we have a parent and then we have a child here so every node will have a parent of course and a node can have a child as well again it's not compulsory but a node can have a child so if you talk about B the parent of B is a but what about a where's a parent For a so there's

no parent for a right so the nodes which has no parent that becomes your root node because that's where this thing starts so that's a root next we have is Edge what is Edge so a line which connects your parent and a child is your Edge so this line here is Edge so we have talked about node node is something where you save data root is the topmost parent node we have Edge which connects different nodes we have talked about parent and child as well Which is a is a parent node here because it has

two nodes here B and C which are child nodes then we have something called a leaf node now what is leaf node a child node which will be only child it's not a parent example if you talk about B here B is child of course of a but it's also a parent of d and e right if you talk about D here D is is not having any child right so there's no child here so this is called a leaf node now this is not the only Leaf node we Have so we got d e

g these are your Leaf nodes next we have a concept of depth so what is depth so let's say if you talk about any particular node so let's let's talk about e here now to reach E from the root node how many edges we have to pass okay so example if you want to reach e basically from a we have to go to B from B we have to go to E so we have to do two passing so we have different levels here okay so the root node is at zero level then B becomes

one And B becomes two okay so that's your depth so depth for this e node is two next we have is height so now when we talk about height we're talking about the the height of a tree okay so what's the height of this tree so we have to go till the last Leaf node which has the highest depth example if you talk about this D the depth for D is two right so from a to b b to D what about G here so for G it is from a to c which is so

this is depth 0 1 2 and three so the height Of this tree is three so we have to go till the highest depth of a node in the entire tree which is three in this case so that's your height what about the sub tree so we have a concept of sub tree now of course this entire is one tree right so the root of this entire tree is a but then we can also have sub trees example if you talk about a we have uh two child notes right we have B B and C

so let's say let's talk about B here now if you consider this as your Tree of course right this is a sub tree now in this sub tree if you're focusing only on this sub tree B becomes your root node okay so B here is a root node and then these are your child of course so when you look at the entire tree of course a is a root node but if we talk about this tree sub tree which is B is a root node if you talk about this sub tree C is a root

node if you talk about this sub Tree f is a root node so basically if you create sub trees or if You consider sub trees then we have a different root node compared to the entire tree okay so those are the terms which we have to remember now if You observe one more thing here when you look at this tree so maximum number of child nodes we have for each node is only two so it's either zero one or two so when you have a tree something like this where you only have mag maximum two

child nodes for each node we call this type of tree as a binary tree so it's a Type of tree where the maximum number of elements or maximum number of child nodes for a particular node is two so of course a child can be zero one or two example if you talk about this a the number of child nodes it has is B and C which have which are two if we talk about F we only have one child node even for C we have only one child node but if we talk about for d

and e they don't have any child nodes here even G so still it's a Binet Tre because the Maximum number of child nodes we have is only two so basically when you talk about binary tree there are different types of it and one type which we're going to talk about which is called a binary search tree because the example which we're going to code is based on this okay let's talk about the binary search tree the thing is when you want to search a particular element from the entire tree it is better if you can

save that in a ban search tree now how it is Different from ban banet tree the thing is in banet tree there's one thing we have discussed which is every node will have maximum two childes right but in banet search tree we have the same thing but additional condition is in this tree the left sub tree will have the values less than the root node and on the right sub tree you'll be having the values greater than the root node something like this so let's say if I want to draw a tree here so let's

say we have five And then on the left hand side we can have a smaller value right hand side we can have a bigger value let's say we have five again U let's say we have a new value which is three and then we can have six and then eight now this is a binary tree but it's also a binary search tree okay so this is how this is how it looks like so the the left sub tree here as you can see here this values are smaller than the root node and right sub tree

the values are bigger Than the root node but if you consider a sub tree itself then again if you can see the left side sub threee of this which is six is smaller than the 7even and 8 is greater than the seven so let's try to understand this more by drawing something or by taking some values okay so let's say we have value something like this we have 8 7 12 15 2 and five so let's say we have this values and I want to store this in a three structure so how will we do

it initially we'll Start with the uh root node now we are going for H so let's start with eight here so8 becomes a root node the next is seven now 7 is less than 8 or greater than 8 it is less than right so s goes on this side so 7 goes here okay what about 12 now a 12 is greater than 8 so 12 will go here next element 15 15 is greater than 8 let's go on right hand side 15 is also greater than 12 so again it will go on the right hand

side of 12 which is 15 will come here next we have Two so two is less than 8 let's go to S two is also less than 7 so we can put two here next we have is five so five is less than 8 let's go on seven five is also less than 7 let's go to two and five is greater than two so five goes on the right hand side okay so when you have the element greater than the particular element so if we talk about two it goes on the right hand side so

this is how you draw a binary search tree but the question is how you're Going to write a code for this so let's implement the binary search tree in Java now the thing is we have talked about different data structure one of it is link list so in link list we have something called nodes right so we connect different nodes and each node will be having data and a reference for the next element now in the same way in three what we have is we have a node of course and then each node will have

two child nodes now when you talk about tree You know sometime it is difficult to imagine how will you code in Java do we have something like one root and multiple elements to it now first of all we don't have any Java syntax which will create a tree there might be some external classes but then internally we know that you can create a variable or object but how will you create a tree structure now to break it down if you try to understand this every node so if you talk about this particular node here Yes

that's a root node so do we have anything special about root node not exactly so root node is also a node the difference is the root node is not having any parent right so that's one thing we have to remember next when you want to imagine tree don't imagine the entire tree in one go imagine root node and root node has two child nodes that's it your job is done here so as for the root node the root node job is done by saying hey I got two child nodes I don't Know what is there

after it then if we talk about the left node of or left child node of a root node it has one more node and that's it you know we don't have to worry about five or seven seven only concerned about two then on on the this side 12 is only concerned about 15 and then two is concerned about five that's it so we have to focus on one node at a time and each node maximum they can have two child nodes our job is done so what happens to those nodes Which don't have any child

in that case both of this are null in this case to we have only one child node on the right hand side what what about the left one this is empty this is null right and that's how if you can implement this thing if you can only imagine about one node at a time your job is done so that means uh if I want to code that first of all we need for sure we need a class called node right in fact I will not writing this here let me just remove it What I want

is I want from my main method basically I want to create a binary tree there are some in classes but we're not going to use it so let's say binary tree and we'll call this as a tree equal to new binary tree so we want to build a Bano tree okay you can see we have some inbuild methods we don't want to use them so let's use a Bano tree we don't have this class yet so what I will do is I will just go back here and you can see is importing this package we

Don't want any inbu things so if I go back here and if I say hey I give me suggestions more actions I want to create this class but the same package and you can see we got it I will just move this on this side I don't want to see the project structure so you can see on left hand side we have a main on right hand side we have a binary tree so basically in this binary tree I want to do all those stuff now when I say I want to do stuff basically we

have to say Tree dot I want to insert value in this tree so I can say insert and I can pass the value let's say 10 I don't know what values I'm passing here or maybe I can I can follow the same value which we have in our notes so we have 8 7 12 15 2 and 5 let's add that okay but unfortunately we don't have this insert okay so what we need to do is we need to create this method called insert inside this B tree and you can see we got insert method

okay but when you say insert that means We have to make sure that you're inserting a node of course you're passing data here but it should be added to a node right and we don't have a node implementation yet so I can create a node implementation by saying class node now what every node will have now if you go back to link list a node will have two things the data and the next value now in terms of this node here which is a Tre node it will have three things data the left node and

the right node so I can say int data then we have to say uh node because when you say right node left node they are itself nodes right let's first write left and then right so yeah so we got data we got left node and we can we got right node I think the only problem is in some of the class I think in linklist we already have a node here that's the problem so what I will do is let me just move banet tree and this main to some other package I I will just

move B with our package let's say Package com. telescope. Tre so sometimes you have to solve the problems in a go need to import the package from here now importing done okay so problem solve the problem was I was having two classes with the same name in the same package I just moved it to different package okay so now uh you don't have to do that if you're just writing the binary code you can just skip this line anyway so we got a node and then we are referring to left node and right node so

that's node done But also what I want to do is maybe when I create a node I will I want to have a Constructor here which will take the data from me and I will assign that data so I can say this do data to data and that's it so we are basically done with the node concept but how will you implement this tree so every time you want to insert the data in a tree how will you do it so if you say this is a tree of course we don't let's say we don't

have a tree here and let's go with The same value I don't know what values we have I can just use this copy okay so we got this value so if I want to draw a tree so let's say someone is giving you the value eight initially so what you do is you create a root node now we know that we don't have a node in the tree so basically the tree is empty in that case you will make this as a root node okay so how do we do that so when you say insert

basically we have to create a root node that means every tree need to Know about only one thing which is a root node right as I mentioned before for a tree the most important thing is root and then tree don't have to worry about other nodes the root node will take care of the next two nodes so what I can do is I can say node root and then every time I create insert and then imagine IM that this is a first time so what you will do is you will create your root node here

so you can simply say root is equal to new node that's how you Create a node just create the object and pass the data and that's it you got your root node in fact you know instead of using this variable as I it should be data it will make much more sense so now if you can see our code this is the thing we have done so we created a root node called 8 and that's your root node which looks good but then what about if I insert one more data here so if I say

three insert I want to insert the next record what's the next record is is Seven so when I insert seven where the seven should go now don't you think the seven should go on this side is because we are implementing B search three 7 is less than eight so it should be on the left hand side so when I say seven it should create a new node and we are doing it you can see every time you say insert it creates a new node but don't you think this time is not a root node it's

a left node of the root node how will you do that and how do we even know That this is not a root node so in that case we need to do is we need to check if the root is null then you create a new node I mean then you create a root node otherwise you don't create root node every time so root node will be created only once if the root is null what else if it is not null then we can check for something else now see if you talk about eight yes

this satisfies is because root is null till this point when you before executing eight but when You insert seven we already have a root node right then we have to go for if Els now the question is now we know that this is not a root root node we have to either go for left or right so what you do is you basically check for data if the data is less than root. data then you go on the left hand side so when you say you go for left hand side what what you simply do

is you say root. left. daa is equal to data that's what you do but then we have one little problem here Because see this will work for this data okay so we will get new new uh thing but we not even creating a new node okay so the problem is we need to modify this to something else why something else let's say we have adding one more which is 12 goes here and then you add 15 now by our logic if the value is greater than root node just add it to the right hand side

but to is already there right then we have to move to 12 and it becomes a right hand side of 12 that means we have To jump from root to the next element and then the next element oh that's a recursive process now so that means we have to add a recursion here that's one thing second problem is every time you insert data we need to get a hold on root you know writing the logic here is not efficient way what we should be doing is create another method which is called let's say insert Rec

and we'll say this will take two things because when you want to do recursion we have to Get a hold on root element or root node so that means we cannot do that in this insert because the moment use a recursion every time you call the method we need to get the hold on the Node where you're calling this so this will not work but that doesn't means we have to remove this I will tell you in sometime why y so basically we have to say node root comma data and here okay this should return

on node because we're going for recursion so it should return Something and now here instead of doing all this logic this logic should be a part of this not this so here we can simply say root is equal to insert record so every time you call insert it will call insert Rec in which you're passing the root node and the data so when you say recursion it will go into recursion we will be using recurs on insert Rec not on insert so we have to change some logic here so this is correct when you say

root I'm only Concerned about this part so how do we implement this one so when I say I want to add element on the left hand side so if you have let's say two now we know that two should go here but then we have to jump from 8 to 7 7 to two that's a recursive recursive process right so what you will do is let me uncommon this now this is not how you do it so basically you say root. left and then you call the function once again by passing the root dot left

because now we We need to followall the tree right as I mentioned before when you talk about the sub trees if it is not eight left then we have to consider this sub tree now this seven becomes your root so how will you send this as a root so you have to say root do left now this becomes a new root so when you call this function which is insert Rec here this becomes your new root and then you have to pass data as well so you're passing data but what if this is not smaller

then you Have to go on the right hand side so we have to say root. data if data is greater than root. data then you do the same thing but for the right hand side so we will say paste here so this should be right and this should be right and then at the end you know your root node so just return root that's it so this is the recursion call which we are getting here so that's how basically you create a tree now this is tree is created but how will we know That this

tree is created we want to print also right and the way you can print it is is like this so if you want to print this tree so let's say we have this tree here and this tree is created by the way we have defined this example here how will you print this now to print we basically have to Travers or we have to travel to different elements here the way you do that is we have different travel cell for tree so when you talk about tree travel cell uh we Have to follow certain things

first there are three three options here we have inorder traversal we have pre-order traversal and we have post order the difference between these three is the way you print your root node okay so when you talk about in order basically what you do is you first go to the left then you go to the root then you go to the right so which is 7 8 12 when you talk about pre-order here you first go to root Which is eight so it will print eight then seven which is left and then 12 which is right

when you talk about post it means first it will go for left then right then root which is seven 12 and 8 okay that's your post Auto ders here we are going to go for in order so in order simply means first you print the left one then you print the AL not exactly printing but you go to the left one then you go to the root node and then you go for the right one so that's your in Order now the way you can do that of course this is also recursive right uh so

in order to do that what I will do is I will create a function called public white in order then you can work here but then since we know that in order is actually or traversal is basically a recursive operation where you go to it sub tree and print it or do some operations for the recursion I will create another method which is public void is because I don't want to return Anything so I will say in order Rick so here we just want to print it now when you say print it how exactly we

are going to print how we going to travel this of course the output will not be similar to the value we have inserted it will have a different order so what it will do is first it will go for it will print the left one right so when you start from here it goes to eight but then we cannot work on the eight because that's a in order then you go to the Left one because in in order you first go for left hand side left sub tree and then from Seven also you can't print

seven because seven becomes a root node for the two so we have to go to two now we don't have any left here right this is empty so in this case you will first print two okay so you will go for two then you go for right since we don't have a left we print the root node because we are considering this sub tree now so you will print two and then you Will print five so here we have five then you go up then you print seven because we don't have anything so that's apparent

for two so we'll go for seven then we print on the right hand side we don't have anything right hand side right so this is empty then you go up you print eight then you go for the right hand side right hand side is 12 on 12 left we don't have anything so it will not print anything but you can print 12 and then you can go for right Hand side which is 15 and if You observe you got a sorted values so that's why we use BST which is sorted values easier to search as

well okay this is the in order traversal okay so let's implement this so how do we do it so first we'll start from the left hand side but also we want to verify if the tree is empty if the tree is empty how will you print something how will you travel and how do you know if the tree tree is empty by using the root element so we can simply Check if root but how do you know the root because root will keep changing depend on Tre right uh so we have to also accept root

here so we'll say node is root and then you check if the root is not equal to null then only you do it now how will you do it now first of all this is a recursive function right so basically you have to call itself so we'll say in order re and then you have to start from the left hand side so always start from left and then keep Going till you find the last left element okay and then once you do that then you have to go for the middle one middle one is root

itself which we got here right so we can print this value here so I will say print and if You observe for every node for every sub there is always a root node If You observe observe for eight S is Left Right but don't you think seven in this sub tree is a root node so that's a root we are printing when you go to two two Becomes a root node right when you go five five becomes a root node for their child which we don't have then we can so we can print data here

so we can say root do data and then we can print a space in between as well just to differentiate the values and also I can skip the new line now once you have done with the root element of course not just printing you can do some other operations as well maybe you can add all the values if you want and then here I Can say in order but this time you will go for root. WR that's it this is how basically you print the values but from in order we have to call in order

Rec by passing The Root node so you will call this only once in order so that means I can simply create a tree by adding values here first of all now what values we have let me just do that quickly okay so you can see we have added all the values and now it's time for traversal so I will just print in order and it Should do the job for us let's try so I will just run this and you can see we got the values we got 2 5 7 8 12 and 15 that's

what expected it is printing in order but let's say if you want to do Post order so what I can do is I can just change their names or maybe I can say pre-order so I can say preorder and of course everywhere you have to do that now the only change you have to make is in pre-order first you Print the root so that means this line will go up that's the only change you have to make in pre-order okay nothing much let's run this and see if this works save this code and run and

you can see this is now pre-order so root element is something which will get print first I think this is the sequence in which we have added no different sequence but anyway you got the point so this is PR order you can also do it post order let me know in the comment section If you have done that and yeah that's how you implement tree