Arrays & Structure Introduction

Structures

Structures (or struct in languages like C and C++) are a user-defined data type that allows
grouping variables of different data types under a single name. Unlike arrays, structures
can combine integers, floats, characters, or even arrays within a single unit, making them
ideal for representing more complex real-world entities. For example, a struct called Student
can have int rollNumber, char name[50], and float marks. Structures allow better organization
and logical grouping of related data, making programs easier to read and maintain. Accessing
individual members of a structure is done using the dot (.) operator, e.g., [Link].
Structures are particularly useful when modeling objects in programs and can also be nested
or used in combination with arrays for more advanced data organization.

Arrays
An array is a collection of elements of the same data type stored in contiguous memory
locations. It allows storing multiple values under a single name, with each element
accessible using an index. Arrays can be one-dimensional, like a simple list of numbers, or
multi-dimensional, such as matrices or tables. The main advantage of arrays is efficient
access to elements using indices, which allows constant time retrieval (O(1)). For example,
an integer array of size 5 can store five integer values like [10, 20, 30, 40, 50], and the element at
index 2 can be accessed directly as arr[2]. Arrays are widely used in programming for
implementing other data structures like stacks, queues, and hash tables. However, a limitation
of arrays is that their size must be defined in advance (in static arrays), and all elements
must be of the same type.

Declaration of arrays
data_type array_name[array_size]={elements separated by commas}
or
data_type array_name[array_size];
Basic Operations in Arrays
The basic operations in the Arrays are insertion, deletion, searching, display, traverse, and
update. These operations are usually performed to either modify the data in the array or to
report the status of the array.
Following are the basic operations supported by an array.

Traverse − print all the array elements one by one.

Insertion − Adds an element at the given index.
Deletion − Deletes an element at the given index.
Search − Searches an element using the given index or by the value.
Update − Updates an element at the given index.
Display − Displays the contents of the array.

Array – Traversal
This operation traverses through all the elements of an array. We use loop statements to
carry this out.
Algorithm Traverse Array(A, n)
Input: An array A of size n
Output: Each element of the array
Step 1: Start
Step 2: For i = 0 to n-1, do
Print A[i]
Step 3: End For
Step 4: Stop

Array - Search Operation

Linear Algorithms
Consider LA is a linear array with N elements and K is a positive integer such that K<=N.
Following is the algorithm to find an element with a value of ITEM using sequential search.
1. Start
2. Set J = 0
3. Repeat steps 4 and 5 while J < N
4. IF LA[J] is equal ITEM THEN GOTO STEP 6
5. Set J = J +1
6. PRINT J, ITEM
7. Stop

Binary Search
Algorithm Binary_Search(A, n, key)
Input: Sorted array A of size n, element key
Output: Position of key if found, otherwise -1
Step 1: Start
Step 2: Set low = 0, high = n-1
Step 3: While low <= high do
mid = (low + high) / 2
If A[mid] == key then return mid
Else if A[mid] < key then low = mid + 1
Else high = mid - 1
Step 4: If not found, return -1
Step 5: Stop

Insertion in Arrays
Insertion means adding a new element at a specific position in an array.
Since arrays have fixed size, elements must often be shifted to make space.
Algorithm: Insert into Array
Algorithm Insert_Array(A, n, pos, val)
Input: Array A of size n, position pos, value val
Output: Array with new element inserted
Step 1: Start
Step 2: For i = n-1 down to pos-1 do
A[i+1] = A[i] // Shift elements right
Step 3: A[pos-1] = val // Insert value
Step 4: n = n + 1
Step 5: Stop
Deletion
Consider LA is a linear array with N elements and K is a positive integer such that K<=N.
Following is the algorithm to delete an element available at the Kth position of LA.
1. Start
2. Set J = K
3. Repeat steps 4 and 5 while J < N
4. Set LA[J] = LA[J + 1]
5. Set J = J+1
6. Set N = N-1
7. Stop

Merge Two Arrays

Algorithm Merge_Arrays(A, n1, B, n2, C)
Input: Array A of size n1, Array B of size n2
Output: Array C containing elements of A followed by B

Step 1: Start
Step 2: For i = 0 to n1-1
C[i] = A[i]
Step 3: For j = 0 to n2-1
C[n1 + j] = B[j]
Step 4: Size of C = n1 + n2
Step 5: Stop

1 dimensional & 2 dimensional arrays, row & column major

representation
When it comes to organizing and accessing elements in a multi-dimensional array, two
prevalent methods are Row Major Order and Column Major Order. These approaches
define how elements are stored in memory and impact the efficiency of data access in
computing.
Calculation of address of element of 1-D, 2-D, and 3-D using row-
major and column-major order
Calculating the address of any element In the 1-D array:
A 1-dimensional array (or single-dimension array) is a type of linear array. Accessing its
elements involves a single subscript that can either represent a row or column index.

To find the address of an element in an array the followingformula is used-

Address of A[Index] = B + W * (Index - LB)
Where:
 Index = The index of the element whose address is to be found (not the value of the
element).
 B = Base address of the array.
 W = Storage size of one element in bytes.
 LB = Lower bound of the index (if not specified, assume zero).

Example:
Given the base address of an array A[1300 ............ 1900] as 1020 and the size of each
element is 2 bytes in the memory, find the address of A[1700].
Given:
 Base address (B) = 1020
 Lower bound (LB) = 1300
 Size of each element (W) = 2 bytes
 Index of element (not value) = 1700

Formula used:
Address of A[Index] = B + W * (Index - LB)
Address of A[1700] = 1020 + 2 * (1700 - 1300)
= 1020 + 2 * (400)
 = 1020 + 800
Address of A[1700] = 1820

Calculate the address of any element in the 2-D array

The 2-dimensional array can be defined as an array of arrays. The 2-Dimensional arrays are
organized as matrices which can be represented as the collection of rows and columns as
array[M][N] where M is the number of rows and N is the number of columns.

To find the address of any element in a 2-Dimensional array there are the following two
ways-
1. Row Major Order
2. Column Major Order

Evaluation of polynomial – Representation

A polynomial is an expression like:

P(x)=anxn+an−1xn−1+⋯+a1x+a0P(x) = a_n x^n + a_{n-1} x^{n-1} + \dots + a_1 x +

a_0P(x)=anxn+an−1xn−1+⋯+a1x+a0

Where:

 a0,a1,...,ana_0, a_1, ..., a_na0,a1,...,an are coefficients

 nnn = degree of polynomial
 xxx = variable

Array Representation:

 Store coefficients in an array.

  Array index = power of x, array value = coefficient.

Example:

P(x)=5x3+2x2+0x+7P(x) = 5x^3 + 2x^2 + 0x + 7P(x)=5x3+2x2+0x+7

Array representation: int coeff[4] = {7, 0, 2, 5};

 coeff[0] = 7 → constant term

 coeff[1] = 0 → x¹ term
 coeff[2] = 2 → x² term
 coeff[3] = 5 → x³ term

Searching
sequential search
Suppose we are searching a target element in an array. In linear search we begin with the
first position of the array, and traverse the whole array in order to find the target element. If
we find the target element we return the index of the element. Otherwise, we will move to
the next position. If we arrive at the last position of an array and still can not find the target,
we return -1. This is called the Linear search or Sequential search.

Algorithm

Algorithm Linear_Search(A[], n, key)

Input: Array A of size n, element key
Output: Index of key if found, else -1

Step 1: Start
Step 2: For i = 0 to n-1 do
If A[i] == key then
Return i // Key found at index i
Step 3: End For
Step 4: Return -1 // Key not found
Step 5: Stop

Binary Search
Binary Search is a more optimized form of searching algorithm. It cuts down the search
space in halves achieving logarithmic time complexity on a sorted data. We take two
extremes lower bound and upper bound and compare our target element with the middle
element. In the process we discard one half where we are sure our target element can not be
found and update our lower and upper bound accordingly.

Algorithm Binary_Search(A[], n, key)

Input: Sorted array A of size n, element key
Output: Index of key if found, else -1

Step 1: Start
Step 2: Set low = 0, high = n-1
Step 3: While low <= high do
mid = (low + high) / 2
If A[mid] == key then
Return mid // Key found
Else if A[mid] < key then
low = mid + 1 // Search in right half
Else
high = mid - 1 // Search in left half
Step 4: End While
Step 5: Return -1 // Key not found
Step 6: Stop

Fibonacci Search
Fibonacci Search is a comparison-based technique that uses Fibonacci numbers to search an
element in a sorted array .

 It is similar to Binary Search but chooses positions based on Fibonacci numbers.

 Works well for large datasets where division operations are expensive.

How it Works
Find the smallest Fibonacci number greater than or equal to the array size n.

Divide the array using Fibonacci numbers:

o If the element at index fib(k-2) < key → move right.

 o Else → move left.
 Repeat until the element is found or array is exhausted.

Indexed Sequential Search

Indexed Sequential Search is a search technique used on sorted data that combines
sequential search with an index table.

 The index table stores the starting address of blocks in the main data.
 First, search the index to find the block where the element may exist.
 Then, perform sequential search within that block

Sorting Algorithms
A Sorting Algorithm is used to rearrange a given array or list of elements in an order. For
example, a given array [10, 20, 5, 2] becomes [2, 5, 10, 20] after sorting in increasing order
and becomes [20, 10, 5, 2] after sorting in decreasing order.

Selection Sort
Selection Sort is a comparison-based sorting algorithm. It sorts an array by repeatedly
selecting the smallest (or largest) element from the unsorted portion and swapping it with
the first unsorted element. This process continues until the entire array is sorted.

1. First, we find the smallest element and swap it with the first element. This way we get
the smallest element at its correct position.

2. Then we find the smallest among remaining elements (or second smallest) and swap it
with the second element.

3. We keep doing this until we get all elements moved to correct position.
Bubble Sort

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the
adjacent elements if they are in the wrong order. This algorithm is not suitable for large data
sets as its average and worst-case time complexity are quite high.
Insertion Sort Algorithm

Insertion sort is a simple sorting algorithm that works by iteratively inserting each element
of an unsorted list into its correct position in a sorted portion of the list. It is like sorting
playing cards in your hands. You split the cards into two groups: the sorted cards and the
unsorted cards. Then, you pick a card from the unsorted group and put it in the right place
in the sorted group.