Searching and Sorting Algorithms

1. Introduction to searching and sorting algorithms
2. Types of searching algorithms - Linear search and Binary search.
3. Basic iterative sorting - Bubble sort, Selection sort and Insertion sort.
4. Time and space complexity analysis of searching and sorting
algorithms.

1. Searching and Sorting Algorithms
Dr. Ashutosh Satapathy
Assistant Professor, Department of CSE
VR Siddhartha Engineering College
Kanuru, Vijayawada
March 9, 2024
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

2. Outline
1
Searching
Introduction
Linear Search
Binary Search
2
Sorting
Introduction
Insertion Sort
Selection Sort
Bubble Sort
Optimized Bubble Sort
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

3. Outline
1
Searching
Introduction
Linear Search
Binary Search
2
Sorting
Introduction
Insertion Sort
Selection Sort
Bubble Sort
Optimized Bubble Sort
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

4. Introduction
Information retrieval is one of the important applications of
computers. It becomes necessary to search a list of records to identify
a particular record.
Each record contains a field whose value is unique to distinguish
among the records are known as keys.
A particular record can be identified when key value of that record is
equal to a given input value. This operation is known as searching.
If the record is found then search is said to be successful, otherwise it
is unsuccessful. The searching problem falls into two cases.
If there are many records, perhaps each one quite large, then it will be
necessary to store the records in files on disk or tape, external to the
primary memory. This is called external searching.
Else, the records to be searched are stored entirely in the primary
memory. This is called internal searching.
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

5. Outline
1
Searching
Introduction
Linear Search
Binary Search
2
Sorting
Introduction
Insertion Sort
Selection Sort
Bubble Sort
Optimized Bubble Sort
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

6. Linear Search
The simplest way to do a search is to begin at one end of the list and
scan down ituntil the desired key is foundor the other end is
reached.
Let us assume that a is an array of n keys,a[0] through a[n-1]. Let
us also assume that key is a search element.
The process starts with a comparison between thefirst element(i.e,
a[0]) andkey. As long as a comparison does not result in a success,
the algorithm proceeds to compare the next element of a and key.
The processterminateswhen thelist exhaustedor acomparison
resultsin asuccess. This method of searching is also known as
linear searching.
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

7. Linear Search
Algorithm 1Linear search
1:procedurelinearsearch(a,n,key)
2:fori←0 ton−1do
3: if(key=a[i])then
4: returni
5: end if
6:end for
7:return-1
8:end procedure
The function examines each key in turn; upon finding one that
matches the search argument, its index is returned. If no match is
found, -1 is returned.
When thevaluesof the array a arenot distinctthen the function
willreturn the first indexof the array a which is equal to key.
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

8. Linear Search
Best Case Time Complexity:The searched element is available at the
a[0].
Algorithm 2Linear search best case analysis
1:procedurelinearsearch(a,n,key) ▷Frequency count is 1
2:fori←0 ton−1do ▷Frequency count is 1
3: if(key=a[i])then ▷Frequency count is 1
4: returni ▷Frequency count is 1
5: end if ▷Frequency count is 0
6:end for ▷Frequency count is 0
7:return-1 ▷Frequency count is 0
8:end procedure ▷Frequency count is 0
Total frequency countf(n)is4. So, thebest-casetime complexity is
O(1).
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

9. Linear Search
Worst Case Time Complexity:The searched element is available at the
a[n-1].
Algorithm 3Linear search worst case analysis
1:procedurelinearsearch(a,n,key) ▷Frequency count is 1
2:fori←0 ton−1do ▷Frequency count is n
3: if(key=a[i])then ▷Frequency count is n
4: returni ▷Frequency count is 1
5: end if ▷Frequency count is 0
6:end for ▷Frequency count is 0
7:return-1 ▷Frequency count is 0
8:end procedure ▷Frequency count is 0
Total frequency countf(n)is2n+2. So, theworst-casetime complexity
isO(n).
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

10. Linear Search
Worst Case Time Complexity:The searched element is is not available
in the array.
Algorithm 4Linear search worst case analysis
1:procedurelinearsearch(a,n,key) ▷Frequency count is 1
2:fori←0 ton−1do ▷Frequency count is n+1
3: if(key=a[i])then ▷Frequency count is n
4: returni ▷Frequency count is 0
5: end if ▷Frequency count is 0
6:end for ▷Frequency count is n
7:return-1 ▷Frequency count is 1
8:end procedure ▷Frequency count is 1
Total frequency countf(n)is3n+4. So, theworst-casetime complexity
isO(n).
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

11. Linear Search
Average Case Time Complexity:
Leticomparisons are necessary to search the i
th
element. Let Piis
the probability that i
th
element will be searched.
The expected number of comparisons for a successful search is given
by f(n) = 1.P0+ 2.P1+ 3.P2+ ... + nPn-1=
P
n
i=1
i.Pi−1
Since P is the probability that record i is retrieved then P0+ P1+ P2
+ ... + Pn-1= 1
If it is assumed that any element is an equally likely candidate for
searching then P0= P1= P2= ... = Pn-1=
1
n
.
In this case, we have f(n) =
P
n
i=1
i.Pi−1=
P
n
i=1
i.
1
n
=
1
n
P
n
i=1
i=
1
n
(1 + 2 +...+n) =
n(n+1)
2n
=
(n+1)
2
So, theaverage-casetime complexity isO(n).
f(n) isminimumwhen P0≥P1≥P2≥...≥Pn-1. i.e, when the
mostfrequently searched elementsare placed towards the
beginningof the array.
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

12. Linear Search
Space Complexity:
The variablesi,nandkeyoccupy a constant12 Bytesof memory.
Thefunction call,for loop,ifandelseconditions andreturn
statementall come under the auxiliary space and let’s assume4
Bytesall together.
The total space complexity is4n+16 Bytes.Algorithm 1has a
space complexity ofO(n).
As the amount ofextra datain linear search isfixed, thespace
complexityof these extra amount spaces isO(1).
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

13. Outline
1
Searching
Introduction
Linear Search
Binary Search
2
Sorting
Introduction
Insertion Sort
Selection Sort
Bubble Sort
Optimized Bubble Sort
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

14. Binary Search
Sequential searchis simple method for searching an element in an
array. This isefficientfor asmall listof elements.
Highly inefficientforlarger lists. In the worst case, we will have to
make n comparisons, as to search for the last element in the list.
Binary search is a very efficient search technique which works for
sorted lists.
we make acomparisonbetweenkeyandmiddle elementof array or
identifyingtheleft halfor theright halfof the array to which the
desired element may belong.
The procedure isrepeatedon thehalfin which the desired element
is likely to be present.
When the number of elements iseven, there aretwo elementsin the
middle. However, anarbitrary choiceofany oneof these as the
middle element will serve the purpose.
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

15. Binary Search
Algorithm 5Binary search
1:procedurebinarysearch(a,n,key)
2:low←0
3:high←n−1
4:while(low≤high)do
5: mid←⌈
low+high
2
⌉
6: if(key=a[mid])then
7: returnmid
8: else if(key<a[mid])then
9: high←mid−1
10: else
11: low←mid+ 1
12: end if
13:end while
14:return-1
15:end procedure
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

16. Binary Search
Figure 1.1:
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

17. Binary Search
Algorithm 6Binary search best case time complexity - O(1)
1:procedurebinarysearch(a,n,key) ▷Frequency count is 1
2:low←0 ▷Frequency count is 1
3:high←n−1 ▷Frequency count is 1
4:while(low≤high)do ▷Frequency count is 1
5: mid←⌈
low+high
2
⌉ ▷Frequency count is 1
6: if(key=a[mid])then ▷Frequency count is 1
7: returnmid ▷Frequency count is 1
8: else if(key<a[mid])then ▷Frequency count is 0
9: high←mid−1 ▷Frequency count is 0
10: else ▷Frequency count is 0
11: low←mid+ 1 ▷Frequency count is 0
12: end if ▷Frequency count is 0
13:end while ▷Frequency count is 0
14:return-1 ▷Frequency count is 0
15:end procedure ▷Frequency count is 0
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

18. Binary Search
Worst Case Time Complexity:
To analyze the performance of binary search, themaximum number
ofcomparisonsrequired fora successful searchwill be computed.
Let i be the smallest integer such that2
i
≥n+1.
The maximum number of elements that are left after the first
comparison is2
i-1
-1and in general, the maximum number of
elements left afterkcomparisons is2
i-k
-1.
we are left with no elements to be compared after i comparisons as
2
i-i
-1.
f(n), the maximum number of comparisons for a successful search is
given byf(n) = i.
So, 2
i
=n+ 1⇒log
22
i
= log
2(n+ 1)⇒ilog
22 = log
2(n+ 1)⇒
i= log
2(n+ 1)⇒f(n) = log
2(n+ 1). The worst case time
complexity isO(log2n).
Searchcan be declared asunsuccessfulonly when there areno
elementsto be probed.
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

19. Binary Search
Average Case Time Complexity:
Theaverage numberofcomparisonsunder the assumption that
eachkeyis anequally likely candidatefor a search.
theprobabilitythat a particular element will be requested in a search
is(1/n).
We assumen=2
i
-1for somei. Now, theelementinmiddle
positionrequires only one comparison to be searched.
theelementsin themiddle positionsof thetwo halvesrequiretwo
comparisonseach when searched.
Thetotal number of comparisonsrequired to search every array
element is given by
C(n) = 1.2
0
+ 2.2
1
+ 3.2
2
+...+i.2
i-1
(1)
Multiply both sides of equation (2) by 2
2.C(n) = 1.2
1
+ 2.2
2
+ 3.2
3
+...+i.2
i
(2)
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

20. Binary Search
Average Case Time Complexity:
Subtracting equation (2) from equation (3), the result is
C(n) =i.2
i
−(2
0
+ 2
1
+ 2
2
+...+ 2
i-1
) =i.2
i
−
P
i−1
i=0
2
i
=
i.2
i
−2
i
+ 1 = 1 + 2
i
(i−1)
The average number of comparisons for a successful search, is given
byf(n) =
C(n)
n
=
1+2
i
(i−1)
n
As 2
i
=n+ 1⇒i= log
2(n+ 1)⇒i−1 = log
2(n+ 1)−1.
f(n) =
1+2
i
(i−1)
n
=
1+(n+1)(log
2
(n+1)−1)
n
=
(n+1) log
2
(n+1)
n
−1
The above outcome has been derived under the assumption thatnis
of the form2
i
-1, the approximate result is valid for any value ofn.
So, the average number of comparisons for a successful as well as
unsuccessful number of comparison areO(log2n).
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

21. Binary Search
Space Complexity:
The variablesn,key,low,highandmidoccupy a constant20 Bytes
of memory. Thefunction call,while loop,if,else ifandelse
conditions andreturn statementall come under the auxiliary space
and let’s assumeK Bytesall together.
The total space complexity is4n+20+K Bytes.Algorithm 5has a
space complexity ofO(n).
As the amount ofextra variablesin binary search isfixed, thespace
complexityof these extra amount spaces isO(1).
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

22. Outline
1
Searching
Introduction
Linear Search
Binary Search
2
Sorting
Introduction
Insertion Sort
Selection Sort
Bubble Sort
Optimized Bubble Sort
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

23. Introduction
Sortingisarrangingthedatain ascending ordescendingorder.
The termsortingcame into picture, as humansrealisedthe
importanceofsearching quickly.
If anarray Acontains a sequence ofn numbers<a1, a2, ..., an>.
ASortingis thepermutation (reordering)<a1
’
, a2
’
, ..., an
’
>of
the input sequence such thata1
’
≤a2
’
≤...≤an
’
.
Since the beginning of the programming age, computer scientists
have been working on solving the problem of sorting by coming up
withvarious different algorithmsto sort data.
Some of the sorting techniques areBubble sort,Selection sort,
Insertion sort,Merge sort,Quick sortandHeap sortetc.
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

24. Outline
1
Searching
Introduction
Linear Search
Binary Search
2
Sorting
Introduction
Insertion Sort
Selection Sort
Bubble Sort
Optimized Bubble Sort
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

25. Insertion Sort
Insertion sortis an efficient algorithm forsortingasmall number
ofelements. It sorts a set of values by inserting values in to an
existing sorted file.
The method can be explained in the similar way thearrangement of
cardsby a card player.
Thecard playerpicks up the cards andinsertsthem in to the
required position.
Thus at every step, weinsertan item in to itsproper placein an
alreadyordered list.
suppose an array a with n elements a[0], a[1], ..., a[n-1] is in memory.
The insertion sort scans a from a[0] to a[n-1], inserting eachelement
a[k]in to itsproper positionin thepreviously sorted sub-array
a[0], a[1], ...., a[k-1].
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

26. Insertion Sort
Algorithm 7Insertion Sort
1:procedureinsertion-sort(A,n)
2:forj←1 ton−1do
3: key←A[j]
4: i←j-1
5: while(i≥0 andA[i]>key)do
6: A[i+1]←A[i]
7: i←i-1
8: end while
9: A[i+1]←key
10:end for
11:end procedure
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

27. Insertion Sort
Figure 2.1:
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

28. Insertion Sort
Best Case Time Complexity:
Algorithm 8Insertion Sort Best Case Analysis
1:procedureinsertion-sort(A,n) ▷Frequency count is 1
2:forj←1 ton−1do ▷Frequency count is n
3: key←A[j] ▷Frequency count is n-1
4: i←j-1 ▷Frequency count is n-1
5: while(i≥0 andA[i]>key)do ▷Frequency count is n-1
6: A[i+1]←A[i] ▷Frequency count is 0
7: i←i-1 ▷Frequency count is 0
8: end while ▷Frequency count is 0
9: A[i+1]←key ▷Frequency count is n-1
10:end for ▷Frequency count is n-1
11:end procedure ▷Frequency count is 1
Total frequency count f(n) is 6n-3. The best case time complexity is O(n)
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

29. Insertion Sort
Table 2.1:
Statement Frequency Count Time
1 1 O(1)
2 n O(n)
3 n-1 O(n)
4 n-1 O(n)
5 2+3+4+...+n = n(n+1)/2 - 1 O(n
2
)
6 1+2+3+...+n-1 = n(n-1)/2 O(n
2
)
7 1+2+3+...+n-1 = n(n-1)/2 O(n
2
)
8 1+2+3+...+n-1 = n(n-1)/2 O(n
2
)
9 n-1 O(n)
10 n-1 O(n)
11 1 O(1)
f(n) 2n
2
+4n-3 O(n
2
)
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

30. Insertion Sort
Best Case Time Complexity Analysis - Big Oh Notation
f(n) = 6n-3≤cn
Assume c = 6, then f(n) = 6n-3≤6n
⇒3≤6 [Since n0= 1]
For n0≥1, f(n)≤6n
So, best case time complexity O(n), where n0= 1 and c = 6.
Worst Case Time Complexity Analysis - Big Oh Notation
f(n) = 2n
2
+4n-3≤cn
2
Assume c = 3, then f(n) = 2n
2
+4n-3≤3n
2
⇒27≤27 [Since n0= 3]
For n0≥3, f(n)≤3n
2
So, worst case time complexity O(n
2
), where n0= 3 and c = 3.
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

31. Insertion Sort
Best Case Time Complexity Analysis - Big Omega Notation
f(n) = 6n-3≥cn
Assume c = 5, then f(n) = 6n-3≥5n
⇒15≥15 [Since n0= 3]
For n0≥3, f(n)≥5n
So, best case time complexity Ω(n), where n0= 3 and c = 5.
Worst Case Time Complexity Analysis - Big Omega Notation
f(n) = 2n
2
+4n-3≥cn
2
Assume c = 2, then f(n) = 2n
2
+4n-3≥2n
2
⇒3≥2 [Since n0= 1]
For n0≥1, f(n)≥2n
2
So, worst case time complexity Ω(n
2
), where n0= 1 and c = 2.
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

32. Insertion Sort
Best Case Time Complexity Analysis - Little Oh Notation
f(n) = 6n-3<cn
Assume c = 6, then f(n) = 6n-3<6n
⇒3<6 [Since n0= 1]
For n0≥1, f(n)<6n
So, best case time complexity o(n), where n0= 1 and c = 6.
Worst Case Time Complexity Analysis - Little Oh Notation
f(n) = 2n
2
+4n-3<cn
2
Assume c = 3, then f(n) = 2n
2
+4n-3<3n
2
⇒45<48 [Since n0= 4]
For n0≥4, f(n)<3n
2
So, worst case time complexity o(n
2
), where n0= 4 and c = 3.
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

33. Insertion Sort
Best Case Time Complexity Analysis - Little Omega Notation
f(n) = 6n-3>cn
Assume c = 5, then f(n) = 6n-3>5n
⇒21>20 [Since n0= 4]
For n0≥4, f(n)>5n
So, best case time complexityω(n), where n0= 4 and c = 5.
Worst Case Time Complexity Analysis - Little Omega Notation
f(n) = 2n
2
+4n-3>cn
2
Assume c = 2, then f(n) = 2n
2
+4n-3>2n
2
⇒3>2 [Since n0= 1]
For n0≥1, f(n)>2n
2
So, worst case time complexityω(n
2
), where n0= 1 and c = 2.
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

34. Insertion Sort
Best Case Time Complexity Analysis - Theta Notation
c1n≤f(n) = 6n-3≤c2n
Assume c1= 5 and c2= 6, then 5n≤6n-3≤6n
⇒15≤15≤18 [Since n0= 3]
For n0≥3, 5n≤f(n)≤6n
So, best case time complexityθ(n), where n0= 3, c1= 5 and c2= 6.
Worst Case Time Complexity Analysis - Theta Notation
c1n
2
≤f(n) = 2n
2
+4n-3≤c2n
2
Assume c1= 2 and c2= 3, then 2n
2
≤2n
2
+4n-3≤3n
2
⇒18≤27≤27 [Since n0= 3]
For n0≥3, 2n
2
≤f(n)≤3n
2
So, worst case time complexityθ(n
2
), where n0= 3, c1= 2 and c2= 3.
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

35. Insertion Sort
Space Complexity:
The variablesn,key,iandjoccupy a constant16 Bytesof memory.
Thefunction call,while loopandfor loopall come under the
auxiliary space and let’s assumeK Bytesall together.
The total space complexity is4n+16+K Bytes.Algorithm 7has a
space complexity ofO(n).
As the amount ofextra variablesin insertion sort isfixed, thespace
complexityof these extra amount spaces isO(1).
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

36. Outline
1
Searching
Introduction
Linear Search
Binary Search
2
Sorting
Introduction
Insertion Sort
Selection Sort
Bubble Sort
Optimized Bubble Sort
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

37. Selection Sort
The selection sort is also known aspush-down sort.
The sort consists entirely of a selection phase in which thesmallest
of the remaining elements,small, is repeatedly placed in its proper
position.
Letabe an array ofn elements. Find theposition iof the smallest
element in the list of n elementsa[0], a[1], ..., a[n-1]and then
interchange a[i] with a[0]. Thena[0]is sorted.
Find theposition iof thesmallestin thesub-list of n-1 elements
a[1], a[2], ..., a[n-1]. Then interchangea[i] with a[1]. Then a[0]
and a[1] are sorted.
find theposition iof thesmallest elementin thesub-list of n-2
elements a[2], a[3], ..., a[n-1]. Then interchangea[i] with a[2].
Thena[0], a[1] and a[2]are sorted.
Like this, find theposition iof thesmallest elementbetweena[n-2]
and a[n-1]. Then interchangea[i] with a[n-2]. Then the array a is
sorted.
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

38. Selection Sort
Algorithm 9Selection Sort
1:procedureSelection-sort(A,n)
2:fori←0 ton−2do
3: min←i
4: forj←i+ 1 ton−1do
5: ifA[j]<a[min]then
6: min←j// index of the i
th
smallest element.
7: end if
8: end for
9: t←A[min]
10: a[min]←A[i]
11: a[i]←t
12:end for
13:end procedure
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

39. Selection Sort
Figure 2.2:
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

40. Selection Sort
Best Case Time Complexity:Total freq. count f(n) is 1.5n
2
+5.5n-4
Algorithm 10Selection Sort
1:procedureSelection-sort(A,n) ▷Frequency count is 1
2:fori←0 ton−2do ▷Frequency count is n
3: min←i ▷Frequency count is n-1
4: forj←i+ 1 ton−1do ▷Freq. count is n(n+1)/2 -1
5: ifA[j]<a[min]then ▷Freq. count is n(n-1)/2
6: min←j ▷Frequency count is 0
7: end if ▷Frequency count is 0
8: end for ▷Freq. count is n(n-1)/2
9: t←A[min] ▷Frequency count is n-1
10: a[min]←A[i] ▷Frequency count is n-1
11: a[i]←t ▷Frequency count is n-1
12:end for ▷Frequency count is n-1
13:end procedure ▷Frequency count is 1
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

41. Selection Sort
Worst Case Time Complexity:Total freq. count f(n) is 2.5n
2
+4.5n-4
Algorithm 11Selection Sort
1:procedureSelection-sort(A,n) ▷Frequency count is 1
2:fori←0 ton−2do ▷Frequency count is n
3: min←i ▷Frequency count is n-1
4: forj←i+ 1 ton−1do ▷Freq. count is n(n+1)/2 -1
5: ifA[j]<a[min]then ▷Freq. count is n(n-1)/2
6: min←j ▷Freq. count is n(n-1)/2
7: end if ▷Freq. count is n(n-1)/2
8: end for ▷Freq. count is n(n-1)/2
9: t←A[min] ▷Frequency count is n-1
10: a[min]←A[i] ▷Frequency count is n-1
11: a[i]←t ▷Frequency count is n-1
12:end for ▷Frequency count is n-1
13:end procedure ▷Frequency count is 1
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

42. Selection Sort
Best Case Time Complexity Analysis - Big Oh Notation
f(n) = 1.5n
2
+5.5n-4≤cn
2
Assume c = 2, then f(n) = 1.5n
2
+5.5n-4≤2n
2
⇒238≤242 [Since n0= 11]
For n0≥11, f(n)≤2n
2
So, best case time complexity O(n
2
), where n0= 11 and c = 2.
Worst Case Time Complexity Analysis - Big Oh Notation
f(n) = 2.5n
2
+4.5n-4≤cn
2
Assume c = 3, then f(n) = 2.5n
2
+4.5n-4≤3n
2
⇒192≤192 [Since n0= 8]
For n0≥8, f(n)≤3n
2
So, worst case time complexity O(n
2
), where n0= 8 and c = 3.
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

43. Selection Sort
Best Case Time Complexity Analysis - Big Omega Notation
f(n) = 1.5n
2
+5.5n-4≥cn
2
Assume c = 1, then f(n) = 1.5n
2
+5.5n-4≥n
2
⇒3≥1 [Since n0= 1]
For n0≥1, f(n)≥n
2
So, best case time complexity Ω(n
2
), where n0= 1 and c = 1.
Worst Case Time Complexity Analysis - Big Omega Notation
f(n) = 2.5n
2
+4.5n-4≥cn
2
Assume c = 2, then f(n) = 2.5n
2
+4.5n-4≥2n
2
⇒3≥2 [Since n0= 1]
For n0≥1, f(n)≥2n
2
So, worst case time complexity Ω(n
2
), where n0= 1 and c = 2.
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

44. Selection Sort
Best Case Time Complexity Analysis - Little Oh Notation
f(n) = 1.5n
2
+5.5n-4<cn
2
Assume c = 2, then f(n) = 1.5n
2
+5.5n-4<2n
2
⇒238<242 [Since n0= 11]
For n0≥11, f(n)<2n
2
So, best case time complexity o(n
2
), where n0= 11 and c = 2.
Worst Case Time Complexity Analysis - Little Oh Notation
f(n) = 2.5n
2
+4.5n-4<cn
2
Assume c = 3, then f(n) = 2.5n
2
+4.5n-4<3n
2
⇒239<243 [Since n0= 9]
For n0≥9, f(n)<3n
2
So, worst case time complexity o(n
2
), where n0= 9 and c = 3.
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

45. Selection Sort
Best Case Time Complexity Analysis - Little Omega Notation
f(n) = 1.5n
2
+5.5n-4>cn
2
Assume c = 1, then f(n) = 1.5n
2
+5.5n-4>n
2
⇒3>1 [Since n0= 1]
For n0≥1, f(n)>n
2
So, best case time complexityω(n
2
), where n0= 1 and c = 1.
Worst Case Time Complexity Analysis - Little Omega Notation
f(n) = 2.5n
2
+4.5n-4>cn
2
Assume c = 2, then f(n) = 2.5n
2
+4.5n-4>2n
2
⇒3>2 [Since n0= 1]
For n0≥1, f(n)>2n
2
So, worst case time complexityω(n
2
), where n0= 1 and c = 2.
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

46. Selection Sort
Best Case Time Complexity Analysis - Theta Notation
c1n
2
≤f(n) = 1.5n
2
+5.5n-4≤c2n
2
Assume c1= 1 and c2= 2, then n
2
≤1.5n
2
+5.5n-4≤2n
2
⇒121≤238≤242 [Since n0= 11]
For n0≥11, n
2
≤f(n)≤2n
2
So, best case time complexityθ(n), where n0= 11, c1= 1 and c2= 2.
Worst Case Time Complexity Analysis - Theta Notation
c1n
2
≤f(n) = 2.5n
2
+4.5n-4≤c2n
2
Assume c1= 2 and c2= 3, then 2n
2
≤2.5n
2
+4.5n-4≤3n
2
⇒128≤192≤192 [Since n0= 8]
For n0≥8, 2n
2
≤f(n)≤3n
2
So, worst case time complexityθ(n
2
), where n0= 8, c1= 2 and c2= 3.
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

47. Selection Sort
Space Complexity:
The variablesn,min,t,iandjoccupy a constant20 Bytesof
memory. Thefunction call,while loopandfor loopall come under
the auxiliary space and let’s assumeK Bytesall together.
The total space complexity is4n+20+K Bytes.Algorithm 9has a
space complexity ofO(n).
As the number ofextra variablesin the selection sort isfixed, the
space complexityof theseextra spacesisO(1).
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

48. Outline
1
Searching
Introduction
Linear Search
Binary Search
2
Sorting
Introduction
Insertion Sort
Selection Sort
Bubble Sort
Optimized Bubble Sort
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

49. Bubble Sort
Bubble sortproceeds byscanning the list from left to right, and
whenever a pair ofadjacent keys found out of order, those
items are swapped.
This process repeats till all the elements of the list are in sorted order.
Leta is an array of n integersin which the elements are to be
sorted, so thata[i]≤a[j]for0≤i<j<n.
The basic idea of bubble sort is to pass through the list sequentially
several times.
Each pass consists ofcomparing each elementin the listwith its
successorsand interchanging the two elements if they are not in the
proper order.
In Pass 1,Compare a[0] and a[1]and arrange them in order so that
a[0]≤a[1]. Thencompare a[1] and a[2]and arrange them so that
a[1]≤a[2].
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

50. Bubble Sort
Continue untila[n-2] and a[n-1]comparison and arrange them so
thata[n-2]≤a[n-1].Pass 1involvesn-1 comparisonand the
largest elementoccupies(n-1)
th
position.
In Pass 2,repeat the above process with one less comparisoni.e.
stop after comparing and possible rearrangement ofa[n-3] and
a[n-2].
It involvesn-2 comparisons, thesecond largest elementwill
occupies(n-2)
th
position. The process continues, and the(n-i)
th
index positionreceivesi
th
largest elementafter pass i.
Comparea[0] and a[1]inpass n-1, and arrange them so thata[0]
≤a[1].
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

51. Bubble Sort
Algorithm 12Bubble Sort
1:procedureBubble-sort(A,n)
2:fori←0 ton−2do
3: forj←0 ton−i−2do
4: // compare adjacent elements
5: ifA[j]>a[j+ 1]then
6: t←A[j]
7: a[j]←A[j+ 1]
8: a[j+ 1]←t
9: end if
10: end for
11:end for
12:end procedure
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

52. Bubble Sort
Figure 2.3:
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

53. Bubble Sort
Figure 2.4:
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

54. Bubble Sort
Best Case Time Complexity:
Algorithm 13Bubble Sort
1:procedureBubble-sort(A,n) ▷Frequency count is 1
2:fori←0 ton−2do ▷Frequency count is n
3: forj←0 ton−i−2do ▷Freq. count is n(n+1)/2 -1
4: ifA[j]>a[j+ 1]then ▷Freq. count is n(n-1)/2
5: t←A[j] ▷Frequency count is 0
6: a[j]←A[j+ 1] ▷Frequency count is 0
7: a[j+ 1]←t ▷Frequency count is 0
8: end if ▷Frequency count is 0
9: end for ▷Freq. count is n(n-1)/2
10:end for ▷Frequency count is n-1
11:end procedure ▷Frequency count is 1
Total frequency count f(n) is 1.5n
2
+1.5n. The best case time complexity
is O(n
2
)
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

55. Bubble Sort
Worst Case Time Complexity:
Algorithm 14Bubble Sort
1:procedureBubble-sort(A,n) ▷Frequency count is 1
2:fori←0 ton−2do ▷Frequency count is n
3: forj←0 ton−i−2do ▷Freq. count is n(n+1)/2 -1
4: ifA[j]>a[j+ 1]then ▷Freq. count is n(n-1)/2
5: t←A[j] ▷Freq. count is n(n-1)/2
6: a[j]←A[j+ 1] ▷Freq. count is n(n-1)/2
7: a[j+ 1]←t ▷Freq. count is n(n-1)/2
8: end if ▷Freq. count is n(n-1)/2
9: end for ▷Freq. count is n(n-1)/2
10:end for ▷Frequency count is n-1
11:end procedure ▷Frequency count is 1
Total frequency count f(n) is 3.5n
2
-0.5n. The worst case time complexity
is O(n
2
)
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

56. Bubble Sort
Best Case Time Complexity Analysis - Big Oh Notation
f(n) = 1.5n
2
+1.5n≤cn
2
Assume c = 2, then f(n) = 1.5n
2
+1.5n≤2n
2
⇒18≤18 [Since n0= 3]
For n0≥3, f(n)≤2n
2
So, best case time complexity O(n
2
), where n0= 3 and c = 2.
Worst Case Time Complexity Analysis - Big Oh Notation
f(n) = 3.5n
2
-0.5n≤cn
2
Assume c = 4, then f(n) = 3.5n
2
-0.5n≤4n
2
⇒3≤4 [Since n0= 1]
For n0≥1, f(n)≤4n
2
So, worst case time complexity O(n
2
), where n0= 1 and c = 4.
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

57. Bubble Sort
Best Case Time Complexity Analysis - Big Omega Notation
f(n) = 1.5n
2
+1.5n≥cn
2
Assume c = 1, then f(n) = 1.5n
2
+1.5n≥n
2
⇒3≥1 [Since n0= 1]
For n0≥1, f(n)≥n
2
So, best case time complexity Ω(n
2
), where n0= 1 and c = 1.
Worst Case Time Complexity Analysis - Big Omega Notation
f(n) = 3.5n
2
-0.5n≥cn
2
Assume c = 3, then f(n) = 3.5n
2
-0.5n≥3n
2
⇒3≥3 [Since n0= 1]
For n0≥1, f(n)≥3n
2
So, worst case time complexity Ω(n
2
), where n0= 1 and c = 3.
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

58. Bubble Sort
Best Case Time Complexity Analysis - Little Oh Notation
f(n) = 1.5n
2
+1.5n<cn
2
Assume c = 2, then f(n) = 1.5n
2
+1.5n<2n
2
⇒30<32 [Since n0= 4]
For n0≥4, f(n)<2n
2
So, best case time complexity o(n
2
), where n0= 4 and c = 2.
Worst Case Time Complexity Analysis - Little Oh Notation
f(n) = 3.5n
2
-0.5n<cn
2
Assume c = 4, then f(n) = 3.5n
2
-0.5n<4n
2
⇒3<4 [Since n0= 1]
For n0≥1, f(n)<4n
2
So, worst case time complexity o(n
2
), where n0= 1 and c = 4.
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

59. Bubble Sort
Best Case Time Complexity Analysis - Little Omega Notation
f(n) = 1.5n
2
+1.5n>cn
2
Assume c = 1, then f(n) = 1.5n
2
+1.5n>n
2
⇒3>1 [Since n0= 1]
For n0≥1, f(n)>n
2
So, best case time complexityω(n
2
), where n0= 1 and c = 1.
Worst Case Time Complexity Analysis - Little Omega Notation
f(n) = 3.5n
2
-0.5n>cn
2
Assume c = 2, then f(n) = 3.5n
2
-0.5n>2n
2
⇒3>2 [Since n0= 1]
For n0≥1, f(n)>2n
2
So, worst case time complexityω(n
2
), where n0= 1 and c = 2.
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

60. Bubble Sort
Best Case Time Complexity Analysis - Theta Notation
c1n
2
≤f(n) = 1.5n
2
+1.5n≤c2n
2
Assume c1= 1 and c2= 2, then n
2
≤1.5n
2
+1.5n≤2n
2
⇒9≤18≤18 [Since n0= 3]
For n0≥3, n
2
≤f(n)≤2n
2
So, best case time complexityθ(n), where n0= 3, c1= 1 and c2= 2.
Worst Case Time Complexity Analysis - Theta Notation
c1n
2
≤f(n) = 2.5n
2
+4.5n-4≤c2n
2
Assume c1= 3 and c2= 4, then 3n
2
≤3.5n
2
-0.5n≤4n
2
⇒3≤3≤4 [Since n0= 1]
For n0≥1, 3n
2
≤f(n)≤4n
2
So, worst case time complexityθ(n
2
), where n0= 1, c1= 3 and c2= 4.
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

61. Bubble Sort
Space Complexity:
The variablesn,t,iandjoccupy a constant16 Bytesof memory.
Thefunction call,while loopandfor loopall come under the
auxiliary space and let’s assumeK Bytesall together.
The total space complexity is4n+16+K Bytes.Algorithm 12has a
space complexity ofO(n).
As the number ofextra variablesin the selection sort isfixed, the
space complexityof theseextra spacesisO(1).
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

62. Outline
1
Searching
Introduction
Linear Search
Binary Search
2
Sorting
Introduction
Insertion Sort
Selection Sort
Bubble Sort
Optimized Bubble Sort
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

63. Optimized Bubble Sort
An algorithm thatoutperforms the default bubble sortalgorithm is
said to be optimized.
An optimized bubble sort algorithm’s primary advantage is thatit
runs faster, which is beneficial for situations where performance is a
key consideration.
Algorithm 15Optimized Bubble Sort
1:procedureBubble-sort(A,n)
2:fori←0 ton−2do
3: swapped←0
4: forj←0 ton−i−2do
5: ifA[j]>a[j+1]then
6: t←A[j]
7: a[j]←A[j+ 1]
8: a[j+ 1]←t
9: swapped←1
10: end if
11: end for
12: if(swapped= 0)then
13: break
14: end if
15:end for
16:end procedure
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

64. Optimized Bubble Sort
No matter if the array is sorted before those number of iterations is
reached or not,regular bubble sort executes iterations equal to
the array size.
Aswap variableis used inoptimized bubble sorttotrackwhether
or not thelist has been sortedall the way through.
We might include thevariable swapas a new one. If there isan
element swap,swap’s value is set to true. It is set to false if it
isn’t.
The value ofswapping will be falseif there isno swapping after
an iteration. This means thatno more iterations are needed
because the elements have already been sorted.
This willmaximize bubble sort efficiencyand quicken the
procedure.
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

65. Optimized Bubble Sort
Table 2.2:
Step Best Case Worst Case Step Best Case Worst Case
1 1 1 9 0 n(n-1)/2
2 1 n 10 0 n(n-1)/2
3 1 n-1 11 n-1 n(n-1)/2
4 n n(n+1)/2 - 1 12 1 n-1
5 n-1 n(n-1)/2 13 1 0
6 0 n(n-1)/2 14 0 0
7 0 n(n-1)/2 15 0 n-1
8 0 n(n-1)/2 16 1 1
Frequency Count 3n+4 4n
2
+n-2
The best case time complexity is O(n) and worst case time complexity is
O(n
2
).
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

66. Optimized Bubble Sort
Best Case Time Complexity Analysis - Big Oh Notation
f(n) = 3n+4≤cn
Assume c = 4, then f(n) = 3n+4≤4n
⇒16≤16 [Since n0= 4]
For n0≥4, f(n)≤4n
So, best case time complexity O(n), where n0= 4 and c = 4.
Worst Case Time Complexity Analysis - Big Oh Notation
f(n) = 4n
2
+n-2≤cn
2
Assume c = 5, then f(n) = 4n
2
+n-2≤5n
2
⇒3≤5 [Since n0= 1]
For n0≥1, f(n)≤5n
2
So, worst case time complexity O(n
2
), where n0= 1 and c = 5.
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

67. Optimized Bubble Sort
Best Case Time Complexity Analysis - Big Omega Notation
f(n) = 3n+4≥cn
Assume c = 3, then f(n) = 3n+4≥3n
⇒7≥3 [Since n0= 1]
For n0≥1, f(n)≥3n
So, best case time complexity Ω(n), where n0= 1 and c = 3.
Worst Case Time Complexity Analysis - Big Omega Notation
f(n) = 4n
2
+n-2≥cn
2
Assume c = 4, then f(n) = 4n
2
+n-2≥4n
2
⇒16≥16 [Since n0= 2]
For n0≥2, f(n)≥4n
2
So, worst case time complexity Ω(n
2
), where n0= 2 and c = 4.
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

68. Optimized Bubble Sort
Best Case Time Complexity Analysis - Little Oh Notation
f(n) = 3n+4<cn
Assume c = 4, then f(n) = 3n+4<4n
⇒19<20 [Since n0= 5]
For n0≥5, f(n)<2n
2
So, best case time complexity o(n
2
), where n0= 5 and c = 2.
Worst Case Time Complexity Analysis - Little Oh Notation
f(n) = 4n
2
+n-2<cn
2
Assume c = 5, then f(n) = 4n
2
+n-2<5n
2
⇒3<5 [Since n0= 1]
For n0≥1, f(n)<5n
2
So, worst case time complexity o(n
2
), where n0= 1 and c = 5.
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

69. Optimized Bubble Sort
Best Case Time Complexity Analysis - Little Omega Notation
f(n) = 3n+4>cn
Assume c = 3, then f(n) = 3n+4>3n
⇒7>3 [Since n0= 1]
For n0≥1, f(n)>3n
So, best case time complexityω(n), where n0= 1 and c = 3.
Worst Case Time Complexity Analysis - Little Omega Notation
f(n) = 4n
2
+n-2>cn
2
Assume c = 4, then f(n) = 4n
2
+n-2>4n
2
⇒37>36 [Since n0= 3]
For n0≥3, f(n)>4n
2
So, worst case time complexityω(n
2
), where n0= 3 and c = 4.
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

70. Optimized Bubble Sort
Best Case Time Complexity Analysis - Theta Notation
c1n≤f(n) = 3n+4≤c2n
Assume c1= 3 and c2= 4, then 3n≤3n+4≤4n
⇒12≤16≤16 [Since n0= 4]
For n0≥4, 3n≤f(n)≤4n
So, best case time complexityθ(n), where n0= 4, c1= 3 and c2= 4.
Worst Case Time Complexity Analysis - Theta Notation
c1n
2
≤f(n) = 4n
2
+n-2≤c2n
2
Assume c1= 4 and c2= 5, then 4n
2
≤4n
2
+n-2≤5n
2
⇒16≤16≤20 [Since n0= 2]
For n0≥2, 4n
2
≤f(n)≤5n
2
So, worst case time complexityθ(n
2
), where n0= 2, c1= 4 and c2= 5.
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

71. Optimized Bubble Sort
Space Complexity:
The variablesn,i,swapped,jandtoccupy a constant20 Bytesof
memory. Thefunction call,while loopandfor loopall come under
the auxiliary space and let’s assumeK Bytesall together.
The total space complexity is4n+20+K Bytes.Algorithm 15has a
space complexity ofO(n).
As the number ofextra variablesin the selection sort isfixed, the
space complexityof theseextra spacesisO(1).
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

72. Summary
Here, we have discussed
Introduction to searching and sorting algorithms
Types of searching algorithms - Linear search and Binary search.
Basic iterative sorting - Bubble sort, Selection sort and Insertion sort.
Time and space complexity analysis of searching and sorting
algorithms.
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024

73. For Further Reading
E. Horowitz, S. Sahni and S. A. Freed.
Fundamentals of Data Structures in C (2
nd
edition).
Universities Press, 2008.
A. K. Rath and A. K. Jagadev.
Data Structures Using C (2
nd
edition).
Scitech Publications, 2011.
T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein.
Introduction to Algorithms (4
th
edition).
The MIT Press, 2022.
M. A. Weiss
Data Structures and Algorithm Analysis in C (2
nd
edition).
Pearson India, 2022.
Dr. Ashutosh Satapathy Searching and Sorting Algorithms March 9, 2024