Arrays
What is array? Do you know what it is?
Array is a collection of items or values which is stored contiguously(contiguous means sequentially no deviation between the elements or empty space between them. That's for we can easily calculate the position of each element).
Keep in mind that C/C++ array and Java array not same. In Java arrays are dynamically allocated in heap. But in C/C++ arrays are not dynamically allocated like java.
/* If you see some algorithm have no explanations that means I made though algorithm too much simple anyone can understand. Also in code section(means where I written code) I also tell you what is actually happening */
Operations on Array
Traversal: Processing each element in the list.
Search: Finding the location of the element with a given value or the record(record is the collection of field values of a given entity(entity is something that has certain attribute or properties which may be assigned values)set) with a given key.
Insertion: Adding a new element to the list.
Deletion: Removing an element from the list.
Sorting: Arranging the elements in some type of order.
Ex: Order: 1) ascending 2) descending
Merging: Combining two list into a single list.
Types of Arrays
Indexed Array: Indexed arrays store a series of one or more values. It can be called as 1 Dimensional array.
Multi dimensional Array: Nested array or you can say 2D array or ND array.
Associated array: Which array is like an object, is made of unordered keys and values. This types of array used keys instead of using numerical values.
_____________________________________________________________
Indexed Array
Traversal:
Algorithm
Step 1: [Initialize counter] Set K=LB.
Step 2: Repeat Step 3 and 4 while K<=UB.
Step 3: [Visit element] Apply PROCESS to LA[K].
Step 4: [Increase counter] Set K = K+1.
[End of Step 2 loop]
Step 5: Exit
Explanation
What we need to traverse array in index type array which is 1D array.
Suppose I have an array called, LA={1,2,3,4,5}
Set K=LB [means Lower Bound[Lower Bound is the lowest index of array] ]
Similarly UB [means Upper Bound[Upper Bound is the Highest index of array]]
/*Keep in mind that I said index that means LB=0 & UB=4. Why because array always start from 0 so if you count it 5 than it will be 5-1=4.*/
Repeat 3 & 4 while K<=UB what is K? K is equals to LB.
We can say that Repeat 3 & 4 while LB <= UB
Why we need to repeat 3 & 4 there must be something special right? Yes.
If that condition is true than this 2 process will do else Exit.
3 step is used to visit element. How increasing index size using loop.
LA[0],LA[1]..LA[4].
4 step is helping us to increasing the size of index.
A lot explanation right but I'll not explain this what I explain here like how we increase size how index in count in array.
Code
Problems
Q1. Find the summation of array elements.
Q2. Find the largest value from the array.
Q3. Find the smallest value from the array.
Searching: In this section I'm going to talk about Linear search & Binary Search.
Linear search means sequentially search.
Ex:
array[] = {1,2,3,4,5}
I want to find 3. What linear search do is start from LB=0 to UB=4 if find than print it.
Binary search means divide and find the element.
Ex:
array[] = {1,2,3,4,5}
I want to find 3. What binary will do LB=0 & UB=4. B=UB/2 Now check the element is greater than B or less than B. Oh it's equals to B than print B ok it's simple. This algorithm is called most extremely efficient searching algorithm
Algorithm
Linear search(Data, N, ITEM, LOC)
Data = Linear array with N elements.
N = Natural Numbers //Take Real number - Natural number😂
ITEM = This is a item which is we are looking for
LOC = This is used to find the location of that element if fined.
---------------------------
Step 1: [Insert ITEM at the end of DATA] Set DATA[N]= ITEM.
Step 2: [Initialize counter] Set LOC = 0.
Step 3: [Search for ITEM] Repeat while DATA[LOC] != ITEM.
Set LOC = LOC + 1.
[End of loop]
Step 4: [Successful?] If LOC = N
than: Set LOC = 0.
Step 5: Exit
Explanation
Step 1: Here we setting the data at N position don't do it. It just an idea If you do the same you will get Index out of bound 5 or what is your number is. It means that you need to traverse top to bottom.
Step 2: Setting location to 0 simple.
Step 3: Repeat while DATA[LOC] != ITEM means you just need to traverse and check weather the item is in the list or not. Look I said search for Item so it is so simple task if DATA[LOC] == ITEM yes got it else loop end.
Step 4: If your not done say sorry else say thank you
Step 5: Welcome Exit.
Code
Examples
I'll provide it later because I need to complete all the algorithm 1st
---------------------------
Algorithm
Binary Search (DATA, LB, UB, ITEM, LOC)
DATA = Linear array(Indexed array don't get confused thank you).
LB = Lower bound
UB = Upper bound
ITEM = Item that you wants to search for.
LOC = Location of that element.
Step 1: [Initialize segment variables.]
Set,
BEG = LB,
END = UB,
MID = INT((BEG + END)/2).
Step 2: Repeat Step 3 & 4
while BEG <= END and DATA[MID] != ITEM
Step 3: If ITEM < DATA[MID], than:
Set END = MID - 1;
Else
Set BEG = MID +1;
[End of if structure]
Step 4: Set MID = INT((BEG + END)/2).
[End of Step 2 loop]
Step 5: IF DATA[MID] = ITEM, then:
Set LOC = MID
Else
Set LOC = NULL.
[End of if structure]
Step 6: Exit.
Explanation
Step 1: What I'm doing here is just simply assigning variable
BEG = LB
END = UB
MID = INT((BEG + END)/2)
MID = INT because it can give fraction so casting purpose and than simply adding 1st index of array and last index of array after that divide by 2.
Step 2: Now what you need to do is check the process is in the range BEG<=ENG ok than check is this element what I want is that not equals to MID means DATA[MID] this value is not equals to your given value. If it is true
Step 3: Than come here now check the value your element is less than DATA[MID] element? IF yes than END -1 else BEG +1.
Step 4: Than the operation we did here is MID = ((BEG + END)/2) //not need to cast it because int / int = int so it will automatically cast to int.
Step 5: If you find it do this else do that .
Step 6: End.
CODE
Problems
Coming soon...
Insertion:
Now will insert element on our indexed array in any position keep in mind that you want to insert element when array is full no space in the array so, you can not be able to do that ok. There but be free space to insert an element.
Algorithm
INSERT(LA, K, N, ITEM)
LA = Just an array with N element.
K = is Natural number means positive integers or the index where you want to place your element.
ITEM = item that you want to insert.
Step 1: [Initialize counter] Set J=N.
Step 2: Repeat Step 3 and 4 while J>=K.
Step 3: [Move Jth element downward] LA[J] = LA[J-1].
Step 4: [Decrease counter] Set J = J-1.
[End of Step 2 loop]
Step 5: [Insert Element] Set LA[K] = ITEM.
Step 6: [Reset N] N=N+1.
Step 7: Exit
Explanation
Step 1: Here you can initialize one variable to another or not your choice.
Step 2: Condition is J>=K so do it until it reach to your desire index. Or the index you love.
Step 3: Time to downward if your index is 5 than assign 5 to index value 6 like this
LA[J] = LA[J-1]
5=4
4=3
3=2
2=1
1=0
0=your element my be here if you want
don't do this LA[J+1] = LA[J] means
suppose you have array A={1,2,3,4} and you this that LA[J+1] = LA[J] and we know J=N and N is equal to number of array we want suppose N=4,
A[0]= 1
A[1]= 2
A[2]= 3
A[3]= 4
what you did is,
LA[4+1] = LA[4] //Look no value in index 4 but you assigning value 4 to value 5 so, that doesn't make sense.
Step 4: Decrease your counter because your index moving downward to take place in upward.
Step 5: LA[K] = ITEM it means the position is ready to insert your element just insert it and be happy.
Step 6: Just increase N by 1
Deletion: Is it possible to delete a element completely from array in java?
Answer is: No
Because of Java arrays do not provide a direct remove method to remove an element. Arrays in Java are static so the size of the arrays cannot change once they are instantiated. Thus we cannot delete an element and reduce the array size. But we can replace it.
Algorithm
Now In this time what I'll do is just simple algorithm. Like main thing.
Step 1: Repeat 2 & 3 While J<array.length-1
Step 2: array[J]=array[J+1];
Step 3: [increase J] J++.
Step 4: End.
Explanation
Step1: J is the index of your element which element you want to delete. Or if you want to delete element by value not index you can do that also if element==array[i] than use for loop and use above algorithm and yes 2nd loop will start from 1st loop index where it becomes true. It's super basic I think no need to explain it more details.
Code
Sorting: In this section I'll do two sorting algorithm Section sort & Bubble Sort
Algorithm
Step 1: Create array
Step 2: start from i=0 Repeat 3 until array.length - 1 and i++
Step 3: start from j=0 Repeat 4 & 5 until array.length -1 and j++
Step 4: check if(array[1]<array[0]) //common sense is that 1<0 or 2<1
Step 5: than swap
[End of both array]
Step 6: Exit //or print if you want
Code
Algorithm
Selection Sort:
Step 1: Create your nice array
Step 2: Start from i=0 Repeat 3 to array.length-1 and i++
and Set minIndex=i.
Step 3: Start from j=i Repeat 4 to array.length-1 and j++
Step 4: If array[j] is less than our array[minIndex]
yes: than minIndex = j.
[End of inner loop]
Step 5: Swapping
[End of outer loop]
Step 6: Exit.
Merging: In this section we will see merge sorting on indexed array. I tell you what is merging but it is bit complex it follows divide and conquer process. No warries I'll try to make it simple as possible. Most used sorting data structures are Merge sort & Quick sort. I'll talk about Quick sort later. But now let's talk about marge sort.
Due to lot's of work(academic study) I'm so much busy that's for this blog will be done in O(n!) manner which is Time complexity of my working algorithm.
Algorithm
Code
_____________________________________________________________
Multidimensional Array
Traversal:
Algorithm
Code
Searching:
Algorithm
Code
Insertion:
Algorithm
Code
Deletion:
Algorithm
Code
Sorting:
Algorithm
Code
Merging:
Algorithm
Code
_____________________________________________________________
Associated Array
Traversal:
Algorithm
Code
Searching:
Algorithm
Code
Insertion:
Algorithm
Code
Deletion:
Algorithm
Code
Sorting:
Algorithm
Code
Merging:
Algorithm
Code
_____________________________________________________________
Comments
Post a Comment