Module 4- Searching and Sorting

Searching
Introduction to SEARCHING

Searching means to find whether a particular value is present in an array or not. If the value is
present in the array, then searching is said to be successful and the searching process gives the
location of that value in the array. However, if the value is not present in the array, the searching
process displays an appropriate message and in this case searching is said to be unsuccessful.
There are two popular methods for searching the array elements:
● linear search
● binary search.
The algorithm that should be used depends entirely on how the values are organized in the array.
For example, if the elements of the array are arranged in ascending order, then binary search
should be used, as it is more efficient for sorted lists in terms of complexity.
Linear Searching
Linear Search
Linear search, also called as sequential search, is a very simple method used for searching an array
for a particular value. It works by comparing the value to be searched with every element of the
array one by one in a sequence until a match is found. Linear search is mostly used to search an
unordered list of elements (array in which data elements are not sorted).
LINEAR_SEARCH(A[], N, ITEM , LOC)
Step 1: Set LOC=0
Step 2: Repeat for i = 1 to N
Step 3: If A[i] == ITEM Then
Step 4: Set LOC = i
[End If]
[End Loop]
Step 5: If LOC==0 Then
Display “Element not Exist”
Step 6: Otherwise
Display “Element in LOC location”
Binary Searching
Binary Search
Binary search is a searching algorithm that works efficiently with a sorted list. The mechanism
of binary search can be better understood by an analogy of a telephone directory.
BINARY_SEARCH(A, lower_bound, upper_bound, element)
Complexity=O(log n)
Step 1 : Set initial_value=lower_bound ,end_value =upper_bound
Step 2: Repeat Steps 3 to 5 while initial_value<=end_value
Step 3 :Find the middle element of array. using ,
middle = initial_value + end_value / 2 ;
Step 2 : If A[middle] = element, return ‘element found’ and index.
Step 3 : if A[middle] > element, call the function with end_value =
middle - 1 .

Step 4 : if A[middle] < element, call the function with initial_value

= middle + 1 .
Step 5 : exit.
Binary Searching int main()
{
Binary search is a searching algorithm int c, beg, end, mid n, search, array[100];
that works efficiently with a sorted list. printf("Enter number of elements\n");
The mechanism of binary search can be better scanf("%d", &n);
understood by an analogy of a telephone directory. printf("Enter numbers in sorted order\n", n);
for (c = 0; c < n; c++)
scanf("%d", &array[c]);
printf("\n\n Enter the number that has to be searched: ");
scanf("%d", &num);
beg = 0, end = n-1;
while(beg<=end)
{
mid = (beg + end)/2
if (num== arr[mid])
{printf(“number found at %d position”,mid);
break;}
else if (num> arr[mid]) // x is on the right side
beg = mid + 1
else // x is on the left side
end= mid - 1
}}
Hashing
Hashing
● Linear search has a running time proportional to O(n), while binary search takes time proportional to
O(logn),where n is the number of elements in the array. Binary search is efficient algorithms than linear search
but we have to sort elements prior to binary [Link] we want to perform the search operation in time
proportional to O(1),we are using hashing. Hashing is a type of a solution which can be used in almost all
situations. Hashing is a technique which uses less key comparisons and searches the element in O(n) time in
the worst case and in an average case it will be done in O(1) time.
Hashing is the process of converting a given key into another value. A hash function is used to
generate the new value according to a mathematical algorithm. The result of a hash function is known as
a hash value or simply, a hash.
Hashing
1) Hash table

Hash table is a data structure in which keys are mapped to array positions by a hash function. A value
stored in a hash table can be searched in O(1) time using a hash function which generates an address
from the key.
Hashing
2) Hash function

A hash function is a mathematical formula which, when applied to a key, produces an integer
which can be used as an index for the key in the hash table.n this the integer returned by the hash
function is called hash key
Thus, the process of mapping keys to appropriate locations (or indices) in a hash table is called hashing.

.
Types of hash function

There are various types of hash function which are used to place the data in a hash table,
1. Division method
In this the hash function is dependent upon the remainder of a division.
For example:-if the record 52,68,99,84 is to be placed in a hash table and let us take the table size is 10.
Then:
h(key)=record% table size.
2=52%10 (reminder of 52/10)
8=68%10
9=99%10
4=84%10
Types of hash function

2. Mid square method

In this method firstly key is squared and then mid part of the result is taken as the index.
For example: consider that if we want to place a record of 3101 and the size of table is 1000. So
3101*3101=9616201 i.e. h (3101) = 162 (middle 3 digit)

3. Digit folding method

In this method the key is divided into separate parts and by using some simple operations these parts are
combined to produce a hash key. For example: consider a record of 12465512 then it will be divided into
parts i.e. 124, 655, 12. After dividing the parts combine these parts by adding it.
H(key)=124+655+12 =791
 Types of hash function

4. Multiplication Method

The steps involved in the multiplication method are as follows:

Step 1: Choose a constant A such that 0 < A < 1.
Step 2: Multiply the key k by A.
Step 3: Extract the fractional part of kA.
Step 4: Multiply the result of Step 3 by the size of hash table (m).
Hence, the hash function can be given as:
h(k) = | m (kA mod 1) |
best choice of A is 0.618033
Example Given a hash table of size 1000, map the key 12345 to an appropriate location in the hash table.
Solution We will use A = 0.618033, m = 1000, and k = 12345
h(12345) = | 1000 (12345 * 0.618033 mod 1) |
h(12345) = | 1000 (7629.617385 mod 1) |
h(12345) = | 1000 (0.617385) |
h(12345) = | 617.385 |
h(12345) = 617
Collision and Collision Resolution Techniques
There are two main approaches to handle collisions:
1. Open Hashing (Separate Chaining)
• Each table index (or slot) points to a linked list (chain) of records that hash to the same value.

• When a collision occurs, the new key is added to the linked list at that index.

Advantages:
• Simple to implement.
• Table never “fills up” — only the lists grow.
• Deletion is straightforward.

Disadvantages:
• Extra memory for pointers.
• Searching may become slow if chains are long.
Collision and Collision Resolution Techniques

Index Chain (Keys)

0 —
1 11 → 21 → 31
2 12
3 —
4 24 → 14
 Collision and Collision Resolution Techniques

2. Closed Hashing

• All elements are stored within the hash

table itself.
• When a collision occurs, a probe
sequence is used to find another empty
slot.

Common Open Addressing Methods:

1. Linear Probing
2. Quadratic Probing
3. Double Hashing
Collision and Collision Resolution Techniques

1. Linear Probing
Probe sequence:
ℎ𝑖 𝑘 = ℎ 𝑘 + 𝑖 mod 𝑚
2. Quadratic Probing
Probe sequence:
ℎ𝑖 𝑘 = ℎ 𝑘 + 𝑖 2 mod 𝑚
3. Double hashing
Two hash functions are used:
ℎ𝑖 𝑘 = ℎ1 𝑘 + 𝑖 ⋅ ℎ2 𝑘 mod 𝑚
Collision and Collision Resolution Techniques
Feature Open Hashing Closed Hashing

Outside hash table (linked

Storage Inside hash table
lists)

Collision Handling Chaining Probing

Table Full? Never Yes (can become full)
Memory Use More (pointers) Less
Deletion Easy Harder
Clustering None Possible
Sorting
INTRODUCTION TO SORTING

● Sorting means arranging the elements of an array so that they are placed in some relevant order which may be
either ascending or descending.
● That is, if A is an array, then the elements of A are arranged in a sorted order (ascending order) in such a way
that A[0] < A[1] < A[2] < ...... < A[N].
● For example, if we have an array that is declared and initialized as int A[] = {21, 34, 11, 9, 1, 0, 22};
● Then the sorted array (ascending order) can be given as: A[] = {0, 1, 9, 11, 21, 22, 34;
● A sorting algorithm is defined as an algorithm that puts the elements of a list in a certain order,which can be
either numerical order, lexicographical order, or any user-defined order.
● Efficient sorting algorithms are widely used to optimize the use of other algorithms like search and merge
algorithms which require sorted lists to work correctly. There are two types of sorting:
● Internal sorting which deals with sorting the data stored in the computer’s memory
● External sorting which deals with sorting the data stored in files.
External sorting is applied when there is voluminous data that cannot be stored in the memory.
Sorting
sort key :Data records can be sorted based on a property. Such a component or property is called a sort key. A
sort key can be defined using two or more sort keys. In such a case, the first key is called the primary sort key,
the second is known as the secondary sort key, etc.
When analysing the performance of different sorting algorithms, the practical considerations
would be the following:
● Number of sort key comparisons that will be performed
● Number of times the records in the list will be moved
● Best case performance
● Worst case performance
● Average case performance
● Stability of the sorting algorithm
Sorting

● In bubble sorting, consecutive adjacent pairs of elements in the array are compared with each other.

● Insertion sort works by moving the current data element past the already sorted values and repeatedly
interchanging it with the preceding value until it is in the correct place.

● Selection sort works by finding the smallest value and placing it in the first position. It then finds the
second smallest value and places it in the second position. This procedure is repeated until the whole array is
sorted.

● Quick sort works by using a divide-and-conquer strategy. It selects a pivot element and rearranges the
elements in such a way that all elements less than pivot appear before it and all elements greater than pivot
appear after it.
Bubble Sorting

● Bubble sort is a very simple method that sorts the array elements by repeatedly moving the
largest element to the highest index position of the array segment (in case of arranging elements
in ascending order).
● In bubble sorting, consecutive adjacent pairs of elements in the array are compared with each other.
● If the element at the lower index is greater than the element at the higher index, the two elements are
interchanged so that the element is placed before the bigger one. This process will continue till the list
become sorted.
● This procedure of sorting is called bubble sorting because elements ‘bubble’ to the top of the
list.
Bubble Sorting

BUBBLE_SORT(A[], N)

Step 1: Repeat Step 2 For I=0 to N-1

Step 2: Repeat For J=0 to N-I-1
Step 3: IF A[J] > A[J+1]
SWAP A[J] and A[J+1]
[END OF INNER LOOP]
[END OF OUTER LOOP]
Step 4: EXIT
Bubble Sorting-Program {
Bubble_sort(int arr[],int n)

#include <stdio.h> int i,j,temp;

#include <conio.h> for(i=0;i<n-1;i++)
Bubble_sort(int arr[],int n) {
int main() for(j=0;j<n–i–1;j++)
{ {
int i, n, arr[10]; if(arr[j] > arr[j+1])
clrscr(); {
printf("\n Enter the number of elements in the array :); temp = arr[j];
scanf("%d", &n);//4 arr[j] = arr[j+1]; SWAP
printf("\n Enter the elements: "); arr[j+1] = temp;
for(i=0;i<n;i++) }
scanf("%d", &arr [i]);//30 10 40 20 }
Bubble_sort(arr,n); }
printf("\n The array sorted in ascending order is :\n"); }
for(i=0;i<n;i++)
printf("%d\t", arr[i]);// 10 20 30 40 Output
getch(); Enter the number of elements in the array : 4
return 0; Enter the elements : 30 10 40 20
} The array sorted in ascending order is :
10 20 30 40
Insertion Sort

Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your
hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked
and placed at the correct position in the sorted part..
Insertion sort is less efficient as compared to other more advanced algorithms such as quick
sort, heap sort, and merge sort.
 Insertion Sort

ALGORITHM

Step 1: Repeat Steps 2 to 5 for I=1 to N

Step 2: SET TEMP = A[I]
Step 3:SET J=I
Step 4: Repeat WHILE (J > 0 && TEMP <A[J-1])
SET A[J] = A[J-1]
SET J=J-1
[END OF INNER LOOP]
Step 5: SET A[J ] = TEMP
[END OF LOOP]
Step 6: EXIT
insertion Sorting void insertion_sort(int arr[], int n)
{
#include <stdio.h> int i, j, temp;
#include <conio.h> for(i=1;i<n;i++)
int main() {
{ temp = arr[i];
int i, n, arr[10]; for(j=i; j>0 && temp < arr[j-1];j--)
clrscr(); {
printf("\n Enter the number of elements in the array : ); arr[j] = arr[j-1];
scanf("%d", &n); }
printf("\n Enter the elements: "); arr[j] = temp;
for(i=0;i<n;i++) }
{ }
scanf("%d", &arr [i]); Output
} Enter the number of elements in the array :4
insertion_sort(arr, n); Enter the elements of the array : 30 10 40 20
printf("\n The sorted array is: \n"); The sorted array is :
for(i=0;i<n;i++) 10 20 30 40
printf(" %d\t", arr[i]);
getch();
}
Selection Sort

The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering
ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two

subarrays in a given array.

1) The subarray which is already sorted.

2) Remaining subarray which is unsorted.

In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted

subarray is picked and moved to the sorted subarray.

Selection Sort
for(i=0;i<n;i++) //i=0 1 2 3
{
min=i;
for(j=i+1;j<n;j++) //j= 1 2 3 Min
{ Find
if(a[j] < a[min])
min=j; // min=1
}

temp = arr[i]; //temp=30

Swap
arr[i] = arr[min];//arr[0]=10 ping
arr[min] = temp; //arr[1]=30
}
Selection Sort void selection_sort(int arr[],int n)
{
int min,i,j, temp;
#include <stdio.h> for(i=0;i<n;i++)
#include <conio.h> {
void selection_sort(int arr[],int n) min=i;
int main() for(j=i+1;j<n;j++)
{ {
int i,n, arr[10]; if(a[j] < a[min])
clrscr(); min=j;
printf("\n Enter the number of elements : "); }
scanf("%d", &n);
printf("\n Enter the elements: ");
temp = arr[i];
for(i=0;i<n;i++)
arr[i] = arr[min];
scanf("%d", &arr [i]);
arr[min] = temp;
selection_sort(arr, n);
}
printf("\n The sorted array is: \n");
}
for(i=0;i<n;i++)
Output
printf(" %d\t", arr[i]);
Enter the number of elements : 4
getch();
Enter the elements of the array : 30 10 40 20
} The sorted array is :
10 20 30 40
 Quick Sorting
Quick sort is a widely used sorting algorithm developed by C. A. R. Hoare
Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of data into smaller
arrays. A large array is partitioned into two arrays one of which holds values smaller than the specified value,
say pivot, based on which the partition is made and another array holds values greater than the pivot value.
Quicksort partitions an array and then calls itself recursively twice to sort the two resulting subarrays. This
algorithm is quite efficient for large-sized data sets as its average and worst-case complexity are O(nLogn)
andO(n2), respectively.
Quick Sorting
 quick_sort(int arr[],int first ,int last){
Quick Sorting int i, j, pivot, temp;
if(first<last){
#include <stdio.h> pivot=first;
#include <conio.h> i=first;
Output
void Quick_sort(int arr[],int ,int) j=last;
Enter the
int main() while(i<j){ number of
{ while(arr[i]<=arr[pivot]&&i<last) elements : 4
int i,n, arr[10]; i++; Enter the
clrscr(); while(arr[j]>arr[pivot]) elements of
printf("\n Enter the number of elements : j--; the array :
"); if(i<j){ 30 10 40 20
scanf("%d", &n); temp=arr[i]; The sorted
printf("\n Enter the elements: "); arr[i]=arr[j]; Swap (arr[i],arr[j]) array is :
for(i=0;i<n;i++) arr[j]=temp; 10 20 30 40
scanf("%d", &arr [i]);
}}
quick_sort(arr, 0 , n-1) temp=arr[pivot];
printf("\n The sorted array is: \n"); Swap(arr[pivot],arr[j])
arr[pivot]=arr[j];
for(i=0;i<n;i++)
arr[j]=temp;
printf(" %d\t", arr[i]);
quicksort(arr,first,j-1);
getch();
quicksort(arr,j+1,last);
}
}}
Merge Sort
• Merge Sort is a divide and conquer sorting algorithm.

• It divides the input array into smaller parts, sorts them, and then merges them back into a single sorted array

Basic Idea
Divide: Split the array into two halves.
Conquer: Recursively sort each half.
Combine: Merge the two sorted halves into one sorted array.

Algorithm Steps
For an array A[low...high]:
If low < high
a. Find the middle index → mid = (low + high) / 2
b. Recursively sort the left half → mergeSort(A, low, mid)
c. Recursively sort the right half → mergeSort(A, mid + 1, high)
d. Merge the two halves → merge(A, low, mid, high)
Merge Sort
Merge Function

The merge() step combines two sorted subarrays into one sorted array.

Process:
Compare elements from both halves.

Copy the smaller element into a temporary array.

Continue until all elements are merged in sorted order.

Merge Sort
Example

Given array: [38, 27, 43, 3, 9, 82, 10]

Process:-

Divide:
[38, 27, 43, 3] [9, 82, 10]
→ [38, 27] [43, 3] [9, 82] [10]
→ [38] [27] [43] [3] [9] [82] [10]

Merge :

• [27, 38] [3, 43] [9, 82] [10]

• → [3, 27, 38, 43] [9, 10, 82]
• → [3, 9, 10, 27, 38, 43, 82]

Sorted Array: [3, 9, 10, 27, 38, 43, 82