UNIT-2

ARRAYS
Basic concepts:
Introduction:
Arrays are the special type of data structure in C. They are the derived data types that
can store the primitive type of data such as int, char, double, float, etc. For example, if
we want to store the marks of a student in 6 subjects, then we don't need to define a
different variable for the marks in different subjects. Instead, we can define an array
that can store the marks in each subject at the contiguous memory locations.
Definition: Array is a linear data structure and it is defined as the collection of similar
types of data items (Homogeneous) stored at contiguous memory locations. It is one
of the simplest data structures where each data element can be randomly accessed
by using its index number.

Declaration and initialization of an Array:

[Link]:
In C, we have to declare the array like any other variable before using it. We can
declare an array by specifying its name, the type of its elements, and the size of its
dimensions. When we declare an array in C, the compiler allocates the memory
block of the specified size to the array name.
data_type array_name [size];
or
data_type array_name [size1] [size2]...[sizeN];
Examples:
1. int a[10];
2. int matrix[3][2];

[Link]
Initialization in C is the process to assign some initial value to the variable. When the
array is declared or allocated memory, the elements of the array contain some
garbage value. So, we need to initialize the array to some meaningful value. There
are multiple ways in which we can initialize an array in C.

A) Array Initialization with Declaration

In this method, we initialize the array along with its declaration. We use an initializer
list to initialize multiple elements of the array. An initializer list is the list of values
enclosed within braces { } separated by a comma.

data_type array_name [size] = {value1, value2, ... valueN};

Example:
1. int num[5]={1,2,3,4,5};
2. char vowels[5]={‘a’,’e’,’i’,’o’,’u’};

Operations on Array:
Following are the basic operations supported by an array.
1. Traverse − print all the array elements one by one.
2. Insertion − Adds an element at the given index.
3. Deletion − Deletes an element at the given index.
4. Search − Searches an element using the given index or by the value.
5. Update − Updates an element at the given index.

1. Traverse:
This operation is performed to traverse through the array elements. It prints all
array elements one after another. Traversal is the process in which we visit every
element of the data structure atleast once. For C array traversal, we use loops to
iterate through each element of the array .
Example program:
#include <stdio.h>
void main()
{
int Arr[5] = {18, 30, 15, 70, 12};
 int i;
printf("Elements of the array are:\n");
for(i = 0; i<5; i++)
{
printf("Arr[%d] = %d, ", i, Arr[i]);
}
getch();
}

Output:

[Link] operation:

This operation is performed to insert one or more elements into the array. As per the
requirements, an element can be added at the beginning, end, or at any index of the
array.

Example program:

#include <stdio.h>
int main()
{
int arr[20] = { 18, 30, 15, 70, 12 };
int i, x, pos, n = 5;
printf("Array elements before insertion\n");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
x = 50; // element to be inserted
pos = 4;
n++;
for (i = n-1; i >= pos; i--)
arr[i] = arr[i - 1];
 arr[pos - 1] = x;
printf("Array elements after insertion\n");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}

Output:

[Link] operation:

As the name implies, this operation removes an element from the array and then
reorganizes all of the array elements.

Example program:

#include <stdio.h>

void main() {
int arr[] = {18, 30, 15, 70, 12};
int k = 30, n = 5;
int i, j;

printf("Given array elements are :\n");

for(i = 0; i<n; i++) {

printf("arr[%d] = %d, ", i, arr[i]);
}
 j = k;

while( j < n) {
arr[j-1] = arr[j];
j = j + 1;
}

n = n -1;

printf("\nElements of array after deletion:\n");

for(i = 0; i<n; i++) {

printf("arr[%d] = %d, ", i, arr[i]);
}
}

Output:

[Link] operation:

This operation is performed to search an element in the array based on the value or
index.

Example program:

#include <stdio.h>

void main() {
int arr[5] = {18, 30, 15, 70, 12};
int item = 70, i, j=0 ;
 printf("Given array elements are :\n");

for(i = 0; i<5; i++) {

printf("arr[%d] = %d, ", i, arr[i]);
}
printf("\nElement to be searched = %d", item);
while( j < 5){
if( arr[j] == item ) {
break;
}

j = j + 1;
}

printf("\nElement %d is found at %d position", item, j+1);

}

Output:

[Link] operation:

This operation is performed to update an existing array element located at the given
index.

Example program:

#include <stdio.h>
void main()
{
int arr[5] = {18, 30, 15, 70, 12};
int item = 50, i, pos = 3;
 printf("Given array elements are :\n");

for(i = 0; i<5; i++)

{
printf("arr[%d] = %d, ", i, arr[i]);
}
arr[pos-1] = item;
printf("\nArray elements after updation :\n");

for(i = 0; i<5; i++)

{
printf("arr[%d] = %d, ", i, arr[i]);
}
getch();
}

Output:

Types of Arrays in C:

There are two types of arrays based on the number of dimensions it has. They are as
follows:
1. One Dimensional Arrays (1D Array)
2. Multidimensional Arrays

1. One Dimensional Array:

The One-dimensional arrays, also known as 1-D arrays in C are those arrays that
have only one dimension.

array_name [size];
// C Program to illustrate the use of 1D array
#include <stdio.h>

int main()
{

// 1d array declaration
int arr[5];

// 1d array initialization using for loop

for (int i = 0; i < 5; i++) {
arr[i] = i * i - 2 * i + 1;
}

printf("Elements of Array: ");

// printing 1d array by traversing using for loop
for (int i = 0; i < 5; i++) {
printf("%d ", arr[i]);
}

return 0;
}

Output:

Elements of Array: 1 0 1 4 9

Array of Characters (Strings):

// C Program to illustrate strings
#include <stdio.h>

int main()
{

// creating array of character

char arr[6] = { 'G', 'e', 'e', 'k', 's', '\0' };

// printing string
int i = 0;
while (arr[i]) {
printf("%c", arr[i++]);
}
return 0;
}

Output:

Geeks

2. Multidimensional Array:

Multi-dimensional Arrays in C are those arrays that have more than one
dimension(subscript). Some of the popular multidimensional arrays are 2D arrays
and 3D arrays. We can declare arrays with more dimensions than 3d arrays but they
are avoided as they get very complex and occupy a large amount of space.

A. Two-Dimensional Array

A Two-Dimensional array or 2D array in C is an array that has exactly two

dimensions (Two subscripts). They can be visualized in the form of rows and
columns organized in a two-dimensional plane.
Syntax of 2D Array in C

array_name[size1] [size2];

Here,
 size1: Size of the first dimension.
 size2: Size of the second dimension .

// C Program to illustrate 2d array

#include <stdio.h>

int main()
{

// declaring and initializing 2d array

int arr [2][3] = { 10, 20, 30, 40, 50, 60 };

printf("2D Array:\n");
// printing 2d array
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 3; j++) {
printf ("%d ", arr[i][j]);
}
printf("\n");
}
 return 0;
}

Output:

2D Array:
10 20 30
40 50 60

B. Three-Dimensional Array
Another popular form of a multi-dimensional array is Three-Dimensional Array or 3D
Array. A 3D array has exactly three dimensions (Three subscripts). It can be
visualized as a collection of 2D arrays stacked on top of each other to create the
third dimension.

Syntax of 3D Array in C:

array_name [size1] [size2] [size3];

// C Program to illustrate the 3d array

#include <stdio.h>

int main()
{

// 3D array declaration
int arr[2][2][2] = { 10, 20, 30, 40, 50, 60 };
 // printing elements
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
printf("%d ", arr[i][j][k]);
}
printf("\n");
}
printf("\n \n");
}
return 0;
}

Output:

10 20
30 40

50 60
0

Memory representation of linear array (Storage structure):

Arrays can be created in C (declared and initialized) is as shown below,

Array is a container which can hold a fix number of items and these items
should be of the same type. Following are the important terms to understand
the concept of Array.
• Element − Each item stored in an array is called an element.
• Index − Each location of an element in an array has a numerical index, which
is used to identify the element.

As per the above illustration, there are some of the following important points -

 Index starts with 0.

 The array's length is 10, which means we can store 10 elements.
 Each element in the array can be accessed via its index.

Arrays as abstract data types (ADT):

1. Representation of data is defined by the language compiler itself. But the

operations on the data are not defined by the compiler.

2. We have to implement or provide the operations on Array data structure.
3. So, data structure array and the set of operations together we can call it as

Abstract Data Type (ADT).

Operations on Array DS:

We can perform more operations on the array data structure but the above are some
basic operations. Let us give some information about the above functions-

1. Display () – To Display the entire array on the screen.

2. Add(n) / Append(n) – To add a particular element on the end of the array.

3. Insert (index, n) – To add an element to a particular index.

4. Delete (index) – To delete an element with the help of an index in the given
array.

5. Search (n) – To check whether the given element is present or not in an array.

6. Get (index) – It will return the element which presents on the given index.

7. Set (index, x) – It will change the element with the new element at a particular
index.

8. Max () / Min () – These will return the max and min element in the given array.

9. Reverse () – It will reverse the order of elements in the given array.

[Link] () – It will shift the whole elements either on the left or right side by the
given number.
Sorting:
Sorting is the process of arranging the array elements in a particular order i.e either
ascending (Increasing)or descending (Decreasing) order.

Example:

int A[10] = { 5, 4, 10, 2, 30, 45, 34, 14, 18, 9 }

The Array sorted in ascending order will be given as;

A[] = { 2, 4, 5, 9, 10, 14, 18, 30, 34, 45 }

Sorting algorithms:

A sorting algorithm is used to arrange elements of an array/list in a specific order (i.e

either in ascending or descending order)
There are various sorting algorithms that can be used to complete this operation. And,
we can use any algorithm based on the requirement.
Types of sorting Algorithm:
1. Selection sort
2. Bubble sort
3. Comb sort
4. Quick sort
5. Counting sort
6. Insertion sort
7. Radix sort
8. Merge sort
9. Shell sort
[Link] sort etc.

Bubble sort:

Bubble Sort (sinking 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 is quite high.
Working of Bubble sort Algorithm:

Bubble sort works on the repeatedly swapping of adjacent elements until they are not
in the intended order. It is called bubble sort because the movement of array
elements is just like the movement of air bubbles in the water. Bubbles in water rise
up to the surface; similarly, the array elements in bubble sort move to the end in each
iteration.

To understand the working of bubble sort algorithm, let's take an unsorted array. We
are taking a short and accurate array, as we know the complexity of bubble sort
is O(n2).

Example,

Let the elements of array are -

First Pass
Sorting will start from the initial two elements. Let compare them to check which is
greater.

Here, 32 is greater than 13 (32 > 13), so it is already sorted. Now, compare 32 with 26.

Here, 26 is smaller than 36. So, swapping is required. After swapping new array will
look like -

Now, compare 32 and 35.

Here, 35 is greater than 32. So, there is no swapping required as they are already
sorted.

Now, the comparison will be in between 35 and 10.

Here, 10 is smaller than 35 that are not sorted. So, swapping is required. Now, we
reach at the end of the array. After first pass, the array will be -
Now, move to the second iteration.

Second Pass
The same process will be followed for second iteration.

Here, 10 is smaller than 32. So, swapping is required. After swapping, the array will be
-

Now, move to the third iteration.

Third Pass
The same process will be followed for third iteration.

Here, 10 is smaller than 26. So, swapping is required. After swapping, the array will be
-
Now, move to the fourth iteration.

Fourth pass
Similarly, after the fourth iteration, the array will be -

Hence, there is no swapping required, so the array is completely sorted.

Algorithm:

1. begin BubbleSort(arr)
2. for all array elements
3. if arr[i] > arr[i+1]
4. swap(arr[i], arr[i+1])
5. end if
6. end for
7. return arr
8. end BubbleSort

//C Program to sort array elements using bubble sort

#include <stdio.h>

void bubble_sort(int arr[], int n) {

int i, j;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) {
 if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr, n);
printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}

Selection sort:

Selection sort is a simple and efficient sorting algorithm that works by repeatedly
selecting the smallest (or largest) element from the unsorted portion of the list and
moving it to the sorted portion of the list.
The algorithm repeatedly selects the smallest (or largest) element from the unsorted
portion of the list and swaps it with the first element of the unsorted part. This
process is repeated for the remaining unsorted portion until the entire list is sorted
Working of Selection sort Algorithm:

Now, let's see the working of the Selection sort Algorithm.

To understand the working of the Selection sort algorithm, let's take an unsorted
array. It will be easier to understand the Selection sort via an example.

Let the elements of array are -

Now, for the first position in the sorted array, the entire array is to be scanned
sequentially.

At present, 12 is stored at the first position, after searching the entire array, it is
found that 8 is the smallest value.

So, swap 12 with 8. After the first iteration, 8 will appear at the first position in the
sorted array.
For the second position, where 29 is stored presently, we again sequentially scan the
rest of the items of unsorted array. After scanning, we find that 12 is the second
lowest element in the array that should be appeared at second position.

Now, swap 29 with 12. After the second iteration, 12 will appear at the second
position in the sorted array. So, after two iterations, the two smallest values are
placed at the beginning in a sorted way.

The same process is applied to the rest of the array elements. Now, we are showing a
pictorial representation of the entire sorting process.
Now, the array is completely sorted.

Algorithm:

1. SELECTION SORT (arr, n)

2.
3. Step 1: Repeat Steps 2 and 3 for i = 0 to n-1
4. Step 2: CALL SMALLEST (arr, i, n, pos)
5. Step 3: SWAP arr[i] with arr[pos]
6. [END OF LOOP]
7. Step 4: EXIT
8. SMALLEST (arr, i, n, pos)
9. Step 1: [INITIALIZE] SET SMALL = arr[i]
[Link] 2: [INITIALIZE] SET pos = i
[Link] 3: Repeat for j = i+1 to n
 [Link] (SMALL > arr[j])
13. SET SMALL = arr[j]
[Link] pos = j
15.[END OF if]
16.[END OF LOOP]
[Link] 4: RETURN pos

//Program to sort list using selection sort

#include <stdio.h>
void main()
{
int i, j, n, temp, pos, a[25];
clrscr();
printf ("Enter the number of elements\n");
scanf ("%d",&n);
printf ("Enter the %d elements\n", n);
for (i = 0; i < n ; i++)
{
scanf ("%d", &a[i]);
}
for (i = 0; i < n - 1; i++)
{
pos =I ;
for (j = i+1; j < n; j++)
{
if (arr[pos] > arr[j])
{
pos=j;
}
if(pos!=i)
{
temp = arr[i];
arr[i] = arr[pos];
arr[pos] = temp;
}
 }
printf("Sorted elements\n"):
for (i = 0; i < n ; i++)
{
printf("%d",a[i]);
}
getch();
}

Quick sort:
Sorting is a way of arranging items in a systematic manner. Quicksort is the widely
used sorting algorithm that makes n log n comparisons in average case for sorting an
array of n elements.

It is a faster and highly efficient sorting algorithm. This algorithm follows the divide
and conquer approach. Divide and conquer is a technique of breaking down the
algorithms into subproblems, then solving the subproblems, and combining the
results back together to solve the original problem.

• Divide: In Divide, first pick a pivot element. After that, partition or rearrange
the array into two sub-arrays such that each element in the left sub-array is less
than or equal to the pivot element and each element in the right sub-array is
larger than the pivot element.
• Conquer: Recursively, sort two subarrays with Quicksort.
• Combine: Combine the already sorted array.

Quicksort picks an element as pivot, and then it partitions the given array around the
picked pivot element. In quick sort, a large array is divided into two arrays in which
one holds values that are smaller than the specified value (Pivot), and another array
holds the values that are greater than the pivot.
After that, left and right sub-arrays are also partitioned using the same approach. It
will continue until the single element remains in the sub-array.

Working of Quick Sort Algorithm:

To understand the working of quick sort, let's take an unsorted array. It will
make the concept clearer and more understandable.

Let the elements of array are -

In the given array, we consider the leftmost element as pivot. So, in this case,
a[left] = 24, a[right] = 27 and a[pivot] = 24.

Since, pivot is at left, so algorithm starts from right and move towards left.
Now, a[pivot] < a[right], so algorithm moves forward one position towards left, i.e.
-

Now, a[left] = 24, a[right] = 19, and a[pivot] = 24.

Because, a[pivot] > a[right], so, algorithm will swap a[pivot] with a[right], and
pivot moves to right, as -

Now, a[left] = 19, a[right] = 24, and a[pivot] = 24. Since, pivot is at right, so
algorithm starts from left and moves to right.

As a[pivot] > a[left], so algorithm moves one position to right as -

Now, a[left] = 9, a[right] = 24, and a[pivot] = 24. As a[pivot] > a[left], so algorithm
moves one position to right as -
Now, a[left] = 29, a[right] = 24, and a[pivot] = 24. As a[pivot] < a[left], so, swap
a[pivot] and a[left], now pivot is at left, i.e. -

Since, pivot is at left, so algorithm starts from right, and move to left. Now, a[left]
= 24, a[right] = 29, and a[pivot] = 24. As a[pivot] < a[right], so algorithm moves
one position to left, as -

Now, a[pivot] = 24, a[left] = 24, and a[right] = 14. As a[pivot] > a[right], so, swap
a[pivot] and a[right], now pivot is at right, i.e. -
Now, a[pivot] = 24, a[left] = 14, and a[right] = 24. Pivot is at right, so
the algorithm starts from left and move to right.

Now, a[pivot] = 24, a[left] = 24, and a[right] = 24. So, pivot, left and right
are pointing the same element. It represents the termination of
procedure.

Element 24, which is the pivot element is placed at its exact position.

Elements that are right side of element 24 are greater than it, and the
elements that are left side of element 24 are smaller than it.

Now, in a similar manner, quick sort algorithm is separately applied to

the left and right subarrays. After sorting gets done, the array will be -

3
Tunga mahavidyalaya, thirthahalli
1
Algorithm:

1. QUICKSORT (array A, start, end)

2. {
3. 1 if (start < end)
4. 2 {
5. 3 p = partition(A, start, end)
6. 4 QUICKSORT (A, start, p - 1)
7. 5 QUICKSORT (A, p + 1, end)
8. 6 }
9. }
10.// The partition algorithm rearranges the sub-arrays in a place
[Link] (array A, start, end)
12.{
13. 1 pivot ? A[end]
14. 2 i ? start-1
15. 3 for j ? start to end -1 {
16. 4 do if (A[j] < pivot) {
17. 5 then i ? i + 1
18. 6 swap A[i] with A[j]
19. 7 }}
20. 8 swap A[i+1] with A[end]
21. 9 return i+1
22.}
23.

Insertion sort:

3
Tunga mahavidyalaya, thirthahalli
2
Insertion sort works similar to the sorting of playing cards in hands. It is
assumed that the first card is already sorted in the card game, and then we
select an unsorted card. If the selected unsorted card is greater than the first
card, it will be placed at the right side; otherwise, it will be placed at the left
side. Similarly, all unsorted cards are taken and put in their exact place.

The simple steps of achieving the insertion sort are listed as follows
(Algorithm):

• Step 1 - If the element is the first element, assume that it is already

sorted. Return 1.
• Step2 - Pick the next element, and store it separately in a key.
• Step3 - Now, compare the key with all elements in the sorted array.
• Step 4 - If the element in the sorted array is smaller than the current
element, then move to the next element. Else, shift greater elements in
the array towards the right.
• Step 5 - Insert the value.
• Step 6 - Repeat until the array is sorted.

Working of Insertion Sort Algorithm

3
Tunga mahavidyalaya, thirthahalli
3
 To understand the working of the insertion sort algorithm, let's take

an unsorted array. It will be easier to understand the insertion sort via an

example. Let the elements of array are -

Initially, the first two elements are compared in insertion sort.

Here, 31 is greater than 12. That means both elements are already in
ascending order. So, for now, 12 is stored in a sorted sub-array.

Now, move to the next two elements and compare them.

Here, 25 is smaller than 31. So, 31 is not at correct position. Now, swap 31
with 25. Along with swapping, insertion sort will also check it with all
elements in the sorted array.

For now, the sorted array has only one element, i.e. 12. So, 25 is greater
than 12. Hence, the sorted array remains sorted after swapping.

3
Tunga mahavidyalaya, thirthahalli
4
Now, two elements in the sorted array are 12 and 25. Move forward to the
next elements that are 31 and 8.

Both 31 and 8 are not sorted. So, swap them.

After swapping, elements 25 and 8 are unsorted.

So, swap them.

Now, elements 12 and 8 are unsorted.

So, swap them too.

Now, the sorted array has three items that are 8, 12 and 25. Move to the
next items that are 31 and 32.

3
Tunga mahavidyalaya, thirthahalli
5
Hence, they are already sorted. Now, the sorted array includes 8, 12, 25 and
31.

Move to the next elements that are 32 and 17.

17 is smaller than 32. So, swap them.

Swapping makes 31 and 17 unsorted. So, swap them too.

Now, swapping makes 25 and 17 unsorted. So, perform swapping again.

Now, the array is completely sorted

3
Tunga mahavidyalaya, thirthahalli
6
Merge sort:
Merge sort is similar to the quick sort algorithm as it uses the divide and
conquer approach to sort the elements. It is one of the most popular and
efficient sorting algorithm. It divides the given list into two equal halves,
calls itself for the two halves and then merges the two sorted halves. We
have to define the merge() function to perform the merging.

The sub-lists are divided again and again into halves until the list cannot be
divided further. Then we combine the pair of one element lists into two-
element lists, sorting them in the process. The sorted two-element pairs is
merged into the four-element lists, and so on until we get the sorted list.

Working of Merge Sort Algorithm

To understand the working of the merge sort algorithm, let's take an

unsorted array. It will be easier to understand the merge sort via an
example.

Let the elements of array are -

3
Tunga mahavidyalaya, thirthahalli
7
According to the merge sort, first divide the given array into two equal
halves. Merge sort keeps dividing the list into equal parts until it cannot be
further divided.

As there are eight elements in the given array, so it is divided into two
arrays of size 4.

Now, again divide these two arrays into halves. As they are of size 4, so
divide them into new arrays of size 2.

Now, again divide these arrays to get the atomic value that cannot be
further divided.

Now, combine them in the same manner they were broken.

In combining, first compare the element of each array and then combine
them into another array in sorted order.

So, first compare 12 and 31, both are in sorted positions. Then compare 25
and 8, and in the list of two values, put 8 first followed by 25. Then
compare 32 and 17, sort them and put 17 first followed by 32. After that,
compare 40 and 42, and place them sequentially.

3
Tunga mahavidyalaya, thirthahalli
8
In the next iteration of combining, now compare the arrays with two data
values and merge them into an array of found values in sorted order.

Now, there is a final merging of the arrays. After the final merging of above
arrays, the array will look like -

Now, the array is completely sorted.

Algorithm:

In the following algorithm, arr is the given array, beg is the starting
element, and end is the last element of the array.

1. MERGE_SORT(arr, beg, end)

2.
3. if beg < end
4. set mid = (beg + end)/2
5. MERGE_SORT(arr, beg, mid)
6. MERGE_SORT(arr, mid + 1, end)
7. MERGE (arr, beg, mid, end)
8. end of if
9.
[Link] MERGE_SORT

3
Tunga mahavidyalaya, thirthahalli
9
The important part of the merge sort is the MERGE function. This function
performs the merging of two sorted sub-arrays that are A[beg…
mid] and A[mid+1…end], to build one sorted array A[beg…end]. So, the inputs
of the MERGE function are A[], beg, mid, and end.

Searching:

• Searching algorithms are methods or procedures used to find a specific

item or element within a collection of data.
• These algorithms are widely used in computer science and are crucial for
tasks like searching for a particular record in a database, finding an
element in a sorted list, or locating a file on a computer.
• Searching is the process of finding some particular element in the list
(collection of elements).
• If the element is present in the list, then the process is called successful,
and the process returns the location of that element. Otherwise, the
search is called unsuccessful.

Types of Searching:
• Linear search
• Binary search
• Interpolation search
• Hashing
• Tree based searching
• Ternary searching
• Jump Searching
• Exponential searching etc.

[Link] search:

Linear Search: In this simple algorithm, each element in the collection is

sequentially checked until the desired item is found, or the entire list is

4
Tunga mahavidyalaya, thirthahalli
0
traversed. It is suitable for small-sized or unsorted lists, but its time complexity
is O(n) in the worst case.

• Linear search is also called as sequential search algorithm. It is the

simplest searching algorithm. In Linear search, we simply traverse the list
completely and match each element of the list with the item whose
location is to be found. If the match is found, then the location of the
item is returned; otherwise, the algorithm returns NULL.
• It is widely used to search an element from the unordered list, i.e., the
list in which items are not sorted. The worst-case time complexity of
linear search is O(n).

Implementation of linear search:

1. First, we have to traverse the array elements using a for loop.
2. In each iteration of for loop, compare the search element with the
current array element, and -
a. If the element matches, then return the index of the
corresponding array element.
b. If the element does not match, then move to the next element.
3. If there is no match or the search element is not present in the given
array, return -1.

Working of Linear search

4
Tunga mahavidyalaya, thirthahalli
1
 To understand the working of linear search algorithm, let's
take an unsorted array. It will be easy to understand the working of
linear search with an example. Let the elements of array are -

Let the element to be searched is K = 41

Now, start from the first element and compare K with each
element of the array.

The value of K, i.e., 41, is not matched with the first element of the
array. So, move to the next element. And follow the same process
until the respective element is found.

4
Tunga mahavidyalaya, thirthahalli
2
Now, the element to be searched is found. So algorithm will return the index of
the element matched.

2) Binary search:

Binary search is the search technique that works efficiently on sorted lists.
Hence, to search an element into some list using the binary search technique,
we must ensure that the list is sorted.

Binary search follows the divide and conquer approach in which the list is
divided into two halves, and the item is compared with the middle element of
the list. If the match is found then, the location of the middle element is
returned. Otherwise, we search into either of the halves depending upon the
result produced through the match.

4
Tunga mahavidyalaya, thirthahalli
3
 To understand the working of the Binary search algorithm, let's
take a sorted array. It will be easy to understand the working of Binary
search with an example.

There are two methods to implement the binary search algorithm -

 Iterative method
 Recursive method

1) Iteration Method
binarySearch (arr, x, low, high)
repeat till low = high mid =
(low + high)/2 if (x ==
arr[mid]) return mid
else if (x > arr[mid])
low = mid + 1 else
high = mid - 1

4
Tunga mahavidyalaya, thirthahalli
4
2) Recursive Method (The recursive method follows the divide and conquers
approach)

binarySearch(arr, x, low, high)

if low > high
return False
else
mid = (low + high) / 2
if x == arr[mid]
return mid
else if x > arr[mid]
return binarySearch(arr, x, mid + 1, high)
else
return binarySearch(arr, x, low, mid - 1)

Working of linear search algorithm:

Let the elements of array are -
4
Tunga mahavidyalaya, thirthahalli
5
Let the element to search is, K = 56

We have to use the below formula to calculate the mid of the array -

1. mid = (low + high)/2 So, in

the given array - low = 0 high

= 8 mid = (0 + 8)/2 = 4. So, 4

is the mid of the array.

Now, the element to search is found. So algorithm will return the index
of the element matched.

Binary Search recursive algorithm:

4
Tunga mahavidyalaya, thirthahalli
6
Binary_Search (a, lower_bound, upper_bound, val)
Step 1: set beg = lower_bound, end = upper_bound, pos = - 1
Step 2: repeat steps 3 and 4 while beg <=end
Step 3: set mid = (beg + end)/2
Step 4: if a[mid] = val
set pos = mid
print pos
go to step 6
else if a[mid] > val
set end = mid - 1
else
set beg = mid + 1
[end of if]
[end of loop]
Step 5: if pos = -1
print "value is not present in the array"
[end of if]
Step 6: exit

//Program to search an element using binary search

#include <stdio.h>
int binarySearch (int a[], int beg, int end, int val)
{
int mid;
if(end >= beg)
{ mid = (beg + end)/2;
/* if the item to be searched is present at middle */
if(a[mid] == val)
{
return mid+1;
}
/* if the item to be searched is smaller than middle, then it can only be i
n left subarray */
else if(a[mid] < val)
{
4
Tunga mahavidyalaya, thirthahalli
7
 return binarySearch (a, mid+1, end, val);
}

/* if the item to be searched is greater than middle, then it can only be i

n right subarray */
else
{
return binarySearch(a, beg, mid-1, val);
}
}
return -1;
}
int main() {
int a[] = {11, 14, 25, 30, 40, 41, 52, 57, 70}; // given array
int val = 40; // value to be searched
int n = sizeof(a) / sizeof(a[0]); // size of array
int res = binarySearch(a, 0, n-1, val); // Store result
printf("The elements of the array are - ");
for (int i = 0; i < n; i++)
printf ("%d ", a[i]);
printf ("\nElement to be searched is - %d", val);
if (res == -1)
printf ("\nElement is not present in the array");
else
printf("\nElement is present at %d position of array", res);
return 0;
}

Sparse Matrix:

4
Tunga mahavidyalaya, thirthahalli
8
 A matrix can be defined as a two-dimensional array having 'm' rows and 'n'
columns. A matrix with m rows and n columns is called m × n matrix. It is a set
of numbers that are arranged in the horizontal or vertical lines of entries.

Sparse matrices are those matrices that have the majority of their elements
equal to zero. In other words, the sparse matrix can be defined as the matrix
that has a greater number of zero elements than the non-zero elements.

There are the following benefits of using the sparse matrix -

1. Storage - We know that a sparse matrix contains lesser non-zero
elements than zero, so less memory can be used to store elements. It
evaluates only the non-zero elements.
2. Computing time: In the case of searching in sparse matrix, we need to
traverse only the non-zero elements rather than traversing all the sparse
matrix elements. It saves computing time by logically designing a data
structure traversing non-zero elements.

4
Tunga mahavidyalaya, thirthahalli
9
 Representation of the sparse matrix:
The non-zero elements in the sparse matrix can be stored using triplets that
are rows, columns, and values. There are two ways to represent the sparse
matrix that are listed as follows -
 Array representation
 Linked list representation

Array representation of the sparse matrix:

Representing a sparse matrix by a 2D array leads to the wastage of lots

of memory. This is because zeroes in the matrix are of no use, so storing zeroes
with non-zero elements is wastage of memory. To avoid such wastage, we can
store only non-zero elements. If we store only non-zero elements, it reduces
the traversal time and the storage space.
• In 2D array representation of sparse matrix, there are three fields used
that are named as -

• Row - It is the index of a row where a non-zero element is located in the

matrix.
• Column - It is the index of the column where a non-zero element is
located in the matrix.
• Value - It is the value of the non-zero element that is located at the index
(row, column).

Consider an example,

5
Tunga mahavidyalaya, thirthahalli
0
Array representation,

Linked List representation of the sparse matrix:

In a linked list representation, the linked list data structure is used to

represent the sparse matrix. The advantage of using a linked list to
represent the sparse matrix is that the complexity of inserting or deleting a
node in a linked list is lesser than the array.
Unlike the array representation, a node in the linked list representation
consists of four fields.

The four fields of the linked list are given as follows:

1. Row - It represents the index of the row where the non-zero element
is located.

5
Tunga mahavidyalaya, thirthahalli
1
 2. Column - It represents the index of the column where the non-zero
element is located.
3. Value - It is the value of the non-zero element that is located at the
index (row, column).
4. Next node - It stores the address of the next node.

Consider an Example:

5
Tunga mahavidyalaya, thirthahalli
2
 5
Tunga mahavidyalaya, thirthahalli
3