Module

no 6
Introduction to
Searching & Sorting
(7 Hour)

Prof. Pooja Polshetwar

 Syllabus

Module 6
Introduction to Sorting and Searching --------------07
Introduction to Searching: Linear search, Binary search,
Sorting: Internal VS. External Sorting, Sorting Techniques:
Bubble, Insertion, selection,
Quick Sort, Merge Sort, Comparison of sorting Techniques
based on their complexity.
Hashing Techniques, Different Hash functions, Collision &
Collision resolution
techniques: Linear and Quadratic probing, Double hashing.
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.
• 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:
1) linear search
2) binary search.
 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
int A[] = {15, 5, 20, 35, 2, 42, 67, 17};
In Steps 1 and 2 of the algorithm, we initialize the value
of POS and I. In Step 3, a while loop is executed that would
be executed till I is less than N (total number of elements
in the array).

In Step 4, a check is made to see if a match is

found between the current array element and VAL. If a match
is found, then the position of the array element is printed, else
the value of I is incremented to match the next element with
VAL.

However, if all the array elements have been compared

with VAL and no match is found, then it means that VAL is not
present in the array.
 Complexity of Linear Search
Algorithm
• Linear search executes in O(n) time where n is the
number of elements in the array
• In the best case of linear search is when VAL is equal
to the first element of the array. In this case, only one
comparison will be made. Likewise, the worst case will
happen when either VAL is not present in the array or
it is equal to the last element of the array.
• In both the cases, n comparisons will have to be
made. However, the performance of the linear search
algorithm can be improved by using a sorted array.
1. Write a program to search an element
for(i=0;i<n;i++)
in an array using the linear search
{
technique.
if(arr[i] == num)
#include <stdio.h>
{
#include <stdlib.h>
found =1;
#include <conio.h>
pos=i;
#define size 20 // Added so the size of the
printf("\n %d is found in the array
array can be altered more easily
at position= %d", num,i+1);
int main() {
/* +1 added in line 23 so that it
int arr[size], num, i, n, found = 0, pos = -1;
would display the number in
printf("\n Enter the number of elements in
the first place in the array as in
the array : ");
position 1 instead of 0 */
scanf("%d", &n);
break;
printf("\n Enter the elements: ");
}
for(i=0;i<n;i++)
}
{
if (found == 0)
scanf("%d", &arr[i]);
printf("\n %d does not exist in the
}
array", num);
printf("\n Enter the number that has to be
return 0;
searched : ");
}
scanf("%d", &num);
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.
When we are searching for a particular
name in a directory, we first open the
directory from the middle and then decide
whether to look for the name in the first
part of the directory or in the second part
of the directory. Again, we open some
page in the middle and the whole process
is repeated until we finally find the right
name.
• Take another analogy. How do we find
words in a dictionary? We first open the
dictionary somewhere in the middle. Then,
we compare the first word on that page
with the desired word whose meaning we
are looking for. If the desired word comes
before the word on the page, we look in
the first half of the dictionary, else we look
in the second half. Again, we open a page
in the first half of the dictionary and
compare the first word on that page with
the desired word and repeat the same
procedure until we finally get the word.
• int A[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

and the value to be searched is VAL = 9. The algorithm will proceed in the
following manner.

BEG = 0, END = 10, MID = (0 + 10)/2 = 5

Now, VAL = 9 and A[MID] = A[5] = 5

A[5] is less than VAL, therefore, we now search
for the value in the second half of the array. So,
we change the values of BEG and MID.
Now, BEG = MID + 1 = 6, END = 10, MID = (6 +
10)/2 =16/2 = 8
• VAL = 9 and A[MID] = A[8] = 8
• A[8] is less than VAL, therefore, we now
search for the value in the second half of
the segment.
• So, again we change the values of BEG
and MID.
• Now, BEG = MID + 1 = 9, END = 10, MID
= (9 + 10)/2 = 9
• Now, VAL = 9 and A[MID] = 9.
• BEG and END are the beginning and ending positions of the segment that
we are looking to search for the element. MID is calculated as (BEG +
END)/2.
• Initially, BEG = lower_bound and END = upper_bound. The algorithm will
terminate when A[MID] = VAL.
• When the algorithm ends, we will set POS = MID. POS is the position at
which the value is present in the array.
• However, if VAL is not equal to A[MID], then the values of BEG, END, and
MID will be changed depending on whether VAL is smaller or greater than
A[MID].
• (a) If VAL < A[MID], then VAL will be present in the left segment of the
array. So, the value of END will be changed as END = MID – 1.
• (b) If VAL > A[MID], then VAL will be present in the right segment of the
array. So, the value of BEG will be changed as BEG = MID + 1.
• Finally, if VAL is not present in the array, then eventually, END will be less
than BEG. When this happens, the algorithm will terminate and the search
will be unsuccessful.
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.
• 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.
• BUBBLE SORT
• 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 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 thehigher index, the two
elements are interchanged so that the element
is placed before the bigger one.
• This process will continue till the list of
unsorted elements exhausts.
• This procedure of sorting is called bubble
sorting because elements ‘bubble’ to the
top of the list. Note that at the end of the
first pass, the largest element in the list will
be placed at its proper position (i.e., at the
end of the list).
• To discuss bubble sort in detail, let us
consider an array A[] that has the following
elements:
A[] = {30, 52, 29, 87, 63, 27, 19, 54}
• Pass 2:
• (a) Compare 30 and 29. Since 30 > 29, swapping is done.
• 29, 30, 52, 63, 27, 19, 54, 87
• (b) Compare 30 and 52. Since 30 < 52, no swapping is done.
• (c) Compare 52 and 63. Since 52 < 63, no swapping is done.
• (d) Compare 63 and 27. Since 63 > 27, swapping is done.
• 29, 30, 52, 27, 63, 19, 54, 87
• (e) Compare 63 and 19. Since 63 > 19, swapping is done.
• 29, 30, 52, 27, 19, 63, 54, 87
• (f) Compare 63 and 54. Since 63 > 54, swapping is
done.
• 29, 30, 52, 27, 19, 54, 63, 87
• Observe that after the end of the second pass, the
second largest element is placed at the second highest
index of the array. All the other elements are still
unsorted.
• Pass 3:
• (a) Compare 29 and 30. Since 29 < 30, no swapping is
done.
• (b) Compare 30 and 52. Since 30 < 52, no swapping is
done.
• (c) Compare 52 and 27. Since 52 > 27, swapping is done.
• 29, 30, 27, 52, 19, 54, 63, 87
• (d) Compare 52 and 19. Since 52 > 19, swapping is done.
• 29, 30, 27, 19, 52, 54, 63, 87
• (e) Compare 52 and 54. Since 52 < 54, no swapping is
done.
• Observe that after the end of the third pass, the third
largest element is placed at the third highest
• index of the array. All the other elements are still unsorted.
• Pass 4:
• (a) Compare 29 and 30. Since 29 < 30, no swapping is
done.
• (b) Compare 30 and 27. Since 30 > 27, swapping is
done.
• 29, 27, 30, 19, 52, 54, 63, 87
• (c) Compare 30 and 19. Since 30 > 19, swapping is
done.
• 29, 27, 19, 30, 52, 54, 63, 87
• (d) Compare 30 and 52. Since 30 < 52, no swapping is
done.
• Observe that after the end of the fourth pass, the fourth
largest element is placed at the fourth highest index of
the array. All the other elements are still unsorted.
• Pass 5:
• (a) Compare 29 and 27. Since 29 > 27,
swapping is done.
• 27, 29, 19, 30, 52, 54, 63, 87
• (b) Compare 29 and 19. Since 29 > 19,
swapping is done.
• 27, 19, 29, 30, 52, 54, 63, 87
• (c) Compare 29 and 30. Since 29 < 30, no
swapping is done.
• Observe that after the end of the fifth pass, the
fifth largest element is placed at the fifth highest
• index of the array. All the other elements are still
unsorted.
• Pass 6:
• (a) Compare 27 and 19. Since 27 > 19, swapping is
done.
• 19, 27, 29, 30, 52, 54, 63, 87
• (b) Compare 27 and 29. Since 27 < 29, no swapping is
done.
• Observe that after the end of the sixth pass, the sixth
largest element is placed at the sixth largest
• index of the array. All the other elements are still
unsorted.
• Pass 7:
• (a) Compare 19 and 27. Since 19 < 27, no swapping is
done.
• Observe that the entire list is sorted now.
• Complexity of Bubble Sort
• The complexity of any sorting algorithm depends upon the number of
comparisons. In bubble
• sort, we have seen that there are N–1 passes in total. In the first pass,
N–1 comparisons are made to
• place the highest element in its correct position. Then, in Pass 2, there
are N–2 comparisons and the
• second highest element is placed in its position. Therefore, to compute
the complexity of bubble
• sort, we need to calculate the total number of comparisons. It can be
given as:
• f(n) = (n – 1) + (n – 2) + (n – 3) + ..... + 3 + 2 + 1
• f(n) = n (n – 1)/2
• f(n) = n2/2 + O(n) = O(n2)
• Therefore, the complexity of bubble sort algorithm is O(n2). It means the
time required to execute bubble sort is proportional to n2, where n is the
total number of elements in the array.
 INSERTION SORT
• Insertion sort is a very simple sorting algorithm
in which the sorted array (or list) is built one
element at a time.
• The main idea behind insertion sort is that it
inserts each item into its proper place in the final
list. To save memory, most implementations of
the insertion sort algorithm work by moving the
current data element past the already sorted
values and repeatedly interchanging it with the
preceding value until it is in its correct place.
• Insertion sort is less efficient as compared
to other more advanced algorithms such
as quick sort, heap sort, and merge sort.
• Insertion sort works as follows:
• The array of values to be sorted is divided into two sets.
One that stores sorted values and another that contains
unsorted values.
• The sorting algorithm will proceed until there are
elements in the unsorted set.
• Suppose there are n elements in the array. Initially, the
element with index 0 (assuming LB =0) is in the sorted
set. Rest of the elements are in the unsorted set.
• The first element of the unsorted partition has array
index 1 (if LB = 0).
• During each iteration of the algorithm, the first element in
the unsorted set is picked up and inserted into the
correct position in the sorted set.
Write a program to sort an array using insertion sort algorithm.
• #include <stdio.h>
• #include <conio.h> void insertion sort(int arr[], int n)
• #define size 5 {
• void insertion_sort(int arr[], int n); int i, j, temp;
• void main() for(i=1;i<n;i++)
• { {
• int arr[size], i, n; temp = arr[i];
• printf("\n Enter the number of j = i-1;
elements in the array: "); while((temp < arr[j]) && (j>=0))
• scanf("%d", &n); {
• printf("\n Enter the elements of the arr[j+1] = arr[j];
array: "); j--;
• for(i=0;i<n;i++) }
• { arr[j+1] = temp;
• scanf("%d", &arr[i]); }
• } }
• insertion_sort(arr, n);
• printf("\n The sorted array is: \n");
• for(i=0;i<n;i++)
• printf(" %d\t", arr[i]);
• getch();
• }
• Output
• Enter the number of elements in the array
:5
• Enter the elements of the array : 500 1 50
23 76
• The sorted array is :
• 1 23 20 76 500 6 7 8 9 10
• Advantages of Insertion Sort
• The advantages of this sorting algorithm are as follows:
• It is easy to implement and efficient to use on small sets of data.
• It can be efficiently implemented on data sets that are already
substantially sorted.
• It performs better than algorithms like selection sort and bubble sort.
Insertion sort algorithm is simpler than shell sort, with only a small
trade-off in efficiency. It is over twice as fast as
• the bubble sort and almost 40 per cent faster than the selection sort.
• it requires less memory space (only O(1) of additional memory
space).
• It is said to be online, as it can sort a list as and when it receives new
elements
 SELECTION SORT
• Selection sort is a sorting algorithm that
has a quadratic running time complexity of
O(n2), thereby making it inefficient to be
used on large lists.
• selection sort performs worse than
insertion sort algorithm, it is noted for its
simplicity.
• Selection sort is generally used for sorting
files with very large objects (records) and
small keys.
• Technique
• Consider an array ARR with N elements. Selection sort works as
follows:
• First find the smallest value in the array and place it in the first
position. Then, find the second smallest value in the array and place
it in the second position. Repeat this procedure until the entire array
is sorted. Therefore,
• In Pass 1, find the position POS of the smallest value in the array
and then swap ARR[POS] and ARR[0]. Thus, ARR[0] is sorted.
• In Pass 2, find the position POS of the smallest value in sub-array of
N–1 elements.
• Swap ARR[POS] with ARR[1]. Now, ARR[0] and ARR[1] is sorted.
• In Pass N–1, find the position POS of the smaller of the elements
ARR[N–2] and ARR[N–1]. Swap ARR[POS] and ARR[N–2] so that
ARR[0], ARR[1], ..., ARR[N–1] is sorted.
 MERGE SORT
• Merge sort is a sorting algorithm that uses
the divide, conquer, and combine
algorithmic paradigm.
• Divide means partitioning the n-element array to be
sorted into two sub-arrays of n/2 elements. If A is an
array containing zero or one element, then it is already
sorted. However, if there are more elements in the array,
divide A into two sub-arrays, A1 and A2 , each containing
about half of the elements of A.
• Conquer means sorting the two sub-
arrays recursively using merge sort.
Combine means merging the two sorted
sub-arrays of size n/2 to produce the
sorted array of n elements.
• Merge sort algorithm focuses on two main
concepts to improve its performance
(running time):
• 1. A smaller list takes fewer steps and thus
less time to sort than a large list.
• 2. As number of steps is relatively less,
thus less time is needed to create a sorted
list from two sorted lists rather than
creating it using two unsorted lists.
• The basic steps of a merge sort algorithm
are as follows:
 If the array is of length 0 or 1, then it is
already sorted.
 Otherwise, divide the unsorted array into
two sub-arrays of about half the size.
 Use merge sort algorithm recursively to
sort each sub-array.
 Merge the two sub-arrays to form a single
sorted list.
The running time of merge sort in the average case and the worst
case can be given as O(n log n).
 Quick Sort
• Quick sort is a widely used sorting
algorithm developed by C. A. R. Hoare
that makes O(n log n) comparisons in the
average case to sort an array of n
elements. However, in the worst case, it
has a quadratic running time given as
O(n2 ).
• The quick sort algorithm works as follows:
1. Select an element pivot from the array
elements.
• 2. Rearrange the elements in the array in
such a way that all elements that are less
than the pivot appear before the pivot and
all elements greater than the pivot element
come after it (equal values can go either
way). After such a partitioning, the pivot is
placed in its final position. This is called
the partition operation.
• 3. Recursively sort the two sub-arrays
thus obtained.
• Sort the elements given in the following
array using quick sort algorithm
• Now left = loc, so the procedure
terminates, as the pivot element (the first
element of the array, that is, 27) is placed
in its correct position. All the elements
smaller than 27 are placed before it and
those greater than 27 are placed after it.
The left sub-array containing 25, 10, 18
and the right sub-array containing 36 and
45 are sorted in the same manner.
• Pros and Cons of Quick Sort It is faster
than other algorithms such as bubble sort,
selection sort, and insertion sort. Quick
sort can be used to sort arrays of small
size, medium size, or large size. On the
flip side, quick sort is complex and
massively recursive.
COMPARISON OF Sorting ALGORITHMS Table 14.1 compares the
average-case and worst-case time complexities of different sorting
algorithms