Module -5: Searching & Sorting
SEARCHING TECHNIQUES
1. INTRODUCTION TO SEARCHING
Searching is the process of locating a particular element (called key) in a collection of data.
If the element is found → Successful Search.
If the element is not found → Unsuccessful Search.
Need of Searching:
1. Database record retrieval
2. File systems
3. Student record management
4. Dictionary applications
5. Compiler symbol tables
Performance Measures:
1. Number of comparisons
2. Time Complexity
3. Space Complexity
2. BASIC NOTATIONS
Let:
A[0 … n-1] → Array of size n
key → Element to be searched
pos → Position of key
n → Number of elements
Time Complexity Notations:
O(1) → Constant time
O(n) → Linear time
O(log n) → Logarithmic time
3. LINEAR SEARCH
Definition:
Linear Search is a sequential searching technique where each element is checked one by
one until the key is found.
Algorithm:
for i = 0 to n-1
if A[i] == key
return i
return -1
Example:
Array: 10, 25, 30, 45, 50
Key = 45
Comparisons: 10, 25, 30, 45 → Found at index 3
Complexity:
Best Case → O(1)
Worst Case → O(n)
Average Case → O(n)
Advantages:
Simple to implement
Works on unsorted data
No extra memory required
Disadvantages:
Inefficient for large datasets
Code for Linear Search
#include<stdio.h>
main()
{
int linearsearch(int[], int, int);
int key, n, a[50], i, pos;
printf("\n LINEAR SEARCH");
printf("\n--------------");
printf("\n size=");
scanf("%d",&n);
printf("\n Enter the Elements");
for(i=0;i<n;i++)
{
printf("\n a[%d]=",i);
scanf("%d",&a[i]);
}
printf("\n Elements to Search");
scanf("%d",&key);
pos=linearsearch(a,n,key);
if(pos==-1)
{
printf("\n %d not found",key);
}
else
{
printf("\n %d found at location %d",key,pos+1);
}
}
int linearsearch(int a[], int n, int key)
{
int i;
for(i=0; i<n; i++)
{
if(a[i]==key)
return i;
}
return-1;
}
4. BINARY SEARCH
Definition:
Binary Search is a divide-and-conquer searching technique that works only on sorted data.
Algorithm:
int binarySearch(int A[], int n, int key)
{
int low = 0, high = n - 1, mid;
while (low <= high)
{
mid = (low + high) / 2;
if (A[mid] == key)
return mid;
else if (key < A[mid])
high = mid - 1;
else
low = mid + 1;
}
return -1; // Key not found
}
Example:
Array: 10, 20, 30, 40, 50
Key = 40
Step 1: mid = 30 → Search right
Step 2: mid = 40 → Found
Complexity:
Best Case → O(1)
Worst Case → O(log n)
Average Case → O(log n)
Advantages:
Very efficient for large data
Fewer comparisons
Disadvantages:
Data must be sorted
Code for Binary Search
#include<stdio.h>
main()
{
int binsearch(int [], int,int);
int pos, key, i, n, a[50];
printf("\n BINARY SEARCH ");
printf("\n-----------------");
printf("\nEnter the Size= ");
scanf("%d", &n);
printf("\nEnter Elements in Ascending order ");
for(i=0; i<n ; i++)
{
scanf("%d",&a[i]);
if(i>0 && a[i]<a[i-1])
{
printf("\nEnter an Element greater than %d",a[i-1]);
i--;
}
}
printf("\nElement to search: ");
scanf("%d", &key);
pos=binsearch(a,n,key);
if (pos==-1)
printf("\nElement %d not found",key);
else
printf("\nElement %d found at location %d",key,pos+1);
}
int binsearch(int a[],int n,int key)
{
int low=0, high=n-1, mid;
while(low<=high)
{
mid=(low+high)/2;
if(a[mid]==key)
return mid;
else if(key>a[mid])
low=mid+1;
else
high=mid-1;
}
return -1;
}
5. HASHED LIST SEARCH (HASHING)
1. What is Hashing?
Hashing is a technique used in data structures to improve the efficiency of storing and
retrieving data from memory. Instead of searching through all elements one by one, hashing
allows us to directly access the data using a special function.
Main idea:
Convert a data value into a memory index using a hash function.
2. Why Do We Need Hashing?
Consider elements stored in memory:
12, 43, 24, 35
If we want to search for an element:
Linear Search
Checks each element one by one.
Worst case time complexity:
O(n)
Binary Search
Divides data into two halves repeatedly.
Requires sorted data.
Time complexity:
O(log n)
Hashing
Hashing directly gives the memory location of the data.
Time complexity:
O(1)
This means constant time search, which is much faster.
3. Key Idea of Hashing
In hashing, data is stored using Key–Value pairs.
Key → Generated using a hash function
Value → Actual data
Example:
Key Value
2 11
5 23
7 35
1 46
4. Hash Function
A hash function converts a data element into a hash key (or hash code).
Example:
Elements: 11, 23, 35, 46
After applying hash function:
Hash Function(element) → Hash Key
Example:
h(11) → 2
h(23) → 5
h(35) → 7
h(46) → 1
These keys represent memory locations.
5. Hash Table
A Hash Table is a fixed-size table used to store elements using hash keys.
Structure of a Hash Table:
Index Value
0
1 46
2 11
3
4
5 23
6
7 35
8
9
Important points:
Hash table has fixed size
Index usually starts from 0
Elements are stored using hash keys
6. Working of Hashing
Step 1: Take the element.
Step 2: Apply a hash function.
Step 3: Hash function generates a hash key.
Step 4: The key represents the index in the hash table.
Step 5: Store the element at that location.
7. Example
Elements: 11, 23, 35, 46
Apply hash function: h(x) = x mod 10
Results:
11 mod 10 = 1
23 mod 10 = 3
35 mod 10 = 5
46 mod 10 = 6
Hash table:
Index Value
1 11
3 23
5 35
6 46
Hashing Methods
1. Division Method
The most common method.
Formula:
h(k )=k mod m
Where
k = key value
m = size of hash table
Example:
k = 123
m = 10
123 mod 10=3
So the element is stored at index 3.
2. Mid-Square Method
Steps:
1. Square the key.
2. Extract middle digits.
3. Use those digits as the hash index.
Example:
Key = 44
2
44 =1936
Middle digits → 93 → hash address.
3. Folding Method
The key is divided into parts and then added together.
Example:
Key = 123456
Split:
123
456
Add:
123+ 456=579
So 579 becomes the hash address (or further mod with table size).
6. COMPARATIVE STUDY
Linear Search:
Works on unsorted data.
Time Complexity: O(n)
Binary Search:
Requires sorted data.
Time Complexity: O(log n)
Hashing:
Uses hash function.
Average Time Complexity: O(1)
Feature Linear Search Binary Search
Data Type Unsorted Sorted
Best Case O(1) O(1)
Average Case O(n) O(log n)
Worst Case O(n) O(log n)
Extra Space No No
Suitable For Small data Large sorted data
7. Note:
Linear Search → Simple but slow.
Binary Search → Fast but needs sorting.
Hashing → Very fast but needs extra space.
Insertion Sort
Insertion Sort is a simple sorting algorithm that works the same way you sort playing cards
in your hand. It takes one element at a time and inserts it into the correct position in the
already sorted part of the list.
Working Principle
1. Assume the first element is already sorted.
2. Take the next element.
3. Compare it with the previous elements.
4. Shift larger elements to the right.
5. Insert the element at the correct position.
6. Repeat until the entire list is sorted.
Example
Unsorted array:
83529
Step 1: 8 | 3 5 2 9
Compare 3 with 8
38|529
Step 2: Compare 5 with 8
358| 29
Step 3: Compare 2 with 8, 5, 3
2358|9
Step 4: Compare 9 with 8
23589
Sorted array obtained.
Algorithm
InsertionSort(A, n)
for i = 1 to n-1
key = A[i]
j=i-1
while j >= 0 and A[j] > key
A[j+1] = A[j]
j=j-1
A[j+1] = key
C Program
#include<stdio.h>
main()
{
void inssort(int[],int);
int n;
int a[50],b[50],i;
printf("\n INSERTION SORT");
printf("\n----------------");
printf("\n Size= ");
scanf("%d",&n);
printf("\n ARRAY ELEMENTS");
for(i=0;i<n;i++)
{
printf("\n a[%d]= ",i);
scanf("%d",&a[i]);
b[i]=a[i];
}
inssort(a,n);
printf("\n Original\t\tAscending\t\tDescending");
printf("\n-----------------------------");
for(i=0;i<n;i++)
printf("\n %d\t\t%d \t\t%d",b[i],a[i],a[n-i-1]);
}
void inssort(int a[50],int n)
{
int i,j,key;
for(i=1;i<n;i++)
{
key=a[i];
j=i-1;
while(j>=0 && a[j]>key)
{
a[j+1]=a[j];
j=j-1;
}
a[j+1]=key;
}
}
Time Complexity
Case Complexity
Best Case O(n)
Average Case O(n²)
Worst Case O(n²)
Best case occurs when the array is already sorted.
Advantages
Simple to understand
Efficient for small datasets
Works well for nearly sorted data
Stable sorting algorithm
Disadvantages
Inefficient for large datasets
Requires many comparisons and shifts
Quick Sort:
Quick Sort is a sorting technique which follows divide and conquer sorting algorithm.
It works by selecting a pivot element, placing it in its correct position, and arranging the
smaller elements to its left and larger elements to its right.
After that, the same process is recursively applied to the left and right subarrays.
Steps of Quick Sort
1. Select a pivot element from the array.
2. Partition the array so that:
Elements less than pivot go to the left.
Elements greater than pivot go to the right.
3. Place the pivot in its correct sorted position.
4. Recursively apply Quick Sort on the left and right subarrays.
Example
Unsorted Array: 38 27 43 3 9 82 10
Choose pivot = 38
After partition:
Left side (<38)
27 3 9 10
Pivot
38
Right side (>38)
43 82
Now apply quick sort again on the left and right parts.
Final Sorted Array: 3 9 10 27 38 43 82
Quick Sort Algorithm
QUICKSORT(A, low, high)
Step 1: If low < high then
Step 2: pivot = PARTITION(A, low, high)
Step 3: QUICKSORT(A, low, pivot - 1)
Step 4: QUICKSORT(A, pivot + 1, high)
Step 5: End If
Partition Algorithm
PARTITION (A, low, high)
Step 1: pivot = A[low]
Step 2: i = low + 1
Step 3: j = high
Step 4: Repeat
Step 5: while (A[i] <= pivot AND i <= high)
Step 6: i=i+1
Step 7: while (A[j] > pivot)
Step 8: j=j-1
Step 9: if (i < j)
Step 10: swap(A[i], A[j])
Step 11: until (i >= j)
Step 12: swap(A[low], A[j])
Step 13: return j
Code:
#include <stdio.h>
#include <conio.h>
main()
{
void quicksort(int[], int, int);
int a[50], b[50];
int i,n;
printf("\n QUICK SORT ");
printf("\n--------------");
printf("\nEnter the Size: ");
scanf("%d",&n);
printf("\n ARRAY ELEMENTS ");
for(i=0; i<n; i++)
{
printf("\n a[%d]= ",i);
scanf("%d",&a[i]);
b[i]=a[i];
}
quicksort(a,0,n-1);
printf("\n ORIGINAL ASCENDING DESCENDING ");
printf("\n-----------------------------------");
for(i=0; i<n; i++)
{
printf("\n %20d %20d %20d", b[i], a[i], a[n-1-i]);
}
}
void quicksort (int a[50], int l, int r)
{
int s;
int partition(int[], int, int);
if(l<r)
{
s=partition(a, l, r);
quicksort(a, l, s-1);
quicksort(a, s+1, r);
}
}
int partition (int a[50], int l, int r)
{
int p,i,j,t;
p=a[l];
i=l;
j=r+1;
while(i<j)
{
do
{
i=i+1;
}while (a[i]<p);
do
{
j=j-1;
}while (a[j]>p);
if (i<j)
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
a[l]=a[j];
a[j]=p;
return j;
}
Selection Sort
Selection Sort is a simple sorting algorithm that repeatedly selects the smallest
element from the unsorted portion of the array and places it at the correct position
in the sorted portion.
The array is divided into two parts:
1. Sorted part (initially empty)
2. Unsorted part
In each pass, the minimum element from the unsorted part is selected and swapped
with the first element of the unsorted part.
Algorithm for Selection Sort
SELECTION_SORT(A, n)
Step 1: for i = 0 to n-2
Step 2: min = i
Step 3: for j = i+1 to n-1
Step 4: if A[j] < A[min]
Step 5: min = j
Step 6: end for
Step 7: swap(A[i], A[min])
Step 8: end for
Example
Array:
64 25 12 22 11
Pass 1
Smallest element = 11
11 25 12 22 64
Pass 2
Smallest element = 12
11 12 25 22 64
Pass 3
Smallest element = 22
11 12 22 25 64
Pass 4
Smallest element = 25
11 12 22 25 64
Sorted Array:
11 12 22 25 64
Code:
#include<stdio.h>
int main()
{
int a[20], n, i, j, min, temp;
printf("Enter number of elements: ");
scanf("%d",&n);
printf("Enter elements:\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n-1;i++)
{
min = i;
for(j=i+1;j<n;j++)
{
if(a[j] < a[min])
min = j;
}
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
printf("Sorted array:\n");
for(i=0;i<n;i++)
printf("%d ",a[i]);
return 0;
}
Advantages
Easy to understand
Simple implementation
Requires less memory
Disadvantages
Slow for large datasets
Performs many comparisons
Merge Sort
Merge Sort is a divide and conquer sorting algorithm.
It divides the array into two halves, sorts each half recursively, and then merges the
sorted halves.
Steps of Merge Sort
1. Divide the array into two halves.
2. Recursively sort both halves.
3. Merge the two sorted halves into a single sorted array.
Merge Sort Algorithm
MERGE_SORT(A, low, high)
Step 1: if low < high then
Step 2: mid = (low + high) / 2
Step 3: MERGE_SORT(A, low, mid)
Step 4: MERGE_SORT(A, mid + 1, high)
Step 5: MERGE(A, low, mid, high)
Step 6: end if
Merge Procedure
MERGE(A, low, mid, high)
Step 1: i = low
Step 2: j = mid + 1
Step 3: k = low
Step 4: while (i ≤ mid and j ≤ high)
Step 5: if A[i] ≤ A[j]
Step 6: B[k] = A[i]
Step 7: i=i+1
Step 8: else
Step 9: B[k] = A[j]
Step 10: j=j+1
Step 11: k = k + 1
Step 12: Copy remaining elements of left subarray
Step 13: Copy remaining elements of right subarray
Step 14: Copy B[] back to A[]
Example
Array:
38 27 43 3 9 82 10
After dividing:
38 27 43 | 3 9 82 10
After sorting and merging:
3 9 10 27 38 43 82
Time Complexity
Case Complexity
Best O(n log n)
Average O(n log n)
Worst O(n log n)
Advantages
Stable sorting algorithm
Efficient for large datasets
Disadvantages
Requires extra memory
Exchange Sort
Exchange Sort is a simple sorting algorithm where two elements are compared and
exchanged if they are in the wrong order.
It repeatedly compares each element with the remaining elements and swaps them
when necessary.
Exchange Sort Algorithm
EXCHANGE_SORT(A, n)
Step 1: for i = 0 to n-2
Step 2: for j = i+1 to n-1
Step 3: if A[i] > A[j]
Step 4: swap(A[i], A[j])
Step 5: end if
Step 6: end for
Step 7: end for
Example
Array: 29 10 14 37 13
Pass 1: 10 29 14 37 13
Pass 2: 10 13 29 37 14
Pass 3: 10 13 14 29 37
Sorted Array: 10 13 14 29 37
Time Complexity
Case Complexity
Best O(n²)
Average O(n²)
Worst O(n²)
Advantages
Very simple to implement
Easy to understand
Disadvantages
Inefficient for large datasets