arrays in data structures and algorithms
October 4, 2022

Arrays in Data Structure

An array is a list of a finite number of homogenous data elements (i.e. data elements of the same type)
Arrays can be classified as
  • One – dimensional array or linear array that requires only one index to access an individual element of the array.
  • Two – dimensional arrays require two indices to access an individual element of the array. It is also called a matrix.
  • Multi-dimensional arrays for which we need two or more indices.

ADT Array

An array is a collection of homogeneous elements.
  1. We can access every element by an index number.
  2. Each element is referred to with an index and the name of the array generally the index value starts with zero or one.
  3. The array is stored in memory in conjunctive locations.

Linear Arrays

An array is a list of a finite number of elements of consecutive homogenous data elements of the same type) such that
  1. The element of the array are referenced respectively by an index set consisting of n consecutive integer numbers
  2. The elements of the array are stored respectively in successive memory locations.

The number n of elements is called the length or size of the array. If not explicitly stated, we will assume the index set consists of the integers 1,2… n. In general, the length or the number of data elements of the array can be obtained from the index set by the formula

N = UB – LB + 1
LB is the Lower bound
UB is the upper bound

Address Calculation

One Dimensional Array

Loc (A [K]) = base (A) + W x (K – LB)

where
base(A) = is the base address of the array.
W = no. of the memory cell for a single element.
K = index of the current element.
LB = Lower Bound

Two Dimensional Array

Let A be a two – dimensional matrix of size m’n. Through a is pictured as a rectangular pattern with m row and n column. The array will be represented in memory by a block of m’n sequential memory location. However, the element can be stored in two different ways

  1. COLUMN MAJOR ORDER: -The element is stored column by column i.e. the m elements of the first column are stored in the first m location, and elements of the second column are stored in the next m location and soon.
  2. ROW MAJOR ORDER: -The element is stored row by row i.e. the n elements of the first row are stored in the first n location, and elements of the second row are stored in the next n location and soon.

The address LOC (A [J, K]) of the array can be obtained by this formula: 
Row – Major Order: 
    LOC (A [J, K]) = Base (A) + W * [n * (J – LB) + (K – LB)] 
Column – Major Order: 
    LOC (A [J, K]) = Base (A) + W * [m * (K – LB) + (J – LB)]

where w=no, of the memory cell for a single element.
An m’n matrix is two – dimensional. Whose m, n elements are arranged in m row and n column. A matrix is denoted by capital letters such as A, B, C.. and its element are denoted by corresponding lower letters suffixed with row and column index such as a (j, k), b (j, k)……

Three-Dimensional Array

Let A be a three-dimensional matrix of size I’m’n. The element can be stored in two different ways
The address LOC (A [I, J, K]) of the array can be obtained by this formula:

Row – Major Order: 
    LOC (A [I, J, K]) = Base (A) + W * [m x n x (I – LB) + n x (J – LB) + (K – LB)] 
Column – Major Order: 
    LOC (A [I, J, K]) = Base (A) + W * [m x n x (I – LB) + m x (K – LB) + (J – LB)]

Operations on Linear Arrays

  1. Traverse
  2. Searching
  3. Insertion
  4. Deletion
  5. Merging
  6. Sorting

Traverse: -Traversing is the process of visiting each element of the array exactly once. As the elements can be accessed directly only we have to vary an index from lower bound to upper bound in the step of one to access individual elements in order For an array of size n, the loop executes n times so the traversal operation on linear arrays is O (n) operation.

Algorithm – Traversal of Array

TRAVERSE (A, LB, UB)
Let ARR is a linear array with lower bound LB and upper bound UB. This algorithm traverses ARR applying an operation PROCESS to each element of LA.

1. Set K:= LB [Initialize counter] 
2. Repeat steps 3 and 4 while K < = UB 
3.        Apply PROCESS to A [k]  [Visit element.]
4.        Set K:= K + 1 [Increase counter]
   [End of Step 2] 
5. Exit

Insertion: -To Insert an element at position k first we have to move elements starting from the kth position down by one position in order to accommodate the element at the kth position. The best possible case occurs when the item is inserted at the last position. In this case, no element is moved down. The worst case occurs when the element is to be inserted at the first position. In this case, all the elements are moved down. Therefore loop executes n time. Thus the complexity of the insertion operation is O (n) i.e. linear time.

Algorithm – Insert a new element in an array at a particular position.

INSERT (ARR, N, ITEM, POS)
Here ARR is the Linear array with N elements and POS is a positive integer such that POS < = N. This procedure inserts an element ITEM at position POS in array ARR of size N.

1. Set I: = N. [Initiallize I to the last element]
2. Repeat steps 3 and 4 while I > = POS: 
3.        Set ARR [I + 1]: = ARR [I]. [Shifting elements one position down]
4.        Set I: = I-1. [Decrement I by 1]
   [End of step 2 loop] 
5. Set ARR [POS] = ITEM. [Inserting ITEM at POS]
6. Set N: = N + 1. [Reset the number N of elements in ARR]
7. Exit.

Deletion: Deletion refers to the operation of removing an element from an existing list of elements. After deletion, the linear array’s size is decreased by one factor. Like the insertion operation, deleting an element from the end of the linear array can be done very easily, However, to delete an element from any other location, the elements are to be moved upward: in order to fill up the location vacated by the removed element

Algorithm – Delete an element in an array from a particular position.

DELETE (ARR, N, POS)
Here ARR is the Linear array with N elements and PS is a positive integer such that POS < = N. This procedure removes an element ITEM from position POS in array ARR of size N.

1. Set I: = POS. [Initialize I to the element to be removed.] 
2. Repeat steps 3 and 4 while I < N: 
3.      Set ARR [I]:= ARR [I + 1]. [Shifting elements one position up] 
4.      Set I: = I + 1. [Increment I by 1] 
   [End of step 2 loop] 
5. Set N: N – 1 [Reset the number N of elements in ARR]
6. Exit

Search Operations: -Searching is the process of finding the location of a given element in the linear array search is said to be successful if the given element is found i.e. the element does exist in the array, otherwise unsuccessful.
There are two approaches to the search operation
  1. Linear search
  2. Binary search

Linear Search: – Given no information about the array the only way to search for a given element item is to compare items with each element one by one. This method, which traverses a sequence to locate an item is called linear search or sequential search. In the best possible case, the item may occur in the first position. In this case, the search operation terminates in success with just one comparison. However, the worst case occurs when either the item is present at the last position or missing from the array. Thus in the worst case, the linear search is O (n) operations.

Algorithm – Linear Search

LINEAR SEARCH (A, N, ITEM, LOC)
Here DATA is the Linear array with N elements and ITEM is a given item of information. This procedure finds the locations LOC of ITEM in A or sets LOC: 0 if the search is unsuccessful.

1. Set LOC: = 0. [Initialize LOC]
2. Set I: = 1. [Initialize counter]
3. Repeat steps 4 to 6 while I < = N:
4.    IF A[I] = ITEM, then: [if the item is found]
            Set LOC:= I and Exit.
      [End of If structure] 
5. Set I: = I + 1. [Increment counter by 1]
   [End of step 3 loop] 
6. Exit.

Binary Search: – This search is fast than linear search but it can be used only when the array is sorted. In this search we first find the mid of the array, if the value is found at the mid position then the search ends otherwise the number is searched in the left half or right half. This process is continued till the item is not found. In each iteration or in each recursive call, the search is reduced to one-half of the array. Therefore, for n elements in the array, there will be logan iterations or recursive calls. Thus the complexity of the binary search is O (log2n). This complexity will be the same irrespective of the position of the element, even if it is not present in the array.

Algorithm – Binary Search

BINARY_SEARCH (A, N, ITEM, LOC)

Here DATA is the Linear array with N elements and ITEM is a given item of information. This procedure finds the locations LOC of ITEM in A or sets LOC: = 0 if the search is unsuccessful.

1. Set LOW: = 1, HIGH:= N.      [Initialize]
2. Repeat steps 3 to 6 while LOW < = HIGH 
3. Set MID:= (LOW + HIGH) / 2 
4. If A [MID] = ITEM, then: 
      Set POS:= MID and RETURN.
5. Else If ITEM > A [MID], then: 
      Set LOW:=MID – 1. 
6. Else: 
      Set HIGH.=MID + 1 
   [End of If structure]
7. Set POS: = 0 
8. Exit

Merge Operation: – Merging is the process of combining the elements of two similar structures (linear arrays) into a single structure. Suppose that two arrays are sorted then our aim is to combine them in such a way that the combined array is also in the sorted order.

Algorithm – Merge two sorted arrays.

MERGE (ARR1, ARR2, ARR3, N1, N2)
[This procedure merges two sorted arrays ARR1 and ARR2 into ARR3 of size N1, N2 and N1 + N2 respectively.]

1. Set I: = 1, J: = 1, K: = 1 
2. Repeat step 3 and 4 while I < = N1 and J < = N2 
3.    If ARR1 [I] < ARR2 [J] then
          (a)   Set ARR3 [K]: = ARR1 [1] 
          (b)   Set I: = I + 1 [Increment I by 1]
      Else:
          (a)   Set ARR3 [K]: = ARR2 [J] 
          (b)   Set J: = J + 1 [Increment J by 1]
      [End of If structure]
4.    Set K: K + 1 [Increment K by 1] 
   [End of Step 2 loop] 
5. Repeat steps 6 and 7 while I < = N1 [Remaining of ARR1]
6.    Set ARR3 [K]: = ARR1 [I] 
7.    Set K = K + 1, I:= I +1 
   [End of step 5 loop] 
8. Repeat steps 9 and 10 while J < = N2 [Remaining of ARR2]
9. Set ARR3 [K]: = ARR2 [J] 
10.Set K: = K + 1, J: = J + 1
   [End of step 8 loop] 
11. Exit.

Leave a Reply

Your email address will not be published. Required fields are marked *