Data Structures

Searching
 Searching
Searching refers to the process of finding the required
information from a collection of items stored as elements
in the computer memory.

These sets of items are in different forms, such as an array,

linked list, graph, or tree.

2
 Searching

Interenal searching External searching

B tree searching

B+ tree searching

Search with key-comparison Search without key-comparison

Adress calculation search

Linear search Non-linera search

Sequential search Tree search

Binary search Binary search tree

Interpolation search AVL tree search

Red-black tree search

Splay tree search

Digital search

Multi-way tree search

m-way tree search

B-tree search

Graph search

Depth first search

Breadth first search 3

 Linear Search
The linear search algorithm iteratively searches all
elements of the array.
It has the best execution time of one and the worst
execution time of n, where n is the total number of items
in the search array.
It is the simplest search algorithm in data structure and
checks each item in the set of elements until it matches the
searched element till the end of data collection.
When the given data is unsorted, a linear search algorithm
is preferred over other search algorithms.

4
Flowchart: Sequential Search with Array
Start

i=0

Yes No
K = A[i]?

i = i+1

No
Print "Successful" i≥n
Yes

Print "Unsuccessful"

Stop

5
Example: Sequential Search with Array
int main()
{
int A[10], i, n, K, flag = 0;
printf("Enter the size of an array: ");
scanf("%d",&n);

printf("Enter the elements of the array: ");

for(i=0; i < n; i++)
scanf("%d",&A[i]);
printf("Enter the number to be searched: ");
scanf("%d",&K);
for(i=0;i<n;i++){
if(a[i] == K){
flag = 1; break;
}
}
if(flag == 0)
printf("The number is not in the list");
else
printf("The number is found at index %d",i);
return 0;
}

6
Complexity Analysis

• Case 1: The key matches with the first element

• T(n) = 1
• Case 2: Key does not exist
• T(n) = n
• Case 3: The key is present at any location in the
n

array T (n) =  p  i
i =1
i

1 n
T ( n) =  i p1 = p 2 =    pi =    p n =
1
n i =1 n
n +1
T ( n) =
2
7
Complexity Analysis : Summary

Number of key Asymptotic

Case Remark
comparisons complexity

Case 1 T(n) = 1 T(n) = O(1) Best case

Case 2 T(n) = n T(n) = O(n) Worst case

n +1
Case 3 T ( n) = T(n) = O(n) Average case
2

8
 Binary Search
Binary search needs sorted order of items of the array.
This algorithm looks for specific items by comparing the
middlemost items in the data collection.
When a match is found, it returns the item’s index.
When the middle item is greater than the search item, it
looks for a central item of the left sub-array. If, on the
other hand, the middle item is smaller than the search
item, it explores the middle item in the right sub-array.
It keeps looking for an item until it finds it or the size of
the sub-arrays reaches zero.
It works faster than a linear search algorithm. The binary
9
search uses the divide and conquer principle.
The Technique

mid
mid

l l u mid = l(l+u)/2
= mid-1 = mid+1 uu
Serach this half the same way Serach this half the same way
if K < A[mid] if K > A[mid]

(c) Search
(a)
(b)An the
Searchentire
ordered list turns
the array
entire into the
oflistelemnets
turns searching
with
into theindex of right-half
values
searching u andonly
of l,left-half
mid
only

10
Flowchart: Binary Search with Array
Start

mid = (l+u)/2

YES NO
K = A[mid]?

YES NO
K < A[mid]?

Search is successful
u = mid-1 l = mid+1

Stop
NO
(l>u)?

YES

Search is unsuccessful

Start

11
Binary Search (with Iteration)
#include <stdio.h>

int main()
{
int i, l, u, mid, n, K, data[100];

printf("Enter number of elements\n");

scanf("%d",&n);

printf("Enter %d integers in sorted order\n", n);

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

scanf("%d",&array[i]);

printf("Enter value to find\n");

scanf("%d", &K);

l = 0;
u = n - 1;
Contd…
mid = (l+u)/2;

12
Binary Search (with Iteration)
while (l <= u) {
if (data[mid] < K)
l = mid + 1;
else if (data[mid] == K) {
printf("%d found at location %d.\n", search, mid+1);
break;
}
else
u = mid - 1;

mid = (l + u)/2;
}
if (l > u)
printf("Not found! %d is not present in the list.\n", K);

return 0;
}

13
Binary Search (with Recursion)
#include<stdio.h>
int main(){

int data[100],i, n, K, flag, l, u;

printf("Enter the size of an array: ");

scanf("%d",&n);

printf("Enter the elements of the array in sorted order: " );

for(i=0;i<n;i++)
scanf("%d",&a[i]);

printf("Enter the number to be search: ");

scanf("%d",&K);

l=0,u=n-1;
flag = binarySearch(data,n,K,l,u);
if(flag==0)
printf("Number is not found.");
else
Contd…
printf("Number is found.");

return 0;
}
14
Binary Search (with Recursion)
int binary(int a[],int n,int K,int l,int u){

int mid;

if(l<=u){
mid=(l+u)/2;
if(K==a[mid]){
return(1);
}
else if(m<a[mid]){
return binarySearch(a,n,K,l,mid-1);
}
else
return binarySearch(a,n,m,mid+1,u);
}
else return(0);
}

15
Complexity Analysis

5
< = >

2 8
< = > < = >

1 3 6 9
< = > < = > < = > < = >

F F F 4 F 7 F 10
< = > < = > < = >

F F F F F F

16
Complexity Analysis: Binary Search
5
< = >

2 8
< = > < = >

1 3 6 9
< = > < = > < = > < = >

F F F 4 F 7 F 10
< = > < = > < = >

F F F F F F

Let n be the total number of elements in the list under search and there exist an
integer k such that:-
• For successful search:-
• If 2k-1 <= n <2k, then the binary search algorithm requires at least one comparison and
at most k comparisons.
• For unsuccessful search:-
• If n = 2k-1, then the binary search algorithm requires k comparisons.
• If 2k-1 <= n < 2k-1then the binary search algorithm requires either k-1 or k number of
comparisons.
17
Interpolation Search

20
• Interpolation search is an improved variant of binary search.
• This search algorithm works on the probing position of the
required value.
• For this algorithm to work properly, the data collection should be
in a and
• Binary search has a huge advantage of time complexity over
linear search. Linear search has worst-case complexity of Ο(n)
whereas binary search has Ο(log n).
• There are cases where the location of target data may be known
in advance. For example, in case of a telephone directory, if we
want to search the telephone number of Vijay. Here, linear search
and even binary search will seem slow as we can directly jump to
memory space where the names start from 'V' are stored. 21
Interpolation Search
1. l = 1, u = n // Initialization: Range of searching
2. flag = FALSE // Hold the status of searching
3. While (flag = FALSE) do
 K − A[l ] 
4. loc =    (u − l ) + l
 A[u ] − A [l ] 
5. If ( l  loc  u) then // If loc is within the range of the list
6. Case: K < A[loc]
7. u = loc -1
8. Case: K = A[loc]
9. flag = TRUE
10. Case: K > A[loc]
11. l = loc +1
12. Else
13. Exit()
14. EndIf
15. EndWhile
16. If (flag) then
17. Print “Successful at” loc
18. Else
19. Print “Unsuccessful”
20. EndIf
21. Stop

22
Sequential Search with Linked List

26
Sequential Search with Linked List

DATA LINK

(a) Structure of a node in the linked list

Header
Search at an intermediate node:
Search begins Search stops here if key matches Search unsuccessfully ends here
here else move to its immediate next node

(b) Linear search on a linked list

27
Flow Chart: Sequential Search with LL
Start

temp = header

while
Print Unsuccessful
temp != NULL
temp = temp->next
T
N temp->data == Y
key

Print Success
Return temp

28
Example: Sequential Search with LL
#include <stdio.h>
#include <stdlib.h>

struct node
{
int data;
struct node *next;
};

int main()
{
struct node *header = NULL;
int K, n;

printf("Enter the number of nodes: ");

scanf("%d", &n);
printf("\nDisplaying the list\n");
generate(header, num);
printf("\nEnter key to search: ");
scanf("%d", &key);
searchBinary(header, K);
delete(header);

return 0;
}

29
Example: Linear Search with LL
void generate(struct node *head, int n)
{
int i;
struct node *temp;

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

{
temp = (struct node *)malloc(sizeof(struct node));
temp->data = rand() % n;
if (*head == NULL)
{
*head = temp;
temp->next = NULL;
}
else
{
temp->next = head;
head = temp;
}
printf("%d ", temp->data);
}
}

30
Example: Linear Search with LL
void searchBinary(struct node *temp, int K)
{
while (temp != NULL)
{
if (temp->data == K)
{
printf("key found\n");
return;
}
else temp = temp->next;
}
printf("Key not found\n");
}

void delete(struct node *header)

{
struct node *temp;
temp = header;
while (temp != NULL)
{
temp = temp->next;
free(header);
header = temp;
}
}

31
Complexity Analysis

Number of key
Case Asymptotic complexity Remark
comparisons

Case 1 T(n) = 1 T(n) = O(1) Best case

n +1
Case 2 T ( n) = T(n) = O(n) Average case
2

Case 3 T(n) = n T(n) = O(n) Worst case

32
• Like Binary Search, Jump Search is a searching algorithm for
sorted arrays.
• The basic idea is to check fewer elements (than linear search) by
jumping ahead by fixed steps or skipping some elements in place
of searching all elements.
• For example, suppose we have an array arr[] of size n and block
(to be jumped) size m. Then we search at the indexes arr[0],
arr[m], arr[2m]…..arr[km] and so on. Once we find the interval
(arr[km] < x < arr[(k+1)m]), we perform a linear search operation
from the index km to find the element x.

33
• Let’s consider the following array: (0, 1, 1, 2, 3, 5, 8, 13, 21, 34,
55, 89, 144, 233, 377, 610). Length of the array is 16. Jump
search will find the value of 55 with the following steps assuming
that the block size to be jumped is 4.
• STEP 1: Jump from index 0 to index 4;
• STEP 2: Jump from index 4 to index 8;
• STEP 3: Jump from index 8 to index 12;
• STEP 4: Since the element at index 12 is greater than 55 we will
jump back a step to come to index 8.
• STEP 5: Perform linear search from index 8 to get the element
55.

34
• What is the optimal block size to be skipped?
• In the worst case, we have to do n/m jumps and if the last
checked value is greater than the element to be searched for, we
perform m-1 comparisons more for linear search. Therefore the
total number of comparisons in the worst case will be ((n/m) + m-
1). The value of the function ((n/m) + m-1) will be minimum
when m = √n. Therefore, the best step size is m = √n.
• So Time Complexity : O(√n)

35
• It is combination of Jump and Binary search
• Exponential search involves two steps:
– Find range where element is present
– Do Binary Search in above found range.
• To find the range where element may be present, start with
subarray size 1, compare its last element with K, then try size 2,
then 4 and so on until last element of a subarray is not greater
than K.
• Once an index i is found (after repeated doubling of i), the
element must be present between i/2 and i (Why i/2? because we
could not find a greater value in previous iteration)
• Perform Binary search on the range i/2 to i
36
• It works better than Binary Search for bounded arrays, and also
when the element to be searched is closer to the first element.
• Time Complexity : O(Log n)

37
Data Structures
Sorting
Sorting – The Task
• Given an array
x[0], x[1], … , x[size-1]
reorder entries so that
x[0] <= x[1] <= . . . <= x[size-1]

Here, List is in non-decreasing order.

• We can also sort a list of elements in non-increasing order.

39
Sorting – Example
• Original list:
– 10, 30, 20, 80, 70, 10, 60, 40, 70

• Sorted in non-decreasing order:

– 10, 10, 20, 30, 40, 60, 70, 70, 80

• Sorted in non-increasing order:

– 80, 70, 70, 60, 40, 30, 20, 10, 10

40
Sorting Problem
• What do we want :
- Data to be sorted in order

0 size-1
x: Unsorted list

Sorted list

41
Issues in Sorting
Many issues are there in sorting techniques
• How to rearrange a given set of data?
• Which data structures are more suitable to store data prior
to their sorting?
• How fast the sorting can be achieved?
• How sorting can be done in a memory constraint situation?
• How to sort various types of data?

42
Sorting Algorithms

43
Sorting by Comparison
• Basic operation involved in this type of sorting
technique is comparison. A data item is compared
with other items in the list of items in order to find
its place in the sorted list.
• Insertion
• Selection
• Exchange
• Enumeration

44
Sorting by Comparison
Sorting by comparison – Insertion:
• From a given list of items, one item is considered at a time.
The item chosen is then inserted into an appropriate position
relative to the previously sorted items. The item can be
inserted into the same list or to a different list.
e.g.: Insertion sort
Sorting by comparison – Selection:

• First the smallest (or largest) item is located and it is separated

from the rest; then the next smallest (or next largest) is
selected and so on until all item are separated.
e.g.: Selection sort, Heap sort

45
Sorting by Comparison
Sorting by comparison – Exchange:

• If two items are found to be out of order, they are

interchanged. The process is repeated until no more exchange
is required.
e.g.: Bubble sort, Shell Sort, Quick Sort
Sorting by comparison – Enumeration:
• Two or more input lists are merged into an output list and
while merging the items, an input list is chosen following the
required sorting order.
e.g.: Merge sort

46
Sorting by Distribution
• No key comparison takes place
• All items under sorting are distributed over an auxiliary storage
space based on the constituent element in each and then grouped
them together to get the sorted list.
• Distributions of items based on the following choices
✓ Radix - An item is placed in a space decided by the
bases (or radix) of its components with which it is
composed of.
✓ Counting - Items are sorted based on their relative counts.
✓ Hashing - Items are hashed, that is, dispersed into a list
based on a hash function.
Note: This lecture concentrates only on sorting by comparison.

47
Insertion Sort

48
Insertion Sort
General situation :
0 i size-1
x: smallest elements, sorted remainder, unsorted

i Compare and
Shift till x[i] is
larger.
i

0 j
size-1

49
Insertion Sort
void insertionSort (int list[], int size)
{
int i,j,item;

for (i=1; i<size; i++)

{
item = list[i] ;
/* Move elements of list[0..i-1], that are greater than
item, to one position ahead of their current position */

for (j=i-1; (j>=0)&& (list[j] > item); j--)

list[j+1] = list[j];
list[j+1] = item ;
}
}

50
Insertion Sort
int main()
{
int x[ ]={-45,89,-65,87,0,3,-23,19,56,21,76,-50};

int i;
for(i=0;i<12;i++)
printf("%d ",x[i]);
OUTPUT
printf("\n");
-45 89 -65 87 0 3 -23 19 56 21 76 -50
insertionSort(x,12);
-65 -50 -45 -23 0 3 19 21 56 76 87 89
for(i=0;i<12;i++)
printf("%d ",x[i]);
printf("\n");
}

51
Insertion Sort - Example

52
Insertion Sort: Complexity Analysis
Case 1: If the input list is already in sorted order

Number of comparisons: Number of comparison in each

iteration is 1.

𝐶 𝑛 = 1 + 1 + 1 + ⋯ + 1 upto (n-1)th iteration.

Number of movement: No data movement takes place in any

iteration.
𝑀 𝑛 =0

53
Insertion Sort: Complexity analysis
Case 2: If the input list is sorted but in reverse order
Number of comparisons: Number of comparison in each
iteration is 1.
𝑛(𝑛 − 1)
𝐶 𝑛 = 1 + 2 +3 +⋯+ 𝑛 − 1 =
2
Number of movement: Number of movements takes place in
any ith iteration is i.
𝑛(𝑛 − 1)
𝑀 𝑛 = 1 + 2 + 3 + ⋯+ 𝑛 − 1 =
2

54
Insertion Sort: Complexity analysis
Case 3: If the input list is in random order
• Let 𝑝𝑗 be the probability that the key will go to the 𝑗𝑡ℎ location
(1 ≤ 𝑗 ≤ 𝑖 + 1). Then the number of comparisons will be 𝑗 ∙ 𝑝𝑗 .

• The average number of comparisons in the (i + 1)𝑡ℎ iteration is

𝑖+1

𝐴𝑖+1 = ෍ 𝑗 ∙ 𝑝𝑗
𝑗=1

• Assume that all keys are distinct and all permutations of keys are
equally likely.
1
𝑝1 = 𝑝2 = 𝑝3 = ⋯ = 𝑝𝑖+1 =
𝑖+1

55
Insertion Sort: Complexity analysis
Case 3: Number of comparisons
• Therefore, the average number of comparisons in the (i +
1)𝑡ℎ iteration
𝑖+1
1 1 𝑖+1 ∙ 𝑖+2 𝑖+2
𝐴𝑖+1 = ෍𝑗 = ∙ =
𝑖+1 𝑖+1 2 2
𝑗=1

• Total number of comparisons for all (𝑛 − 1) iterations is

𝑛−1
1 𝑛 𝑛−1
𝐶 𝑛 = ෍ 𝐴𝑖+1 = ∙ + (𝑛 − 1)
2 2
𝑖=0

56
Insertion Sort: Complexity analysis
Case 3: Number of Movements
• On the average, number of movements in the 𝑖𝑡ℎ iteration

𝑖 + 𝑖 − 1 + 𝑖 − 2 + ⋯+ 2 + 1 𝑖 + 1
𝑀𝑖 = =
𝑖 2

• Total number of movements

𝑛−1
1 𝑛 𝑛−1 𝑛−1
𝑀 𝑛 = ෍ 𝑀𝑖 = ∙ +
2 2 2
𝑖=1

57
Insertion Sort: Summary of Complexity Analysis
Case Comparisons Movement Memory Remarks
Case 1 C 𝑛 = (𝑛 − 1) 𝑀 𝑛 =0 𝑆 𝑛 =𝑛 Input list is in sorted
order
Case 2 𝑛(𝑛 − 1) 𝑛(𝑛 − 1) 𝑆 𝑛 =𝑛 Input list is sorted in
C 𝑛 = 𝑀 𝑛 =
2 2 reverse order

Case 3 (𝑛 − 1)(𝑛 + 4) (𝑛 − 1)(𝑛 + 2) 𝑆 𝑛 =𝑛 Input list is in random

C 𝑛 = 𝑀 𝑛 =
4 4 order

Case Run time, 𝑻(𝒏) Complexity Remarks

Case 1 𝑇 𝑛 = 𝑐 (𝑛 − 1) 𝑇 𝑛 = 𝑂(𝑛)
Best case

Case 2 𝑇 𝑛 = 𝑐 𝑛(𝑛 − 1) 𝑇 𝑛 = 𝑂(𝑛2 ) Worst case

Case 3 (𝑛 − 1)(𝑛 + 3) 𝑇 𝑛 = 𝑂(𝑛2 )

𝑇 𝑛 =𝑐 Average case
2

58
Selection Sort

59
Selection Sort
General situation :
0 k size-1
x: smallest elements, sorted remainder, unsorted

Steps :
• Find smallest element, mval, in x[k…size-1]
• Swap smallest element with x[k], then increase k.

0 k mval size-1
x:

swap

60
Selection Sort
/* Yield location of smallest element in
x[k .. size-1];*/

int findMinLloc (int x[ ], int k, int size)

{
int j, pos; /* x[pos] is the smallest
element found so far */
pos = k;
for (j=k+1; j<size; j++)
if (x[j] < x[pos])
pos = j;
return pos;
}

61
Selection Sort
/* The main sorting function */
/* Sort x[0..size-1] in non-decreasing order */

int selectionSort (int x[], int size)

{ int k, m;
for (k=0; k<size-1; k++)
{
m = findMinLoc(x, k, size);
temp = a[k];
a[k] = a[m];
a[m] = temp;
}
}

62
Selection Sort - Example
x: 3 12 -5 6 142 21 -17 45 x: -17 -5 3 6 12 21 142 45

x: -17 12 -5 6 142 21 3 45 x: -17 -5 3 6 12 21 45 142

x: -17 -5 12 6 142 21 3 45 x: -17 -5 3 6 12 21 45 142

x: -17 -5 3 6 142 21 12 45

x: -17 -5 3 6 142 21 12 45

x: -17 -5 3 6 12 21 142 45

63
Selection Sort: Complexity Analysis
Case 1: If the input list is already in sorted order
Number of comparisons:
𝑛−1
𝑛(𝑛 − 1)
𝐶 𝑛 = ෍ 𝑛−𝑖 =
2
𝑖=1

Number of movement: no data movement takes place in any

iteration.
𝑀 𝑛 =0

64
Selection Sort: Complexity Analysis
Case 2: If the input list is sorted but in reverse order
Number of comparisons:
𝑛−1
𝑛(𝑛 − 1)
𝑐 𝑛 = ෍ 𝑛−𝑖 =
2
𝑖=1

Number of movements:
3
𝑀 𝑛 = (𝑛 − 1)
2

65
Selection Sort: Complexity Analysis
Case 3: If the input list is in random order
Number of comparisons:
𝑛(𝑛 − 1)
𝐶 𝑛 =
2
• Let 𝑝𝑖 be the probability that the 𝑖𝑡ℎ smallest element is in the 𝑖𝑡ℎ
position. Number of total swap operations = (1 − 𝑝𝑖 ) × (𝑛 − 1)
1
where 𝑝1 = 𝑝2 = 𝑝3 = ⋯ = 𝑝𝑛 =
𝑛

• Total number of movements

1 3(𝑛 − 1)(𝑛 − 1)
𝑀 𝑛 = 1− × 𝑛−1 ×3=
𝑛 𝑛

66
Selection Sort: Summary of Complexity analysis
Case Comparisons Movement Memory Remarks
Case 1 𝑛(𝑛 − 1) 𝑀 𝑛 =0 𝑆 𝑛 =0 Input list is in sorted
𝑐 𝑛 =
2 order
Case 2 𝑛(𝑛 − 1) 3(𝑛 − 1) 𝑆 𝑛 =0 Input list is sorted in
𝑐 𝑛 = 𝑀 𝑛 =
2 2 reverse order

𝑛(𝑛 − 1) 2 𝑆 𝑛 =0
Case 3 3 𝑛−1 Input list is in random
𝑐 𝑛 = 𝑀 𝑛 =
2 𝑛 order

Case Run time, 𝑻(𝒏) Complexity Remarks

Case 1 𝑛(𝑛 − 1) 𝑇 𝑛 = 𝑂(𝑛2 )
𝑇 𝑛 = Best case
2
Case 2 (𝑛 − 1)(𝑛 + 3) 𝑇 𝑛 = 𝑂(𝑛2 )
𝑇 𝑛 = Worst case
2
Case 3 (𝑛 − 1)(2𝑛 + 3) 𝑇 𝑛 = 𝑂(𝑛2 )
𝑇 𝑛 ≈ Average case
2
(Taking 𝑛 − 1 ≈ 𝑛)

67
Bubble Sort

68
Bubble Sort
In every iteration The sorting process proceeds in
heaviest element drops
several passes.
at the bottom.
• In every pass we go on
comparing neighbouring pairs,
and swap them if out of order.
• In every pass, the largest of the
elements under considering
will bubble to the top (i.e., the
The bottom
moves upward. right).

69
Bubble Sort
How the passes proceed?
• In pass 1, we consider index 0 to n-1.
• In pass 2, we consider index 0 to n-2.
• In pass 3, we consider index 0 to n-3.
• ……
• ……
• In pass n-1, we consider index 0 to 1.

70
Bubble Sort - Example
Pass: 1

x: 3 12 -5 6 72 21 -7 45 x: 3 -5 6 12 72 21 -7 45

x: 3 12 -5 6 72 21 -7 45 x: 3 -5 6 12 21 72 -7 45

x: 3 -5 12 6 72 21 -7 45 x: 3 -5 6 12 21 -7 72 45

x: 3 -5 6 12 72 21 -7 45 x: 3 -5 6 12 21 -7 45 72

71
Bubble Sort - Example
Pass: 2

x: 3 -5 6 12 21 -7 45 72 x: -5 3 6 12 21 -7 45 72

x: -5 3 6 12 21 -7 45 72 x: -5 3 6 12 -7 21 45 72

x: -5 3 6 12 21 -7 45 72 x: -5 3 6 12 -7 21 45 72

x: -5 3 6 12 21 -7 45 72

72
Bubble Sort
void swap(int *x, int *y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}

void bubble_sort(int x[], int n)

{
int i,j;
for (i=n-1; i>0; i--)
for (j=0; j<i; j++)
if (x[j] > x[j+1])
swap(&x[j],&x[j+1]);
}

73
Bubble Sort
int main()
{
int x[ ]={-45,89,-65,87,0,3,-23,19,56,21,76,-50};
int i;
for(i=0;i<12;i++)
printf("%d ",x[i]); OUTPUT
printf("\n");
-45 89 -65 87 0 3 -23 19 56 21 76 -50
bubble_sort(x,12);
for(i=0;i<12;i++) -65 -50 -45 -23 0 3 19 21 56 76 87 89
printf("%d ",x[i]);
printf("\n");
}

74
Bubble Sort: Complexity analysis
Case 1: If the input list is already in sorted order
Number of comparisons:
𝑛(𝑛 − 1)
𝐶 𝑛 =
2

Number of movements:
𝑀 𝑛 =0

75
Bubble Sort: Complexity analysis
Case 2: If the input list is sorted but in reverse order
Number of comparisons:
𝑛(𝑛 − 1)
𝑐 𝑛 =
2

Number of movements:
𝑛(𝑛 − 1)
𝑀 𝑛 =
2

76
Bubble Sort: Complexity analysis
Case 3: If the input list is in random order
Number of comparisons:
𝑛(𝑛 − 1)
𝐶 𝑛 =
2
Number of movements:
• Let 𝑝𝑗 be the probability that the largest element is in the unsorted
part is in 𝑗𝑡ℎ (1 ≤ 𝑗 ≤ 𝑛 − 𝑖 + 1) location.
• The average number of swaps in the 𝑖𝑡ℎ pass is
𝑛−𝑖+1

= ෍ 𝑛 − 𝑖 + 1 − 𝑗 ∙ 𝑝𝑗
𝑗=1

77
Bubble Sort: Complexity analysis
Case 3: If the input list is in random order
Number of movements:
1
• 𝑝1 = 𝑝2 = 𝑝𝑛−𝑖+1 =
𝑛−𝑖+1
• Therefore, the average number of swaps in the 𝑖𝑡ℎ pass is
𝑛−𝑖+1
1 𝑛−𝑖
= ෍ ∙ 𝑛−𝑖+1−𝑗 =
𝑛−𝑖+1 2
𝑗=1
• The average number of movements
𝑛−1
𝑛 − 𝑖 𝑛(𝑛 − 1)
𝑀(𝑛) = ෍ =
2 4
𝑖=1

78
Bubble Sort: Summary of Complexity analysis
Case Comparisons Movement Memory Remarks
Case 1 𝑛(𝑛 − 1) 𝑀 𝑛 =0 𝑆 𝑛 =0 Input list is in sorted
𝑐 𝑛 =
2 order
Case 2 𝑛(𝑛 − 1) 𝑛(𝑛 − 1) 𝑆 𝑛 =0 Input list is sorted in
𝑐 𝑛 = 𝑀 𝑛 =
2 2 reverse order

Case 3 𝑛(𝑛 − 1) 𝑛(𝑛 − 1) 𝑆 𝑛 =0 Input list is in random

𝑐 𝑛 = 𝑀 𝑛 =
2 4 order

Case Run time, 𝑻(𝒏) Complexity Remarks

Case 1 𝑛(𝑛 − 1) 𝑇 𝑛 = 𝑂(𝑛2 )
𝑇 𝑛 =𝑐 Best case
2
Case 2 𝑇 𝑛 = 𝑐𝑛 𝑛 − 1 𝑇 𝑛 = 𝑂(𝑛2 ) Worst case

Case 3 3 𝑇 𝑛 = 𝑂(𝑛2 )
𝑇 𝑛 = 𝑛(𝑛 − 1) Average case
4

79
Bubble Sort
How do you make best case with (n-1)
comparisons only?

• By maintaining a variable flag, to check if

there has been any swaps in a given pass.
• If not, the array is already sorted.

80
Bubble Sort
void bubble_sort(int x[], int n)
{
int i,j;
int flag = 0;
for (i=n-1; i>0; i--)
{
for (j=0; j<i; j++)
if (x[j] > x[j+1])
{
swap(&x[j],&x[j+1]);
flag = 1;
}
if (flag == 0) return;
}
}

81
Efficient Sorting algorithms
Two of the most popular sorting algorithms are based on divide-
and-conquer approach.
• Quick sort
• Merge sort
Basic concept of divide-and-conquer method:
sort (list)
{
if the list has length greater than 1
{
Partition the list into lowlist and highlist;
sort (lowlist);
sort (highlist);
combine (lowlist, highlist);
}
}

82
Quick Sort

83
Quick Sort – How it Works?
At every step, we select a pivot element in the list
(usually the first element).
• We put the pivot element in the final position of the sorted
list.
• All the elements less than or equal to the pivot element are
to the left.
• All the elements greater than the pivot element are to the
right.

84
Quick Sort Partitioning
0 size-1
x:
pivot

Values smaller Values greater

Perform Perform
partitioning partitioning

85
Quick Sort
#include <stdio.h>
void quickSort( int[], int, int);
int partition( int[], int, int);
void main()
{
int i,a[] = { 7, 12, 1, -2, 0, 15, 4, 11, 9};
printf("\n\nUnsorted array is: ");
for(i = 0; i < 9; ++i)
printf(" %d ", a[i]);
quickSort( a, 0, 8);
printf("\n\nSorted array is: ");
for(i = 0; i < 9; ++i)
printf(" %d ", a[i]);
}
void quickSort( int a[], int l, int r)
{
int j;
if( l < r ) { // divide and conquer
j = partition( a, l, r);
quickSort( a, l, j-1);
quickSort( a, j+1, r);
}
}

86
Quick Sort
int partition( int a[], int l, int r)
{
int pivot, i, j, t;
pivot = a[l];
i = l;
j = r+1;
while( 1) {
do {
++i;
} while(a[i]<=pivot && i<=r);
do {
--j;
} while( a[j] > pivot );
if( i >= j ) break;
t = a[i];
a[i] = a[j];
a[j] = t;
}
t = a[l];
a[l] = a[j];
a[j] = t;
return j;
}

87
Quick Sort - Example
Input: 45 -56 78 90 -3 -6 123 0 -3 45 69 68

45 -56 78 90 -3 -6 123 0 -3 45 69 68

-6 -56 -3 0 -3 45 123 90 78 45 69 68
-56 -6 -3 0 -3 68 90 78 45 69 123
-3 0 -3 45 68 78 90 69
-3 0 69 78 90

Output: -56 -6 -3 -3 0 45 45 68 69 78 90 123

88
Quick Sort: Complexity analysis
Memory requirement:
Size of the stack is:
𝑆 𝑛 = 𝑙𝑜𝑔2 𝑛 + 1
Number of comparisons:
• Let, 𝑇(𝑛) represents total time to sort n elements and
𝑃(𝑛) represents the time for perform a partition of a list of
𝑛 elements.
𝑇 𝑛 = 𝑃 𝑛 + 𝑇 𝑛𝑙 + 𝑇 𝑛𝑟 , with 𝑇 1 = 𝑇 0 = 0
where, 𝑛𝑙 = number of elements in the left sub list
𝑛𝑟 = number of elements in the right sub list and 0 ≤ 𝑛𝑙 , 𝑛𝑟 < 𝑛

89
Quick Sort: Complexity analysis
Case 1: Elements in the list are in ascending order
Number of comparisons:
𝐶 𝑛 = 𝑛 − 1 + 𝐶 𝑛 − 1 , with 𝐶 1 = 𝐶 0 = 0
𝐶 𝑛 = 𝑛 − 1 + 𝑛 − 2 + 𝑛 − 3 + ⋯+ 2 + 1
𝑛(𝑛 − 1)
𝐶 𝑛 =
2
Number of movements:
𝑀 𝑛 =0

90
Quick Sort: Complexity analysis
Case 2: Elements in the list are in reverse order
Number of comparisons:
𝐶 𝑛 = 𝑛 − 1 + 𝐶 𝑛 − 1 , with 𝐶 1 = 𝐶 0 = 0
𝐶 𝑛 = 𝑛 − 1 + 𝑛 −2 + 𝑛 −3 +⋯+2 +1
𝑛(𝑛 − 1)
𝐶 𝑛 =
2
Number of movements:
𝑛−1
, 𝑖𝑓 𝑛 𝑖𝑠 𝑜𝑑𝑑
𝑀 𝑛 = 2
𝑛
, 𝑖𝑓 𝑛 𝑖𝑠 𝑒𝑣𝑒𝑛
2

91
Quick Sort: Complexity analysis
Case 3: Elements in the list are in random order
𝒊𝒕𝒉 location
(i-1) (n-1)

Number of comparisons:
𝑛−1
1
𝐶 𝑛 = 𝑛 − 1 + ෍ 𝐶 𝑖 − 1 + 𝐶(𝑛 − 1) 𝑤𝑖𝑡ℎ 𝐶 1 = 𝐶 0 = 0
𝑛
𝑖=1
𝑛−1
2
𝐶 𝑛 = 𝑛 − 1 + ෍ 𝐶(𝑖)
𝑛
𝑖=1

𝐶 𝑛 = 2 𝑛 + 1 𝑙𝑜𝑔𝑒 𝑛 + 0.577 − 4𝑛

92
Quick Sort: Complexity analysis
Case 3: Elements in the list are in random order
Number of movements:
𝑛
1
𝑀 𝑛 = ෍ 𝑖 − 1 + 𝑀 𝑖 − 1 + 𝑀(𝑛 − 𝑖)
𝑛
𝑖=1
𝑛−1
𝑛−1 2
𝑀 𝑛 = + ෍ 𝑀(𝑖)
2 𝑛
𝑖=1

𝑀 𝑛 = 2 𝑛 + 1 𝑙𝑜𝑔𝑒 𝑛 + 0.577 − 4𝑛

93
Quick Sort: Summary of Complexity analysis
Case Comparisons Movement Memory Remarks
Case 1 𝑛(𝑛 − 1) 𝑀 𝑛 =0 𝑆 𝑛 =1 Input list is in sorted
𝑐 𝑛 =
2 order
Case 2 𝑛(𝑛 − 1) 𝑛 𝑆 𝑛 =1 Input list is sorted in
𝑐 𝑛 = 𝑀 𝑛 =
2 2 reverse order
Case 3 𝐶 𝑛 𝑀 𝑛 𝑆 𝑛 Input list is in
= 2 𝑛 + 1 𝑙𝑜𝑔𝑒 𝑛 + 0.577 = 2 𝑛 + 1 (𝑙𝑜𝑔𝑒 𝑛 = 𝑙𝑜𝑔2 𝑛 + 1 random order
− 4𝑛 + 0.577) − 4𝑛

Case Run time, 𝑻(𝒏) Complexity Remarks

Case 1 𝑛(𝑛 − 1) 𝑇 𝑛 = 𝑂(𝑛2 )
𝑇 𝑛 =𝑐 Worst case
2
Case 2 𝑛(𝑛 − 1) 𝑛 𝑇 𝑛 = 𝑂(𝑛2 )
𝑇 𝑛 =𝑐 + Worst case
2 2

Case 3 𝑇 𝑛 = 4𝑐 𝑛 + 1 𝑙𝑜𝑔𝑒 𝑛 + 0.577 − 8𝑐𝑛 𝑇 𝑛 = 𝑂(𝑛𝑙𝑜𝑔2 𝑛) Best / Average

𝑇 𝑛 = 2𝑐 𝑛𝑙𝑜𝑔2 𝑛 − 𝑛 + 1 case

94
Merge Sort

95
Merge Sort – How it Works?
Input Array

Part-I Part-II

Part-I Part-II Part-I Part-II

Split
Merge
Sorted arrays

96
Merging two Sorted arrays
𝑷𝒂 𝑷𝒃

a: Sorted Array b: Sorted Array

0 l 0 m

c: Merged sorted array

0 l+m-1

Move and copy elements pointed by 𝑃𝑎 if its value is smaller

than the element pointed by 𝑃𝑏 in (𝑙 + 𝑚 − 1) operations and otherwise.

97
Merge Sort – Example
x: 3 12 -5 6 72 21 -7 45

3 12 -5 6 Splitting arrays 72 21 -7 45

3 12 -5 6 72 21 -7 45

3 12 -5 6 72 21 -7 45

3 12 -5 6 21 72 -7 45
Merging two
-5 3 6 12 -7 21 45 72
sorted arrays

-7
-7 -5 3 6 12 21 45 72 98
Merge Sort Program
#include<stdio.h>
void mergesort(int a[],int i,int j);
void merge(int a[],int i1,int j1,int i2,int j2);
int main()
{
int a[30],n,i;
printf("Enter no of elements:");
scanf("%d",&n);
printf("Enter array elements:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
mergesort(a,0,n-1);
printf("\nSorted array is :");
for(i=0;i<n;i++)
printf("%d ",a[i]);
return 0;
}

99
Merge Sort Program
void mergesort(int a[],int i,int j)
{
int mid;

if(i<j) {
mid=(i+j)/2;
/* left recursion */
mergesort(a,i,mid);
/* right recursion */
mergesort(a,mid+1,j);
/* merging of two sorted sub-arrays */
merge(a,i,mid,mid+1,j);
}
}

100
Merge Sort Program
void merge(int a[],int i1,int i2,int j1,int j2)
{
int temp[50]; //array used for merging
int i=i1,j=j1,k=0;
while(i<=i2 && j<=j2) //while elements in both lists
{
if(a[i]<a[j])
temp[k++]=a[i++];
else
temp[k++]=a[j++];
}
while(i<=i2) //copy remaining elements of the first list
temp[k++]=a[i++];
while(j<=j2) //copy remaining elements of the second list
temp[k++]=a[j++];
for(i=i1,j=0;i<=j2;i++,j++)
a[i]=temp[j]; //Transfer elements from temp[] back to a[]
}

101
Merge Sort – Splitting Trace
-56 23 43 -5 -3 0 123 -35 87 56 75 80

-56 23 43 -5 -3 0 123 -35 87 56 75 80

-56 23 43 -5 -3 0 123 -35 87 56 75 80

-56 23 43 -5 -3 0 123 -35 87 56 75 80

23 43 -3 0 -35 87 75 80

Output: -56 -35 -5 -3 0 23 43 56 75 80 87 123

Space Complexity?? Worst Case: O(n.log(n))

102
Merge Sort: Complexity analysis
Time Complexity:
𝑛 𝑛
𝑇 𝑛 =𝐷 𝑛 +𝑇 +𝑇 +𝐶 𝑛 𝑖𝑓 𝑛 > 1
2 2
𝑇 𝑛 = 𝑐1 𝑖𝑓 𝑛 = 1
• For simplicity of calculation
𝑛 𝑛 𝑛
𝑇 =𝑇 =𝑇
2 2 2
𝑇 𝑛 = 𝑐1 𝑖𝑓 𝑛 = 1
𝑛
𝑇 𝑛 = 𝑐2 + 2𝑇 + 𝑛−1 𝑖𝑓 𝑛 > 1
2
𝑇 𝑛 = 𝑛 ∙ 𝑐1 + 𝑛𝑙𝑜𝑔2 𝑛 + 𝑐2 − 1 𝑛 − 1 𝐴𝑠𝑠𝑢𝑚𝑖𝑛𝑔 𝑛 = 2𝑘

103
Quick Sort vs. Merge Sort
• Quick sort
• hard division, easy combination
• partition in the divide step of the divide-and-conquer
framework
• hence combine step does nothing

• Merge sort
• easy division, hard combination
• merge in the combine step
• the divide step in this framework does one simple
calculation only

104
Quick Sort vs. Merge Sort
Both the algorithms divide the problem into two sub
problems.
• Merge sort:
– two sub problems are of almost equal size always.

• Quick sort:
– an equal sub division is not guaranteed.

• This difference between the two sorting methods appears as

the deciding factor of their run time performances.

105