1.2 Array Operations - Traversal, Insertion | Explanation with C Program | DSA Course

so in this video I am going to talk about various operations performed on arrays in data structure on 1d arrays specifically see I have already discussed the fundamentals of arrays what is need of Faerie array declaration in acid ization of array memory representation of air in the previous video so if you check out that video then I'll provide you the link in the description box you can check out there fine in this video we'll talk about the operations on array although there are many operations can be performed on array but basically the most important operations we are going to discuss that is traversal of array insertion in array deletion of any data from the array searching of any key if element exists or not in the array sorting of array we have already discussed searching and sorting techniques fine you can check out in the playlist in this video I am going to talk about how to traverse an array and how to insert a data in the array with their good because insertion is also of three types may be you can insert element at starting of the array at the end position of the array or at any position at any specific position in the array fine so I am going to talk about these operations traversal and insertion with their code fine see besides these operations many operations can be there like find a minimum and maximum element from the array find duplicate elements from the array reverse of an array find second largest element from the array so now first of all we'll discuss traversing of an you can say travel cell of array now what does this travel cell means traversal means visiting every element of the array exactly once fine suppose you can take one example you have five apples and you are going to point your finger at first Apple first of all then second then third and fourth and then fifth something like this you are traversing all the apples so thus in this case we are going to traverse all the elements of the array and output should be what you should print the elements of the array what whatever the elements in the array we are going to print those elements so I am going to see this with the help of a code see let us take we have this Airy array name is a the size of arrays five index would be from zero to four and these are the elements in the array how the data is to be stored because each integer is going to take four bytes in today in typical compilers so address suppose base address memory manager has allocated to the array base address that is hundreds so next next for the next integer for the next element of the array that this would be worth 100 plus four because this this one integer will take four bytes so that is one zero four one zero is something like this I have already discussed in the previous video this concept and detail fine so say now how we are going to traverse theory we are going to take one variable I started from zero now see what is there at this place six we are going to print this six now this I would be implemented I is here now now here what is the value two then two would be printed then I would be implemented then here then here now and like this the values would be printed and I would go from zero to four that is from zero to size minus one size of air is five so size minus one this is how we are going to traverse the area and you are going to write down the code for this now how we are going to write down the code first of all see I am also going to discuss how to initialize there a how we are going to take these elements and initialization would be of two types at compile time at runtime so in this food at runtime I'm going to ask from the user what elements the user wants in the area how to populate the area at runtime now see let us check so initially we don't have anything in this area so first of all what we will do we will just write header files and all I think you can write that thing now let us take I am going to declare an array of size 50 see actually when you are using the array when you are used when you are storing the integers and you can store only ten in pieces it's up to you less than 50 but you cannot store more than 60 why we are taking this 50 because see it is fixed size once you once you declare the size of ferry at compile-time you cannot change it at runtime find that is drawback of there but one another drawback is that it arrays not having any bounds checking property at runtime so it is the job of the programmer only to check to write down the code for checking the boundary of the areas in program only fine now what is that bounds checking I will discuss later so see I have declared array of size 50 now how many bytes would be allocated by the memory manager 15 to 4 that is 200 bytes so something like this if this is our memory so now see in the memory in the memory how many bytes would be allocated and that is 550 into 4 because one case it will take 4 bytes that is 200 bytes so suppose the base address is 100 so 100 to $2.99 these bytes should be allocated to this array this space but here we don't have any data now we are going to take the input from the user now next thing is you can ask from the user that how many data the user want to insert in this area what is the actual size of the array this is the maximum size fine this is the maximum limit so see you can ask from the user printf inter size of Faerie print F is a function standard function that is used to print something on output screen and scanf is used to take input from the user now user will enter what suppose size is 5 I want to insert 5 elements only so here you will write percentage D because for integer the format specifiers percentage is d for float it is percentage so here you will write address off now if user will give something some input that is some integer value then obviously that value should be stored in memory and how values to be stored in memory using variable so you have to declare one another variable fine so let us suppose we have declared array and I am going to declare here the one variable name that is sighs fine and I'm going to write here address of sighs so now the compiler will see this line then what compiler will do compiler will allocate for this variable it will allocate four bytes somewhere in the memory from three zero four two three zero seven four the variable name sighs fine now this is what address of operator address of operator operator means when user wants to insert when user will insert the data then compiler should know at which address you are going to store the value so this address means this would return at 3:04 you are going to store the value so suppose user enter the size five so here you will write here what what has to be inserted five would be converted into binary form and five would be inserted so here you will insert five in these four bytes fine now we want to populate the data in this area now the size is five so you I want to and insert five venues fine now how the value is to be inserted I would be started from 0 till for L size minus one you have to take one for loop I have already discussed there so what you will write you will write what printf enter elements of array and you will write one for loop and this loop could be started I value would be started from zero I would be less than less than size less than five that is for a zero to four index would be zero to four and that is I plus plus and in for loop you will write because to take input from the user views kind of function here you will write same percentage D format specifier and address or where you are going to store the values first value would be stored at zeroth location means at this location in these four bytes one two three four these four bytes next will be stored in these four bytes so now here you write a oh I find a dress off area name is a and at which index are going to store index will be started from 0 to 1 2 3 4 this is how we are going I am going to represent it 0 1 2 3 4 each block is having these 4 bytes fine so this address is to be located now when I value is 0 I value is 0 then value would be stored at address of a of 0 address means add value hundred a of 0 of 0 means at this index fine so now user will insert the values suppose user has inserted the values 6 to 0 for n 5 because Luke would be started from I is 0 2 sizes 5 0 to 4 so that is why 0 to 4 there it would be populated now now what how that this air is to be traversed now we are going to again start a loop from here we are going to check we are going to access this element as we are going to print output should be you are going to print the array what are the elements in there you are going to print that fine so for printing you will write 1 1 for loop again for loop would be there I would be from 0 to 4 fine so you can write here printf elements in array are after printf you will write one for loop I would be started from zero I would be less than size but you can say less than equal to size minus 1 I plus plus and here within this for loop you will write good now we are going to print a diary so you will not write scanf scanf is for taking input you'll write here printf % is DS for integer because datatype isn't easy and here simply you will write array of i because in the previous video i have told you for accessing the element of dairy you simply write array name and breakers will write index so i would be 0 then a of 0 would be printed the 6 then i plus plus i is 1 then a of 1 would be printed that is 2 like this from 0 to 4 values will be printed so this is now the traversing of the n see here we are using one more variable that is i so you have to declare this variable here before that is i fine so i guess you can write the header files and you can execute this program so next we will discuss now how data is to be inserted in the air at specific position because if you get how data can be inserted at specific position then you can easily modify the code for inserting the data at the beginning and at the end of theory fine so now we will see how to insert an element at a specific position in any see I'm going to take the same example array size is 50 now first of all you how to take care of this this thing if air is full then that is overflow condition you cannot insert so in the program you have to write that condition also from 0 to 49 we have index this address will be 296 so if you have inserted all the 50 values and then you cannot insert any other value if there is not full then you can insert fine in this case we have inserted only 5 elements because the size we have taken only 5 but we have space for storing 50 elements so still you can store how many elements 45 element see one and another thing you have to pick it I have told you there is no upper bound checking concept of areas in C like this if you take hair in a is equal to 50 fine now memory man is it has has allocated to how many bytes two hundred bytes for storing 50 elements and if you write down here enters the sizeof array and you if you enter the size 51 or you can say 60 then user can insert 60 values also but that is not actually correct because initially how many bytes has been allocated the space for only storing 50 elements how you can store 60 elements so that is not a concept of bound checking in the array the programmer has to take care of this thing the programmer has to write down a code in the program only to check the upper bound limit of the array fine so here only after inserting the size you will write a line that if size is greater than this upper bound limit upper this 50 then you will print what overflow condition else you will write down that inter the elements of their and other code you will write down in the else blow fine now say I'm going to take the same example we are having only five elements fine now how to insert first of all we'll discuss with the help of an example this example then we'll write down the code fine now suppose at position here at position 3 say I'm going to take index and position different thing somewhere you find out that index is same as position somewhere it is written that at position 2 we are going to insert so index is also 2 but here I am going see here I am going to consider position is third but index is 2 because as you can see position is 1 2 & 3 fine but index is 2 so I am going to insert here so here I am considering this as the position position is equal to 3 here I am going to store the value here I want to store the value so now what you can do can you directly store a value suppose I want to store a number 10 so if I store directly here 10 then what will happen then you will lose zero and that should not be a case fine we all we want all the previous element as well as we want some extra element that you want to insert so you cannot do directly this so another approach is what you can shift these elements to the right side fine because still we have space left in the area so you can shift this this five here then this four here then this is zero here so here what you can write this five after shifting now this four would be shifted here so in the place of this wife you will write for now zero will be shifted in the place so four because four will be lost and zero is there now here also we have zero till this position where you want to insert till that position you are going to shift to the right and from variable to start the loop we are going to start the loop from here from the last element of there you can say from size minus 1 see sizes what five but index is 4 so you are going to start the loop from 4 I would be started from 4 and I would be decremented now I is equal to 3 now I is equal to 2 and F is equal to 2 then you are going to stop means you are we have found the position we have 0 4 5 here now 0 is duplicated so we can we can insert 10 here we can insert 10 here we can overwrite this 0 now so that is how we can inserted this number 10 at position 3 position 3 indexes to fine so how we are going to write down this loop see so here we are also taking more inputs from the user that is number you want to insert and at which position you want to insert the data so for storing these two values you have to declare two variables that is num and booze right so now say enter the size of their a size you have to enter then you are going to enter the elements of the array and if the size this size of that it should be less than or equal to this 50 if size is greater than 50 then you cannot insert anything extra element in there fine so now after this 10 if you will right if sighs if this size is greater than 50 this size then you will write what print overflow condition you cannot insert fine and after that in a stroke an else fluke you will write from here printf and after that you write in else blow this is how we are going to check the boundaries upper bound of theory because I have told you there is no concept of bounds checking of arrays in c so programmer has to write down the code itself for the checking of the boundaries so these two more inputs you will take from the user enter data you want to insert that as scan a percentage the address of num fine for the num also for bytes is to be allocated in the memory and enter the position at which you want to insert and for position also for bytes is to be located in the memory now now what you will do you have number also you have positional so suppose number is 10 and position is 3 now the swapping would be done fine from where from where you will start the swapping from the last element only why so because see at this position at third position you want to insert and if you say I will swap from this position only first of all I will swap this element here so if you swap 0 here then this 4 would be overwritten you will lose this value 4 and here you will insert this 0 now from where you can recover this for we cannot recover this 4 so you cannot swap star the swapping from here you have to swap from this position only fine so now you write down a for loop for swapping and we will start this for loop from where we have started from here initially we are having only 5 elements from 0 to 4 so we have started our loop from here and we have shifted this to this two ways are there you can also start our for loop here from sizes sizes five so you can start from the for loop here I is equal to size that is also fine and you can also start from here that is size minus one so here I am starting from size minus one and from where I should be greater than equal to position minus one see I will go till the value 2 and position value is 3 so 3 minus 1 that is 10 - so I should be greater than equal to 2 from here to here you are going to swap and here unite I - - now what here what we are doing we are inserting this this value previous value to I plus 1 right so have you in right here a off so here you will write a Oh 5 plus 1 is equal to ca off I would be shifted to a oh 5 plus 1 that is at starting I is equal to size minus 1 so I is equal to size is 5 size is 5 so I is equal to 4 4 is greater than equal to position minus 1 4 is greater than equal to 2 fine so a control will go here so a of I plus 1 that is a or 4 plus 1 5 is equal to a or 4 and it means this a Oh for this value will be transferred to a of 5 that's what we have done exactly fine now again I - - that as I would be 3 now a of 3 plus 1 that is 4 is equal to a of 3 now a of 3 value will be transferred to here now again you have to value will be transferred to here fine and when I becomes 2 then also fine when I becomes 1 then 1 is not greater than equal to 2 that is why we are going to not we are going to stop you are not going to swap this value fine so now after this for look what you will do you are going to insert now the data where you are going to insert a of the position - 1 C position is 3 but where we are dealing with index na so a of 3 minus 1 that is a of 2 a of 2 here you are going to insert 10 but position is still say 1 2 & 3 but indexes position minus 1 so here you are going to insert number and after inserting this number now array size becomes what 6 so now size becomes size plus plus right now finally you will print this area how you can print this area we have discussed when you were traversing there you just write down a for loop in for loop you will start from 0 to the size fine and you simply write printf percentage D and a of I and these all values would be printed this is how we are going to insert the data at specific position fine and in this case you can also write down one more condition that is you can also write down a bound on position if position is less than 0 that is in minus 1 or minus 2 then you cannot insert that is invalid position and if position is greater than the size size is 5 size is 5 so we have from 0 to 4 here so within this range you can insert position can be 1 2 3 4 & 5 all the position can be 6 here also you can insert but position can be likes 10 here you cannot insert why so because in arrays you are going to store the real time consecutive location where you can say continuous locations so it's not like you have data from 0 to 4 and you skip these positions and now you are going to insert here that is not possible in area so here you can also write down 1 if conditional position after this position here so here you can write if position is less than equal to 0 because if we take position is equal to 0 then here is you - 1 that is minus 1 that is invalid so position is less than equal to 0 or position is greater then size or size plus 1 you can say fine because size is 5 5 so here also you can insert at 6th position that is also fine but after size plus 1 you cannot insert then you will write word print if invalid position and after this F in L slope you will write this for loop and you will also going to print the array in this else also after that you are going to close the cells fine so this is how you can insert a data at any specific position you can insert it this also you can insert at the end also fine using this method but suppose you don't want to ask from the user about the position you know that you want to insert at the beginning only at the zeroth location or at the first position you don't want to ask this enter position and scanf like this and second cases you want to insert after after all the data at the end of there you don't want to ask from the user the position then how you will do you you are not supposed to write in that case these lines printf interposition and this and you have to modify this for loop a little bit fine so this this would be as it is fine this this would be as it is you are going to write this thing i am going to rub this thing and i am just going to write down this for loop this updated for new and the beginning how you will insert at the beginning of the area for inserting at the beginning you will have to you will have to shift all these data same you are going to start new from here size minus 1 and loop will go till 0 because obviously you are going to insert here so you are going to swap all this data to the right side so simply you will update this for loop like this i is equal to size minus 1 say men i should be greater than equal to 0 now you know the position so no need to do position minus 1 and I minus same you write a oh five plus one is equal to a oh I fine and here you will night work at a of zero you want to insert number and simply size plus plus no need to write position minus one because you know the that where you want to insert that a of zero three location fine and if you want to insert after the all the elements at the end of theory then what we will do then that is very simple no swapping would be done fine so now how you will insert simply you just enter the data you want to insert no need to ask the position no need to do this swapping and all fine simply will write a off here here means you can say that size a of size size is five so at index five at here at index file because if size is five then data will do from zero to four so at a of size you can insert the number and size plus plus you can do so now if we discuss the time complexity then see if you are given some position suppose position is given this one you are going to insert data here so you are going to shift all the elements to the right side so time complexity would be theta n so in best case it is one and in worst cases it is Theta N and basically time complexity the time taken depends on the position given find if position is this one one then you have to shift all the elements find that as n shift would be there if position is this one then n minus one shift then position is this one and n minus two shift like this if position is this one then no shift operations so rather than writing this you can also write theta n minus P where P is what position it depends on the position given fine now see this is now unsorted area so now the best L go to insert a day tine unsorted array because you are not concerned with the ordering of the array then the best elbow is worth what you can do see see you want to insert a ten here at position three initially there is this one rather than shifting like this what you can do because arrays unsorted so you can simply take this value insert at the end of the array and here you can insert directly this in so you can simply write these two lines at a size size means size is equal to five so a oh five you can simply store this as zero zero means from a of position minus one position is three 3 minus 1 that is 2 and add to add position minus 1 you can insert number and this will take how much time constant time that is 1 so in exam if question is asked then what you will write you will not write that in West case this one was is this one or this one no may be options would be given but an exam you are going to write down the best algorithm time complexity so the best time complexity is Theta and in unsorted array fine in sorted array what you have to do in that case you cannot do this thing you cannot simply take this value and set at the end and do this thing no you have to take care of the relative ordering of the elements in sorted array in that case you are doing two you are going to do this shift operations so you can apply this shifting or method in this unsorted array also but the best method is what you simply do this thing so next video will discuss how to delete data from the array so I'll see you in the next video till then bye-bye take

Channel: Jenny's Lectures CS IT

Views: 816,253

Keywords: array, what is array, array operations, traversal, insertion, deletion, data structures, array in data structure, jennys lectures, jayanti khatri lamba, jenny lamba, sorting algorithms, algorithm, data structures and algorithms, study material, ugc net computer science syllabus, gate, GATE computer science, preparation, cse, it, computer science engineering, information technology, youtube channels, technical, CS/IT, net and jrf, jrf, net exam, JRF, dijkstra algorithm, c program, arrays

Id: Bnjbun-hiBk

Length: 28min 51sec (1731 seconds)

Published: Wed Jul 24 2019