ADA

SEARCHING AND SORTING

Dr. Puneet Singh Lamba

Assistant Prof.
Dr. Puneet Singh Lamba
SGTB KHALSA COLLEGE
 Linear search program in C
#include <stdio.h>
1. Linear Search int main()
{
int array[9];
int search, c, n;
for (c = 0; c < n; c++) for(c=0;c<10;c++)
{ {
if (array[c] == search) /* If printf("Enter element”);
required element is found */
Scanf(“%d”,&array[c]);
{
printf("%d is present at location
%d.\n", search, c+1);
break;
}
}
if (c == n) scanf("%d", &n);
printf("%d isn't present in the array.\ for (c = 0; c < n; c++)
n", search);
scanf("%d", &array[c]);
return 0;
} printf("Enter a number to search\n");
scanf("%d", &search);
Complexity

Time Complexity Analysis: (In Big-O notation)

•Best Case: O(1), This will take place if the element to be searched is on
the first index of the given list. So, the number of comparisons, in this
case, is 1.
•Average Case: O(n), This will take place if the element to be searched is
on the middle index of the given list.
•Worst Case: O(n), This will take place if:
• The element to be searched is on the last index
• The element to be searched is not present on the list
 2. Binary Search
Binary Search Algorithm: The basic steps to perform Binary Search are:
•Begin with an interval covering the whole array. (Array is Sorted)
•If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half.
•Otherwise, narrow it to the upper half.
•Repeatedly check until the value is found or the interval is empty.
Binary Search

low = 0;
#include <stdio.h> high = n - 1;
int main() mid = (low+high)/2;
{ while (low <= high) {
int i, low, high, mid, n, key, if(array[mid] < key)
array[100]; low = mid + 1;
printf("Enter number of else if (array[mid] == key) {
elementsn"); printf("%d found at location %d.n", key, mid+1);
scanf("%d",&n); break;
printf("Enter %d integersn", n); }
for(i = 0; i < n; i++) else
scanf("%d",&array[i]); high = mid - 1;
printf("Enter value to findn"); mid = (low + high)/2;
scanf("%d", &key); }
if(low > high)
printf("Not found! %d isn't present in the list.n", key);
return 0;
}
Average Case Time Complexity of Binary Search
Algorithm: O(log N)
•Case1: Element is present in the array
•Case2: Element is not present in the array.
There are N Case1 and 1 Case2. So total number of cases = N+1. Now notice the following:
•An element at index N/2 can be found in 1 comparison
•Elements at index N/4 and 3N/4 can be found in 2 comparisons.
•Elements at indices N/8, 3N/8, 5N/8 and 7N/8 can be found in 3 comparisons and so on.
Based on this we can conclude that elements that require:
•1 comparison = 1
•2 comparisons = 2
•3 comparisons = 4
•x comparisons = 2x-1 where x belongs to the range [1, logN] because maximum comparisons =
maximum time N can be halved = maximum comparisons to reach 1st element = logN.
So, total comparisons
= 1*(elements requiring 1 comparisons) + 2*(elements requiring 2 comparisons) + . . . +
logN*(elements requiring logN comparisons)
= 1*1 + 2*2 + 3*4 + . . . + logN * (2logN-1)
= 2logN * (logN – 1) + 1
= N * (logN – 1) + 1
Total number of cases = N+1.
Therefore, the average complexity = (N*(logN – 1) + 1)/N+1 = N*logN / (N+1) + 1/(N+1).
Here the dominant term is N*logN/(N+1) which is approximately logN. So the average case
3. 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.
Algorithm
To sort an array of size n in ascending order:
1: Iterate from arr[1] to arr[n] over the array.
2: Compare the current element (key) to its
predecessor.
3: If the key element is smaller than its
predecessor, compare it to the elements before.
Move the greater elements one position up to
make space for the swapped element.
Insertion Sort
Loop invariants help us understand why an algorithm is
correct. When you’re using a loop invariant, you need to
show three things:

Initialization: It is true prior to the first iteration of the

loop.

Maintenance: If it is true before an iteration of the

loop, it remains true before the next iteration.

Termination: The loop terminates, and when it

terminates, the invariant usually along with the reason
that the loop terminated gives us a useful property that
helps show that the algorithm is correct.
Bubble Sort
Bubble sort
Bubble Sort
Selection Sort
 Selection Sort
Selection sort program in C for (c = 0; c < (n - 1); c++)
#include <stdio.h>
int main() {
{
position = c;
int array[100], n, c, d, position, t;
printf("Enter number of elements\n"); for (d = c + 1; d < n; d++)
scanf("%d", &n); {
printf("Enter %d integers\n", n); if (array[position] > array[d])
for (c = 0; c < n; c++) position = d;
scanf("%d", &array[c]); }
if (position != c)
{
t = array[c];
array[c] = array[position];
array[position] = t;
}
}
printf("Sorted list in ascending order:\
n");
for (c = 0; c < n; c++)
printf("%d\n", array[c]);
return 0;
}
Time Complexity Analysis of Selection Sort:
•Best-case: O(n2), best case occurs when the array is already sorted. (where
n is the number of integers in an array)
•Average-case: O(n2), the average case arises when the elements of the array
are in a disordered or random order, without a clear ascending or descending
pattern.
•Worst-case: O(n2), The worst-case scenario arises when we need to sort an
array in ascending order, but the array is initially in descending order.
 Heap sort
• Heap sort processes the elements by creating the min-heap or max-heap using
the elements of the given array.

• Min-heap or max-heap represents the ordering of array in which the root element
represents the minimum or maximum element of the array.

• Max heap is a complete binary tree. A complete binary tree is a binary tree in
which all levels are completely filled and all the nodes in the last level are as left
as possible.

• also meets this criteria: the parent’s key is larger than both children’s keys. The
Max heap should largest value is at the root. Heap is related to priority Heap sort

queue and heapsort.

Heap sort basically recursively performs two main operations -
Algorithm 1: Algorithm 2:
•Build a heap H, using the elements of array. Insertion Heapify +
•Repeatedly delete the root element of the heap formed in 1 st phase. +Deletion Deletion
Dr. Puneet Singh Lamba
 Algorithm1: Max Heap Construction Algorithm
We shall use the same example to demonstrate how a Max Heap is created. The procedure to create Min Heap is
similar but we go for min values instead of max values. We are going to derive an algorithm for max heap by inserting
one element at a time. At any point of time, heap must maintain its property.

While insertion, we also assume that we are inserting

a node in an already heapified tree.
Step 1 − Create a new node at the end of heap.
Step 2 − Assign new value to the node.
Step 3 − Compare the value of this child node with its
parent.
Step 4 − If value of parent is less than child, then swap
them.
Step 5 − Repeat step 3 & 4 until Heap property holds.
Dr. Puneet Singh Lamba
 Heap: Insertion of node

Dr. Puneet Singh Lamba

Max Heap Deletion Algorithm

Let us derive an algorithm to delete from max heap.

Deletion in Max (or Min) Heap always happens at the
root to remove the Maximum (or minimum) value.
Step 1 − Remove root node.
Step 2 − Move the last element of last level to root.
Step 3 − Compare the value of this child node with its
parent.
Step 4 − If value of parent is less than child, then swap
them.
Step 5 − Repeat step 3 & 4 until Heap property holds.

Dr. Puneet Singh Lamba

After Inserting all
the node,
Deletion Starts
with root node

Dr. Puneet Singh Lamba

Dr. Puneet Singh Lamba
Algotithm-2 (part 1:Heapify )

• Create a complete tree with a given array

• Start with last leaf node parent.
• At parent node check the max heap node
conditions.
• now after the adjustment go to second last
leaf node and find the parent and apply
heapify method and so on…

Dr. Puneet(part
Algotithm-2 Singh2:Delete
Lambaprocedure is same, refer previous slided)
Max-heap implementation – Insertion algorithm

Dr. Puneet Singh Lamba

 Heap Sort
• Advantages of heapsort:
• Efficiency – The time required to perform Heap sort increases logarithmically
while other algorithms may grow exponentially slower as the number of items to
sort increases. This sorting algorithm is very efficient.
• Memory Usage – Memory usage is minimal because apart from what is necessary
to hold the initial list of items to be sorted, it needs no additional memory space to
work
• Simplicity – It is simpler to understand than other equally efficient sorting
algorithms because it does not use advanced computer science concepts such as
recursion

Dr. Puneet Singh Lamba

Deletion

Dr. Puneet Singh Lamba

Dr. Puneet Singh Lamba
HEAPIFY

Dr. Puneet Singh Lamba

Dr. Puneet Singh Lamba
Dr. Puneet Singh Lamba
 • Viewing a heap as a tree, we define the height of a node in a heap to be the
number of edges on the longest simple downward path from the node to a
leaf, and we define the height of the heap to be the height of its root. Since a
heap of n elements is based on a complete binary tree, its height is theta(lg n)
• As we’ll see, the basic operations on heaps run in time at most proportional to
the height of the tree and thus take O(lg n) time.
• The MAX-HEAPIFY procedure, which runs in O(lg n) time, is the key to
maintaining the max-heap property.
• The BUILD-MAX-HEAP procedure, which runs in linear time, produces a
maxheap from an unordered input array.
• The HEAPSORT procedure, which runs in O(n lg n) time, sorts an array in place.

Dr. Puneet Singh Lamba

 Count Sort

Dr. Puneet Singh Lamba

Dr. Puneet Singh Lamba
 Radix sort
The algorithm is named radix sort as it specifies the radix r to be used which
changes how the sort is performed. The radix, or base, of the number system is
the number of digits that represent a single position in the number; a radix of 2
is binary (0-1), 10 is decimal (0-9), 16 is hexadecimal (0-F) and so on. Radix
Sort is a linear sorting algorithm. The algorithm based on idea that sorting the
elements by first grouping the individual digits of the same place value. Radix
sort depends on the digits or letters, so it is less flexible than other sorts.
Radix Sort Algorithm
[Link] the least significant digit of each element.
[Link] the list of elements based on that digit, but keep the order of elements
with the same digit.
[Link] the sort with each more significant digit.
The speed of the Radix sort depends on the inner basic operations.
If the operations are not efficient enough, Radix sort can be slower than other
algorithms such as Quick Sort and Merge Sort.
Dr. Puneet Singh Lamba
[Link]
Radix sort

Advantages of Radix Sort

[Link] when the keys are short i.e when the range of the array elements is less.
[Link] in suffix array construction algorithms like Manber’s algorithm and DC3
algorithm.
Disadvantages of Radix Sort
[Link] Sort depends on digits or letters, so it is less flexible than other sorts.
[Link] constant for Radix sort is greater compared to other sorting algorithms.
[Link] takes more space compared to Quick sort which is inplace sorting.

Dr. Puneet Singh Lamba

 Radix Sort

Dr. Puneet Singh Lamba

 Bucket Sort

Dr. Puneet Singh Lamba

Dr. Puneet Singh Lamba
Summary of Sorting
Algorithms
Algorithm Time Notes
 in-place
selection-sort O(n2)  slow (good for small inputs)

 in-place
insertion-sort O(n2)  slow (good for small inputs)

quick-sort O(n log n)  in-place, randomized

expected  fastest (good for large inputs)

 in-place
heap-sort O(n log n)  fast (good for large inputs)

 sequential data access

merge-sort O(n log n)  fast (good for huge inputs)

Dr. Puneet Singh Lamba

 Algorithm Time Complexity
Best Average Worst
Selection Sort Ω(n^2) θ(n^2) O(n^2)
Bubble Sort Ω(n) θ(n^2) O(n^2)
Insertion Sort Ω(n) θ(n^2) O(n^2)
Heap Sort Ω(n log(n)) θ(n log(n)) O(n log(n))
Quick Sort Ω(n log(n)) θ(n log(n)) O(n^2)
Merge Sort Ω(n log(n)) θ(n log(n)) O(n log(n))

Dr. Puneet Singh Lamba

Divide and Conquer
 Merge Sort: Divide-and-Conquer
• Divide and Conquer is more than just a military strategy; it is also a method
of algorithm design that has created such efficient algorithms as Merge Sort.

• In terms or algorithms, this method has three distinct steps:

• Divide: If the input size is too large to deal with in a straightforward

manner, divide the data into two or more disjoint subsets.
• Recur: Use divide and conquer to solve the subproblems associated
with the data subsets.
• Conquer: Take the solutions to the subproblems and “merge” these
solutions into a solution for the original problem.

Merge sort is one of the efficient & fastest sorting algorithms with the following time complexity:
Worst Case Time Complexity: O(n*logn)
Best Case Time Complexity: O(n*log n)
Dr. Puneet Singh Lamba Average Time Complexity: O(n*log n)
Given: Arr(5, 8, 3, 9, 1, 2)
•We split the array into two halves Arr1 = (5, 8, 3) and Arr2 = (9, 1, 2).
•Again, we divide them into two halves: Arr3 = (5, 8) and Arr4 = (3) and
Arr5 = (9, 1) and Arr6 = (2)
•Again, we divide them into two halves: Arr7 = (5), Arr8 = (8), Arr9 =
(9), Arr10 = (1) and Arr6 = (2)
•We will now compare the elements in these sub arrays in order to
merge them.
Merge Sort Algorithm:
step 1: start

step 2: declare array and left, right, mid variable

step 3: perform merge function.

if left > right
return
mid= (left+right)/2
mergesort(array, left, mid)
mergesort(array, mid+1, right)
merge(array, left, mid, right)

step 4: Stop
Merge Sort
Merge Sort
MERGE
#include <stdio.h> void sort(int low, int high) { void merging(int low, int mid, int high)
#define max 10 int mid; {
int a[11] = { 10, 14, 19, 26, 27, int l1, l2, i;
31, 33, 35, 42, 44, 0 };
if(low < high) { for(l1 = low, l2 = mid + 1, i = low; l1
int b[10]; <= mid && l2 <= high; i++) {
int main() mid = (low + high) / 2;
if(a[l1] <= a[l2])
{ sort(low, mid);
b[i] = a[l1++];
int i; sort(mid+1, high); else
printf("List before sorting\ merging(low, mid, high);
n"); b[i] = a[l2++];
} else { }
for(i = 0; i <= max; i++)
printf("%d ", a[i]);
return; while(l1 <= mid)
} b[i++] = a[l1++];

sort(0, max); } while(l2 <= high)

printf("\nList after sorting\ b[i++] = a[l2++];
n");
for(i = low; i <= high; i++)
for(i = 0; i <= max; i++)
a[i] = b[i];
printf("%d ", a[i]);
}
}
 Quick Sort

QuickSort is a Divide and Conquer algorithm. It

picks an element as a pivot and partitions the
given array around the picked pivot. There are
many different versions of quick Sort that pick
pivot in different ways.
•Always pick the first element as a pivot.
•Always pick the last element as a pivot
(implemented below)
•Pick a random element as a pivot.
•Pick median as the pivot.

[Link]
Dr. Puneet Singh Lamba
int main()
Quick Sort #include <stdio.h>
void swap(int *p, int *q)
{
int n, i; {
void quickSort(int a[], int low, int high) int temp = *p;
printf("What is the size of the
{ *p = *q;
array?\n");
if (low < high) *q = temp;
scanf("%d",&n);
{ }
int a[n]; int k = partition(a, low, high); int partition(int a[], int low, int high)
printf("Enter elements of quickSort(a, low, k - 1); {
the array one by one\n"); quickSort(a, k + 1, high); int pivot = a[high];
for(i = 0; i < n; i++) } int i = (low - 1);
{ }
for (int j = low; j <= high- 1; j++)
scanf("\n%d",&a[i]); {
void print(int a[], int size)
} if (a[j] <= pivot)
{
{
quickSort(a, 0, n - 1);
int i;
i++;
printf("Sorted array: "); for (i = 0; i < size; i++)
swap(&a[i], &a[j]);
print(a, n); printf("%d ", a[i]);
}
return 0; printf("\n");
}
} }
swap(&a[i + 1], &a[high]);
return (i + 1);
}

Dr. Puneet Singh Lamba

Quick Sort Algorithm
[Link] divide-and-conquer strategy is used in quicksort. Below the recursion step is described: Choose a pivot value. We take the value of the middle element as

pivot value, but it can be any value, which is in range of sorted values, even if it doesn't present in the array.

[Link]. Rearrange elements in such a way, that all elements which are lesser than the pivot go to the left part of the array and all elements greater than the

pivot, go to the right part of the array. Values equal to the pivot can stay in any part of the array. Notice, that array may be divided in non-equal parts.

[Link] both parts. Apply quicksort algorithm recursively to the left and the right parts.

The algorithm rearranges the unsorted list by picking a pivot value and rearranging the list so that values that are lower than the pivot value are positioned before

it in the list, and values that are higher than the pivot value are positioned after it in the list. To rearrange the values, the low mark and high mark are used.

4. As the list is checked, the low mark is moved up over values that are lower than the pivot value. Once the low mark reaches a value that is higher than the

pivot value, it stops in that place and the algorithm proceeds to examine the high mark.

5. The high mark is moved down over values that are higher than the pivot value. If the high mark reaches a value that is lower than the pivot value, the

algorithm swaps the values of the low mark and the high mark.

6. The process continues until the high mark overlaps with the low mark, which indicates the new position for the pivot value. Sometimes the pivot value is

already
Dr. in Singh
Puneet that position.
Lamba
 Matrix Multiplication

Dr. Puneet Singh Lamba

 Divide
Step

Dr. Puneet Singh Lamba

 Divide and
Conquer

Dr. Puneet Singh Lamba

Dr. Puneet Singh Lamba
 Strassen Multiplication

Dr. Puneet Singh Lamba