DSCC- Module 2

Arrays :
Array is a collection of items of the same variable type that are stored at contiguous
memory locations. It is one of the most popular and simple data structures used in
programming.

Basic terminologies of Array

● Array Index: In an array, elements are identified by their indexes. Array index starts
from 0.
● Array element: Elements are items stored in an array and can be accessed by their
index.
● Array Length: The length of an array is determined by the number of elements it can
contain.

Applications of Array Data Structure:

Arrays mainly have advantages like random access and cache friendliness over other data
structures that make them useful.

Below are some applications of arrays.

Storing and accessing data: Arrays store elements in a specific order and allow constant-
time O(1) access to any element.

Searching: If data in array is sorted, we can search an item in O(log n) time. We can also find
floor(), ceiling(), kth smallest, kth largest, etc efficiently.
Matrices: Two-dimensional arrays are used for matrices in computations like graph
algorithms and image processing.

Implementing other data structures: Arrays are used as the underlying data structure for
implementing stacks and queues.

Dynamic programming: Dynamic programming algorithms often use arrays to store

intermediate results of subproblems in order to solve a larger problem.

Data Buffers: Arrays serve as data buffers and queues, temporarily storing incoming data
like network packets, file streams, and database results before processing.

Basic Operations in Arrays :

The 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.
 Sort- Sort an array either ascending or descending order
 Update − Updates an element at the given index.
 Display − Displays the contents of the array.

Create and Traverse an Array:

Algorithm
Step 1: Start
Step 2: Declare an integer array arr[100] and an integer variable n.
Step 4: Read the value of n from the user.
Step 5: Display a message: “Enter n elements”.
Step 6: Repeat for i = 0 to n - 1
Read arr[i] from the user.
Step 7: Display: “The array elements are:”
Step 8: Repeat for i = 0 to n - 1
Display: arr[i] with its index.
Step 9: Stop
C Program:
Insertion (Adds an element at the given index) :
Algorithm:
Step 1: Start
Step 2: Declare an integer array e.g. arr[] = {10, 20, 30, 40, 50} and set n = 5.
Step 3: Set the position pos = 2 (for example) and value to insert value = 99.
Step 4: Shift elements to the right from the end to the given position:
Repeat for i = n down to pos + 1:
arr[i] = arr[i - 1]
Step 5: Insert value at the given position:
arr[pos] = value
Step 6: Increment n = n + 1
Step 7: Display the updated array:
Repeat for i = 0 to n - 1:
Print arr[i]
Step 8: Stop

C Program:
Deletion (Deletes an element at the given index) :
Algorithm:
Step 1: Start
Step 2: Declare and initialize the array
e.g., arr[] = {10, 20, 30, 40, 50} and n = 5.
Step 3: Set the index pos = 2 (index of the element to delete).
Step 4: Shift elements to the left from pos + 1 to n - 1:
Repeat for i = pos to n - 2:
arr[i] = arr[i + 1]
Step 5: Decrease size: n = n - 1
Step 6: Display the updated array:
Repeat for i = 0 to n - 1:
Print arr[i]
Step 7: Stop

C Program:
Alogorithm for creation, traversal, insertion and deletion
operations in an array using function
Step 1: Start
Step 2: In main, declare:
a. An integer array arr[100]
b. A variable n to store the number of elements

Step 3: Define a function createArray(arr[]):

a. Prompt the user to enter the number of elements (maximum 100)
b. Read the value into n
c. Ask the user to enter the array elements
d. Repeat for i from 0 to n - 1:
i. Prompt for element at index i
ii. Read arr[i]
e. Return n

Step 4: Define a function traverseArray(arr[], n):

a. Display "The array elements are:"
b. Repeat for i from 0 to n - 1:
i. Display index i and value arr[i]

Step 5: Define a function insertElement(arr[], n, pos, value):

a. If n >= 100 or pos < 0 or pos > n:
i. Display "Insertion not possible."
ii. Return n
b. Repeat for i from n down to pos + 1:
i. Set arr[i] = arr[i - 1]
c. Set arr[pos] = value
d. Return n + 1

Step 6: Define a function deleteElement(arr[], n, pos):

a. If n <= 0 or pos < 0 or pos >= n:
i. Display "Deletion not possible."
ii. Return n
b. Repeat for i from pos to n - 2:
i. Set arr[i] = arr[i + 1]
c. Return n - 1

Step 7: In main, call n = createArray(arr)

Step 8: Call traverseArray(arr, n)
Step 9: Call n = insertElement(arr, n, pos, value)
Step 10: Call traverseArray(arr, n)
Step 11: Call n = deleteElement(arr, n, pos)
Step 12: Call traverseArray(arr, n)
Step 13: Stop
C Program:
#include <stdio.h>

// Create array
int createArray(int arr[]) {
int n, i;
printf("Enter the number of elements (max 100): ");
scanf("%d", &n);

printf("Enter %d elements:\n", n);

for (i = 0; i < n; i++) {
printf("Element %d: ", i);
scanf("%d", &arr[i]);
}

return n;
}

// Traverse array
void traverseArray(int arr[], int n) {
int i;
printf("The array elements are:\n");
for (i = 0; i < n; i++) {
printf("Index %d: %d\n", i, arr[i]);
}
}

// Modified Insert element

int insertElement(int arr[], int n, int pos, int value) {
int i;
if (n >= 100 || pos < 0 || pos > n) {
printf("Insertion not possible.\n");
return n;
}

for (i = n; i > pos; i--) {

arr[i] = arr[i - 1];
}
arr[pos] = value;

return n + 1;
}

// Modified Delete element

int deleteElement(int arr[], int n, int pos) {
int i;
if (n <= 0 || pos < 0 || pos >= n) {
 printf("Deletion not possible.\n");
return n;
}

for (i = pos; i < n - 1; i++) {

arr[i] = arr[i + 1];
}

return n - 1;
}

int main() {
int arr[100];
int n;

n = createArray(arr);

traverseArray(arr, n);

n = insertElement(arr, n, 2, 99);
printf("\nAfter Insertion at index 2:\n");
traverseArray(arr, n);

n = deleteElement(arr, n, 2);
printf("\nAfter Deletion from index 2:\n");
traverseArray(arr, n);

return 0;
}

Searching :
Searching is the process of finding the location of a specific element in a given array. There
are mainly two types of searching techniques used in arrays:

1. Linear Search
2. Binary Search

Linear Search (Sequential Search) :

The simplest search to be done on an array is the linear search. This search starts from one
end of the array and keeps iterating until the element is found, or there are no more
elements left (which means that the element does not exist).
This is suitable for unsorted array.
Algorithm :
Step 1: Start
Step 2: Input the array arr[], number of elements n, and the key to search.
Step 3: Repeat for i = 0 to n - 1
a. If arr[i] == key, then
Return i (element found at index i)
Step 4: If the loop completes without finding the key
Return -1 (element not found)
Step 5: Stop

C Program with and without using function:

Time Complexity

 Average case: O(n)

 Best case: O(1)
 Worst case: O(n)

The average time complexity is O(n) as the element to be found may be present at the end
of the list or may not be present at all. Linear search has to visit all the elements until the
needed element is found. Algorithmically, this comes out to be O(n).
The best and worst case of a search algorithm will be O(1) and O(n) respectively, as the
element to be searched could always be found on the first iteration or the last iteration.

Binary Search :
Binary Search is an efficient algorithm for finding an element in a sorted array by repeatedly dividing
the search interval in half.

The search starts by accessing the middle of the array. If the element is less than this element, it
starts its search from this element to the left of the array. If the element is larger more than this
element, it starts its search from this element to the right of the array. This process is repeated
unless a the middle element is equal to the number we are searching.

It is faster than linear search with time complexity O(log n).

Algorithm :
Step 1: Start
Step 2: Input the sorted array arr[], size n, and the key to search
Step 3: Initialize low = 0, high = n - 1
Step 4: Repeat while low <= high:
a. Find mid = (low + high) / 2
b. If arr[mid] == key, return mid (element found)
c. If key < arr[mid], set high = mid - 1
d. Else, set low = mid + 1
Step 5: If loop ends, return -1 (element not found)
Step 6: Stop

Time Complexity

 Average case: O(Log n)

 Best case: O(1)
 Worst case: O(log n)

C Program:
Sorting:
Sorting an array means arranging its elements in a particular order — either ascending
(small to large) or descending (large to small). There are so many sorting algorithms we can
use any one for sorting.

Bubble Sort :
Bubble Sort is a simple comparison-based sorting algorithm. It works by repeatedly
swapping adjacent elements if they are in the wrong order.
Think of it like bubbles rising to the top — the largest values “bubble” to the end with each
pass.

Algorithm :
Step 1: Start
Step 2: Take the array and its size n
Step 3: Repeat the following for i = 0 to n - 2 (total passes = n - 1):
a: Start from the first element (index 0)
b: For each element from j = 0 to n - i - 2, do:
 b.i: Compare arr[j] with arr[j + 1]
b.ii: If arr[j] > arr[j + 1], then swap them
Step 4: After each pass, the largest unsorted element moves to its correct position at the
end
Step 5: Repeat until the array is fully sorted
Step 6: Stop

Time Complexity :
Best case: O(n), (Already sorted, only one pass needed)
Average case: O(n2), (Many swaps and comparisons)
Worst-case: O(n2), (Reverse order → max comparisons/swaps)

C Program:
Selection Sort:
Selection Sort works by repeatedly selecting the smallest (or largest) element from the
unsorted part of the array and placing it at the correct position in the sorted part.
It divides the array into two parts:
 Sorted part (at the beginning)
 Unsorted part (remaining elements)
Algorithm :
Step 1: Start
Step 2: Take the array and its size n
Step 3: Repeat the following for i = 0 to n - 2 (total passes = n - 1):
a: Assume the element at position i is the minimum (set minIndex = i)
b: For each element from j = i + 1 to n - 1, do:
b.i: Compare arr[j] with arr[minIndex]
b.ii: If arr[j] < arr[minIndex], set minIndex = j
c: After inner loop, if minIndex ≠ i, swap arr[i] and arr[minIndex]
Step 4: After each pass, the smallest unsorted element is placed at the correct position in
the sorted part
Step 5: Repeat until the entire array is sorted
Step 6: Stop

Time Complexity :
Best case /Average case / Worst-case: O(n2)

C Program :
Address Calculation of 1D and 2D Array:
Calculating the address of any element In the 1-D array:
A 1D array is a list of elements stored one after another in memory.
To find the memory address of arr[i]:
Address(arr[i]) = B + i * W
Where,
B = base address (starting address of array arr)
i = index (0-based)
W = size of each element in bytes (e.g., 4 for int)

Example:
Let B = 1000, W = 4, then Address(arr[3]) = 1000 + 3 * 4 = 1012

Calculating the address of any element In the 2-D array:

The 2-Dimensional arrays are organized as matrices which can be represented as the
collection of rows and columns .
To find the address of any element in a 2-Dimensional array there are the following two
ways-
Row Major Order
Column Major Order

Row Major Order :

If elements of an array are stored in a row-major fashion means moving across the row and
then to the next row then it's in row-major order. To find the address of the element using
row-major order use the following formula:
Suppose the array is, int arr[3][4];

Address(arr[i][j]) = B + [i * N + j] * W
Where,

 B = base address
 i = row index
 j = column index
 N = total number of columns in each row (here, 4)
 W = size of each element (e.g., 4 bytes for int)

Example:

Let B = 2000, W = 4, N = 4 (4 columns)

To find address of arr[2][1]:

Address = 2000 + [2 * 4 + 1] * 4 = 2000 + (8 + 1) * 4 = 2000 + 36 = 2036

Column Major Order :
If elements of an array are stored in a column-major fashion means moving across the
column and then to the next column then it's in column-major order. To find the address of
the element using column-major order use the following formula:
Suppose the array is, int arr[3][4];

Address(arr[i][j]) = B + [j * M + i] * W
Where,

 B = base address
 i = row index
 j = column index
 M = total number of rows in each column (here, 3)
 W = size of each element (e.g., 4 bytes for int)

Example:

Let B = 2000, W = 4, M = 3 (4 rows)

To find address of arr[2][1]:

Address = 2000 + [1 * 3+ 2] * 4 = 2000 + 5* 4 = 2000 + 20 = 2020

Sparse Matrix
A matrix is a two-dimensional data object made of m rows and n columns, therefore having
total m x n values. If most of the elements of the matrix have 0 value, then it is called a
sparse matrix.
Why to use Sparse Matrix instead of simple matrix ?

 Save memory space.

 Speed up computations

Example:

Note: If P is the no. of non-zero elements in sparse matrix a[M][N], then for sparsity
MxN > 3xP
Sparse Matrix Representation Using Array:
Representing a sparse matrix by a 2D array leads to wastage of lots of memory as zeroes in
the matrix are of no use in most of the cases. So, instead of storing zeroes with non-zero
elements, we only store non-zero elements. This means storing non-zero elements
with triples- (Row, Column, value).
2D array is used to represent a sparse matrix in which there are three rows named as
 Row: Index of row, where non-zero element is located
 Column: Index of column, where non-zero element is located
 Value: Value of the non zero element located at index - (row,column

Implementation:
#include<stdio.h>
int main()
{
// Assume 4x5 sparse matrix
int sparseMatrix[4][5] =
{
{0 , 0 , 3 , 0 , 4 },
{0 , 0 , 5 , 7 , 0 },
{0 , 0 , 0 , 0 , 0 },
{0 , 2 , 6 , 0 , 0 }
};

int size = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 5; j++)
if (sparseMatrix[i][j] != 0)
size++; // No. of non-zero elements

// number of columns in compactMatrix (size) must be equal to number of non - //zero

elements in sparseMatrix
int compactMatrix[3][size];

// Making of new matrix

int k = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 5; j++)
 if (sparseMatrix[i][j] != 0)
{
compactMatrix[0][k] = i;
compactMatrix[1][k] = j;
compactMatrix[2][k] = sparseMatrix[i][j];
k++;
}

for (int i=0; i<3; i++)

{
for (int j=0; j<size; j++)
printf("%d ", compactMatrix[i][j]);

printf("\n");
}
return 0;
}