Module 5: Searching and Sorting (Week 5)

5.1 Introduction
Searching and sorting are essential techniques for organizing and
manipulating data. Searching involves finding a specific element within a data
set, while sorting involves arranging the elements of a data set in a specific
order. Both techniques play a vital role in the performance and efficiency of
computer programs. There are various searching and sorting algorithms
available in programming, each with its own strengths and weaknesses
depending on the size, type, and complexity of the data. Examples of sorting
algorithms include Bubble Sort, Insertion Sort, Merge Sort, and Quick Sort,
while common searching algorithms include Linear Search and Binary
Search.

5.2 Searching Techniques

The process of finding a particular element of an array is called Searching. If
the item is not present in the array, then the search is unsuccessful. There
are two types of search algorithm (Linear search and Binary Search).

5.2.1 Linear Search

Linear search is also called a sequential search algorithm. The Linear
search compares each element of the array with the search key until the
search key is found. To determine that a value is not in the array, the program
must compare the search key to every element in the array. It is also called
“Sequential Search” because it traverses the data sequentially to locate the
element.

5.2.1.1 How Linear Search works

To understand the working of linear search algorithm, let us take an unsorted
array an example. Let the elements of array are:

Let the element to be searched is K = 41. Now, start from the first element and
compare K with each element of the array.

Page 1 of 31
The value of K, i.e., 41, does not match with the first element of the array. So,
move to the next element. And follow the same process until the respective
element is found.

Now, the element to be searched is found. Therefore, the algorithm will return
the index of the element matched

5.2.1.2 Linear Search Algorithm

The Linear Search Algorithm is stated below:

(Linear Search) LINEAR (DATA, N, ITEM, LOC)

[Here DATA is a linear array with N elements, and ITEM is a given item
of information. This algorithm finds the location LOC of ITEM in DATA,
or Sets LOC =0 if the search is unsuccessful.]

Page 2 of 31
 1. [Insert ITEM at the end of DATA.] Set DATA [N + I]: = ITEM.
2. [Initialize counter] Set LOC:= 1.
3. [Search for ITEM.]
Repeat while DATA[LOC] ≠ ITEM:
Set LOC:=LOC+1.
(End of loop.]
4. [Successful?] If LOC = N + 1, then: Set LOC: = 0.
5. Exit.

5.2.1.3 Complexity of Linear Search

The Time and Space complexity of the Linear Search is given below:

(a) Time Complexity

The time complexity of linear search in the best case, average case, and
worst case is presented in the space below.

Case Time Description

Complexity
Best Case O (1) In Linear search, best case occurs when the
element we are finding is at the first position of
the array. The best-case time complexity of
linear search is O (1).
Average Case O(n) The average case time complexity of linear
search is O(n).
Worst Case O(n) In Linear search, the worst case occurs when
the element we are looking is present at the
end of the array. The worst-case in linear
search could be when the target element is not
present in the given array, and we have to
traverse the entire array. The worst-case time
complexity of linear search is O(n).

The time complexity of linear search is O(n) because every element in the
array is compared only once.

(b) Space Complexity

The space complexity of linear search is O(1). The Linear Search algorithm
takes up no extra space; its space complexity is O(1) for an array of n
elements.

Page 3 of 31
5.2.1.4 Program Codes
Implement the Linear Search Algorithm using Java and C++

5.2.2 Binary Search

Binary search is a fast search algorithm with run-time complexity of Ο(log n).
This search algorithm works on the principle of divide and conquer. For this
algorithm to work properly, the data collection should be in the sorted form.

The Binary search algorithm can only be used with sorted array and
eliminates one half of the elements in the array being searched after each
comparison. The algorithm locates the middle element of the array and
compares it to the search key. If they are equal, the search key is found and
array subscript of that element is returned. Otherwise, the problem is reduced
to searching one half of the array. If the search key is less than the middle
element of array, the first half of the array is searched. If the search key is not
the middle element of in the specified sub array, the algorithm is repeated on
one quarter of the original array. The search continues until the sub array
that consist of one element that is equal to the search key (search successful).
But if Search-key not found in the array then the value of END of new selected
range will be less than the START of new selected range.

5.2.2.1 How Binary Search Algorithm works

Binary Search Algorithm can be implemented in two ways which are
discussed below.

(a) Iterative Method

(b) Recursive Method

The recursive method follows the divide and conquer approach. The general
steps for both methods are discussed below.

For a Binary search to work, it is mandatory for the target array to be sorted.
We shall learn the process of binary search with a pictorial example. The
following is our sorted array and let us assume that we need to search the
location of value 31 using binary search.

First, we shall determine half of the array by using this formula:

Page 4 of 31
 mid = low + (high - low) / 2

Here it is, 0 + (9 - 0) / 2 = 4 (integer value of 4.5). So, 4 is the mid of the array.

Now, we compare the value stored at location 4, with the value being searched,
i.e. 31. We find that the value at location 4 is 27, which is not a match. As the
value is greater than 27 and we have a sorted array, so we also know that the
target value must be in the upper portion of the array.

We change our low to mid + 1 and find the new mid value again.
low = mid + 1
mid = low + (high - low) / 2

Our new mid is 7 now. We compare the value stored at location 7 with our
target value 31.

The value stored at location 7 is not a match, rather it is more than what we
are looking for. So, the value must be in the lower part from this location.

Hence, we calculate the mid again. This time it is 5.

Page 5 of 31
We compare the value stored at location 5 with our target value. We find that
it is a match.

We conclude that the target value 31 is stored at location 5. Binary search

halves the searchable items and thus reduces the count of comparisons to be
made to very less numbers.

5.2.2.2 Binary Search Algorithm

The Binary Search Algorithm is given below:

BINARY (DATA, LB, UB, ITEM, LOC)

[Here DATA is a sorted array with lower bound LB and upper bound
UB, and ITEM is a given item of information. The variables BEG, END
and MID denote, respectively, the beginning, end and middle locations
of a segment of elements of DATA. This algorithm finds the location LOC
of ITEM in DATA or sets LOC = NULL]

1. [Initialize segment variables.]

Set BEG:= LB. END := UB and MID := INT((BEG+ END)/2).
2. Repeat Steps 3 and 4 while BEG ≤ END and DATA[MID] ≠ ITEM.
3. If ITEM < DATA[MID], then:
Set END:= MID —1.
Else:
Set BEG:= MID + 1.
[End of If structure.]
4. Set MID:= INT((BEG + END)/2).
[End of Step 2 loop.]
5. If DATA[MID] = ITEM, then:
Set LOC:= MID.
Else:
Set LOC:= NULL.
[End of If structure.)
6. Exit.

5.2.2.3 Complexity of Binary Search Algorithm

The time and space complexity of Binary search algorithm.
(a) Time Complexity: The time complexity of Binary search in the best
case, average case, and worst case is given in the table below.

Page 6 of 31
 Case Time Description
Complexity
Best Case O(1) In Binary search, best case occurs when the
element to search is found in first comparison, i.e.,
when the first middle element itself is the element
to be searched. The best-case time complexity of
Binary search is O(1).
Average O(logn) The average case time complexity of Binary search
Case is O(logn)
Worst O(logn) In Binary search, the worst case occurs, when we
Case have to keep reducing the search space till it has
only one element. The worst-case time complexity of
Binary search is O(logn).

(b) Space Complexity: The space complexity of Binary search is O(1). The
Binary Search algorithm takes up no extra space; its space
complexity is O(n) for an array of n elements.

5.2.2.4 Program Codes

Implement the Binary search algorithm in C++ and Java

5.3 Sorting Techniques

Sorting refers to the operation of arranging data in some given order. Such as
increasing or decreasing, with numeric data or alphabetically, with string
data. There are many sorting and searching algorithms. The particular
algorithm one chooses depends on the properties of the data and the
operations one may perform on the data. Accordingly, we will want to know
the complexity of each algorithm; that is, we will want to know the running
time f(n) of each algorithm as a function of the number n of input items.
Sometimes, we will also discuss the space requirements of our algorithms.

Sorting and searching frequently apply to a file of records, so we recall some

standard terminology. Each record in a file F can contain many fields, but
there may be one particular field whose values uniquely determine the records
in the file. Such a field K is called a primary key, and the values k1, k2 , . . .kn
in such a field are called keys or key values. Sorting the file F usually refers
to sorting F with respect to a particular primary key, and searching in F refers
to searching for the record with a given key value

Let A be a list of n elements A1 , A2, ..., An in memory. Sorting A refers to the

operation of rearranging the contents of A so that they are increasing in order
(numerically or lexicographically), that is, so that

Page 7 of 31
 A1 ≤ A2 ≤ . . . ≤ An

Since A has n elements, there are n! ways that the contents can appear in A.
These ways correspond precisely to the n! permutations of 1, 2.... . n.
Accordingly, each sorting algorithm must take care of these n! possibilities.

5.3.1 Types of Sorting

(a) Internal sorting and External Sorting
Any Sorting algorithm that uses the main memory exclusively during the sort
process is known as an Internal sorting algorithm. In Internal sorting, the data
can be accessed extremely fast and randomly. The internal sorting technique
is used when data items are less than enough to be held in the main memory
(RAM). Bubble sort, Insertion sort and Quicksort algorithms are examples of
Internal sorting.

For sorting larger datasets, it may be necessary to hold only a smaller chunk
of data in memory at a time, since all input data will not all fit in the RAM.
The rest of the data is normally held on some larger, but slower medium, like
a hard disk or any other storage device. The sorting of these large datasets is
called External sorting.

(b) In-place Sorting and Not-in-place Sorting

Sorting algorithms may require some extra space for comparison and
temporary storage of a few data elements.

Those algorithms do not require any extra space and sorting is said to happen
in-place, or for example, within the array itself are called In-place sorting.
Bubble sort, Insertion sort, Selection sort, Quicksort and Heap sort are
examples of in-place sorting.

However, in some sorting algorithms, the program requires space that is more
than or equal to the elements being sorted. Sorting that uses equal or more
space is called Not in-place sorting. Merge sort and radix sort are examples of
non-in-place sorting.

(c) Stable and Not Stable Sorting

The Stability of an algorithm matters when we wish to maintain the sequence
of original elements, like in a tuple for example

A Sorting algorithm is said to be stable if two objects with equal keys appear
in the same order in sorted output as they appear in the input data set. The
diagram explains the stable sorting algorithms. Sorting Algorithm such as
Insertion Sort, Merge Sort and Bubble Sort are stable by nature.

Page 8 of 31
As the diagram depicts, our unsorted list has two fives. The first 5 is in a white
slot and the second one is in a gray slot. After sorting, in the sorted sequence
also, the 5 in the white slot remains before the 5 in the gray slot. This is an
example of a stable sort.

Unstable sorting algorithms do not maintain the relative ordering of elements

of equal values in a sorted sequence. The following diagram will help in
understanding the unstable sorting. Quicksort, Heapsort and Selection sort
are examples of unstable sorting.

As the diagram depicts, our unsorted list has two fives. The first 5 is in a white
slot and the second one is in a gray slot. After sorting, in the sorted sequence
also, the 5 in the white slot appears after the 5 in the gray slot.

(d) Adaptive and Non-Adaptive Sorting Algorithm

A Sorting algorithm is said to be adaptive, if it takes advantage of already
'sorted' elements in the list that is to be sorted. That is, while sorting if the
source list has some element already sorted, adaptive sorting algorithms will
take this into account and will try not to re-order them. The order of elements
affects the complexity of Adaptive sorting algorithm. Bubble sort, Insertion
sort, and Quicksort algorithms are examples of adaptive sorting algorithms.

A non-adaptive algorithm is one which does not take into account the
elements which are already sorted. A non-adaptive sorting algorithm tries to
force all the items into sorted order. In a non-adaptive algorithm, the time
complexity remains the same for any order of the array. This helps in

Page 9 of 31
situations when the order of elements cannot be guessed or are not known
beforehand. Selection sort, Merge sort and Heap sort are examples of non-
adaptive sorting algorithms.

5.3.2 Other Important Sorting Concepts

Some terms are generally coined while discussing sorting techniques, here is
a brief introduction to them.

(a) Increasing Order

A sequence of values is said to be in increasing order, if the successive
element is greater than the previous one. For example, 1, 3, 4, 6, 8, 9 are
in increasing order, as every next element is greater than the previous
element.

(b) Decreasing Order

A sequence of values is said to be in decreasing order, if the successive
element is less than the current one. For example, 9, 8, 6, 4, 3, 1 are in
decreasing order, as every next element is less than the previous element.

(c)Non-Increasing Order
A sequence of values is said to be in non-increasing order, if the successive
element is less than or equal to its previous element in the sequence. This
order occurs when the sequence contains duplicate values. For example,
9, 8, 6, 3, 3, 1 are in non-increasing order, as every next element is less
than or equal to (in case of 3) but not greater than any previous element.

(d) Non-Decreasing Order

A sequence of values is said to be in non-decreasing order, if the
successive element is greater than or equal to its previous element in the
sequence. This order occurs when the sequence contains duplicate values.
For example, 1, 3, 3, 6, 8, 9 are in non-decreasing order, as every next
element is greater than or equal to (in case of 3) but not less than the
previous one.

5.4 Bubble Sort Algorithm

Bubble sort algorithm, also known as Sinking sort is comparison-based
algorithm in which each pair of adjacent elements is compared and the
elements are swapped if they are not in order. It is called bubble sort because
the movement of array elements is just like the movement of air bubbles in
the water. Bubbles in water rise up to the surface; similarly, the array
elements in bubble sort move to the end in each iteration.
Although it is simple to use, it is primarily used as an educational tool because
the performance of bubble sort is poor in the real world. It is not suitable for

Page 10 of 31
large data sets. This algorithm is not suitable for large data sets as its average
and worst-case complexity are O(n2) of where n is the number of items.

5.4.1 How Bubble Sort Algorithm works

Suppose the list of numbers A [1], A[2].... . A[N] is in memory. The bubble sort
algorithm works as follows:

Step I: Compare A [1] and A [2] and arrange them in the desired order, so that
A[1] <A(2].Then compare A[2] and A[3] and arrange them so that A[2] < A[3].
Then compare A [3] and A [4] and arrange them so that A[3]< A[4]. Continue
until we compare A[N – 1] with A[N] and arrange them so that A[N – 1] < A[N].
▪ Observe that Step I involves is n- I comparisons. (During Step 1, the
largest element is "bubbled up" to the nth position or "sinks" to the nth
position.) When Step 1 is completed, A[N] will contain the largest
element.

Step 2: Repeat Step 1 with one less comparison; that is, now we stop after we
compare and possibly rearrange A[N-2] and A[N–1]. (Step 2 involves N–2
comparisons, and when Step 2 is completed, the second largest element will
occupy A [N–1]

Step 3: Repeat Step I with two fewer comparisons; that is, we stop after we
compare and possibly rearrange A [N – 3] and A[N – 2].

Step N – 1: Compare A [1] with A[2] and arrange them so that A[1]< A[2].

Let assume we want to sort the array with the values given as {7,2,9,6,4} in
ascending order. Since the array contains five elements, that means four
comparisons must be performed for the most significant (greatest) element to
bubble to the top of the array. The number comparison is N- 1 where N is the
size of the array. In this case, the number of comparisons is 5 - 1 = 4.

The sorting process will proceed as shown below:

First Pass
▪ Compare the first and second elements, starting with the first index.
▪ They are swapped if the first element is greater than the second.
▪ Compare the second and third elements now. If they are not in the
correct order, swap them.
▪ The preceding procedure is repeated until it reaches the final element.

Page 11 of 31
Second Pass
▪ The process is repeated for the remaining iterations.
▪ The most significant element among the unsorted elements is placed at
the end of each iteration.

Third Pass
▪ The comparison is performed up to the last unsorted element in each
iteration.

Page 12 of 31
Fourth Pass
▪ When all of the unsorted elements are placed in their correct
positions, the array is sorted.

5.4.2 Bubble Sort Algorithm

The Bubble sort algorithm is given below:
BUBBLESORT (DATA, N)
[Here, DATA is an array with N elements. This algorithm sorts the
elements in DATA.]

1.Repeat Steps 2 and 3 for K= 1 to N- I.

2. Set PTR:= 1. [Initializes pass pointer PTR]
3. Repeat while PTR ≤ N - K: [Executes pass.]
(a) If DATA[PTR] > DATA [PTR + 1], then:
Interchange DATA[PTR] and DATA[PTR+1.]
[End of If structure.]
(b) Set PTR: = PTR + 1.
[End of inner loop.]
[End of Step I outer loop.]
4. Exit.

5.4.3 Optimized Bubble sort Algorithm

In the bubble sort algorithm, comparisons are made even when the array is
already sorted. Because of that, the execution time increases. To solve it, we
can use an extra variable swapped. It is set to true if swapping is required;
otherwise, it is set to false. It will be helpful, as suppose after an iteration, if
there is no swapping required, the value of variable swapped will be false. It
means that the elements are already sorted, and no further iterations are
required. This method will reduce the execution time and also optimizes the
bubble sort.

The algorithm for Optimized Bubble Sort Algorithm is given below:

Bubblesort (array, n)
n = length(array)
repeat
swapped = false
for i = 1 to n - 1
if array [i - 1] > array[i], then
swap (array[i - 1], array[i])

Page 13 of 31
 swapped = true
end if
end for
n=n-1
until not swapped
end Bubblesort

5.4.4 Complexity of Bubble Sort Algorithm

The time and space complexity of the Bubble sort algorithm is given below

(a) Time Complexity

The time complexity of bubble sort in the best case, average case, and worst
case is given in the table below:

Case Time Description

Complexity
Best Case O(n) It occurs when there is no sorting required, i.e. the
array is already sorted. The best-case time
complexity of bubble sort is O(n).
Average O(n2) It occurs when the array elements are in jumbled
Case order, that is, when not properly in ascending and
descending order. The average case time
complexity of bubble sort is O(n2).
Worst O(n2) It occurs when the array elements are required to
Case be sorted in reverse order. That means suppose
you have to sort the array elements in ascending
order, but its elements are in descending order.
The worst-case time complexity of bubble sort
is O(n2).

(b) Space Complexity

▪ The space complexity of bubble sort is O(1) and this is because, in
bubble sort, an extra variable is required for swapping.

▪ The space complexity of optimized bubble sort is O(2). It is because

two extra variables are required in optimized bubble sort.

5.4.5 Implementation of Bubble Sort Algorithm in Java and C++

Implementation both the Bubble sort and Optimized Bubble sort algorithm in
C++ and Java.

Page 14 of 31
5.5 Insertion Sort Algorithm
Insertion sort works similar to the sorting of playing cards in hands. It is
assumed that the first card is already sorted in the card game, and then we
select an unsorted card. If the selected unsorted card is greater than the first
card, it will be placed at the right side; otherwise, it will be placed at the left
side. Similarly, all unsorted cards are taken and put in their exact place.

Insertion sort is a simple sorting algorithm that virtually splits the given array
into sorted and unsorted parts, then the values from the unsorted parts are
picked and placed at the correct position in the sorted part. The idea behind
insertion sort is that first take one element, iterate it through the sorted array.

Although it is simple to use, it is not appropriate for large data sets as the
time complexity of insertion sort in the average case and worst case is O(n2),
where n is the number of items. Insertion sort is less efficient than the other
sorting algorithms like heap sort, quick sort, merge sort, etc.

5.5.1 How Insertion Sort works

Suppose an array A with N elements A[0], A[1], . . . . A[N-1] is in memory. The
insertion sort algorithm scan A from A[0] to A[N-1], inserting each element
A[K] into its proper position in the previously sorting sub array A[0], A[1], . . .
.A[K-1].

The steps are:

▪ Pass 1: A[1] is inserted either before of after A[0] so that: A[0],

A[1] is sorted.

▪ Pass 2: A[2] is inserted into its proper place in A[0], A[1], so that
A[0], A[1], A[2] are sorted.

▪ Pass 3: A[3] is inserted into its proper place in A[0], A[1], A[2] so
that: A[0], A[1], A[2], A[3] are sorted.
. ......................................................
..
▪ Pass N-1: A[N-1] is inserted into its proper place in A[0], A[1], . . . . .
A[N-1] so that: A[0], A[1], . . . . A[N-1] are sorted.

This sorting algorithm is frequently used when N is small. There remains only
the problem of deciding how to insert A[K] in its proper place in the subarray
A[0], A[1],. . . . A[K-1]. This can be accomplished by comparing A[K] with A[K-
1], comparing A[K] with A[K-2], comparing A[K] with A[K-3], and so on, until
first meeting an element A[i] (where i start from k-1) such that A[i] ≤ A[K].

Page 15 of 31
Then each of elements A[K-1], A[K-2], . . . . A[i+1] is moved forward one
location, and A[K] is then inserted in the i+1st position in the array.

The following examples demonstrate how Insertion sort algorithm

Example 1: Let the array {6, 2, 11, 7, 5} be sorted in ascending order.

The Insertion sort works as:

Firstly (Pass 1)
▪ It selects the second element (2).
▪ It checks whether it is smaller than any of the elements before it.
▪ Since 2 < 6, so it shifts 6 towards right and places 2 before it.
▪ The resulting list is 2, 6, 11, 7, 5.

Secondly (Pass 2)
▪ It selects the third element (11).
▪ It checks whether it is smaller than any of the elements before it.
▪ Since 11 > (2, 6), so no shifting takes place.
▪ The resulting list remains the same.

Thirdly (Pass 3)
▪ It selects the fourth element (7).
▪ It checks whether it is smaller than any of the elements before it.
▪ Since 7 < 11, so it shifts 11 towards right and places 7 before it.
▪ The resulting list is 2, 6, 7, 11, 5.

Fourthly (Pass 4)
▪ It selects the fifth element (5).
▪ It checks whether it is smaller than any of the elements before it.
▪ Since 5 < (6, 7, 11), so it shifts (6, 7, 11) towards right and places 5
before them.
▪ The resulting list is 2, 5, 6, 7, 11.

As a result, sorted elements in ascending order are: 2, 5, 6, 7, 11

Another way to show how Insertion Sort works is with examples below:

Example 2: Suppose we need to sort the following array {9 5 1 4 3}.

First Pass
The first element in the array is assumed to be sorted. Take the second
element and store it separately in key. Compare key with the first element. If

Page 16 of 31
the first element is greater than key, then key is placed in front of the first
element.

Second Pass
Now, the first two elements are sorted. Take the third element and compare it
with the elements on the left of it. Placed it just behind the element smaller
than it. If there is no element smaller than it, then place it at the beginning of
the array.

Third Pass
Similarly, place every unsorted element at its correct position.

Page 17 of 31
Fourth Pass
The last place every unsorted element at its correct position

Example 3: Assuming the array to be sorted contains the following

data: 80, 77, 33, 44, 11, 88, 22, 66, 55

Page 18 of 31
5.5.2 Insertion Sort Algorithm
The Insertion sort algorithm is:

Algorithm: (INSERTION SORT)

INSERTION (A, N)
[Where A is an array and N is the Size of values in the array ]
1. Repeat steps 2 to 4 for K=1,2,3, . . . . . N-1:
2. Set TEMP = A[K] and i =K-1.
3. Repeat while i >= 0 and TEMP < A[i]
(a) Set A[i+1] = A[i]. [Moves element forward.]
(b) Set i = i -1.
[End of loop.]
4. Set A[i+1] =TEMP. [Insert element in proper place.]
End of Step 2 loop.]
5 Return

5.5.3 Complexity of Insertion Sort Algorithm

The time and space complexity of Insertion sort algorithm is depicted in the
table below:

Case Time Description

Complexity
Best O(n) It occurs when there is no sorting required, i.e.,
the array is already sorted. The best-case time
complexity of insertion sort is O(n).
Average O(n2) It occurs when the array elements are in
jumbled order, that is, not properly ascending
and descending order. The average case time
complexity of insertion sort is O(n2).
Worst O(n2) It occurs when the array elements are required
to be sorted in reverse order. That means
suppose you have to sort the array elements in
ascending order, but its elements are in
descending order. The worst-case time
complexity of insertion sort is O(n2).
Space O(1) The space complexity of insertion sort is O(1). It
Complexity is because, in insertion sort, an extra variable
is required for swapping.
Stability Yes Insertion sort is a stable algorithm

5.5.4 Implementation of Insertion Sort Algorithm in C++ and Java

Implement the Insertion sort algorithm using C++ and Java.

Page 19 of 31
5.6 Selection Sort Algorithm
In Selection sort, the smallest value among the unsorted elements of the array
is selected in every pass and inserted to its appropriate position into the array.
It is also the simplest algorithm. It is an in-place comparison sorting
algorithm. In this algorithm, the array is divided into two parts, first is sorted
part, and another one is the unsorted part. Initially, the sorted part of the
array is empty, and unsorted part is the given array. Sorted part is placed at
the left, while the unsorted part is placed at the right.

In Selection sort, the first smallest element is selected from the unsorted array
and placed at the first position. After that second smallest element is selected
and placed in the second position. The process continues until the array is
entirely sorted.

The average and worst-case complexity of selection sort is O(n2), where n is

the number of items. Due to this, it is not suitable for large data sets.

5.6.1 How Selection Sort works

Suppose an array A with N elements A [0], A [1], . . . A[N-1] Is in memory. The
Selection sort algorithm for sorting an array A works as follows. First find the
smallest element in the list and put it in the first position. Then find the
second smallest element in the list and put it the second position. And so on.

Pass 1: Find the location LOC of the smallest in the list of N elements A[0],
A[1], . . . . . A[N-1], and then interchange A[LOC] and A[0]. Then: A[0]
is sorted.

Pass 2: Find the location LOC of the smallest in the sub-list of N-1 elements
A[1],A[2], . . . A[N-1], and interchange A[LOC] and A[1]. Then: A[0],
A[1] is sorted. Since A[0] ≤ A[1].

...........................................................
...........................................................

Pass N-1: Find the location LOC of the smallest A[N-2] and A[N-1], and then
interchanged A[LOC] and A[N-1]. Then: A[0], A[1], A[2], . . . . A[N-1]
is sorted.

For example, suppose we need to sort the Array with the following elements:
{77,33, 44, 11,88,22, 66, 55}

Page 20 of 31
The sorting process is shown in the table below:

5.6.2 Selection Sort Algorithm

The Selection sort algorithm contain two algorithms, the algorithm MIN (K, N,
LOC) find the location of the smallest elements in the array while the algorithm
SELECTION (A,N) carry out the sorting.

Algorithm: MIN (A, K, N, LOC)

[An Array A is in memory. This procedure finds the location Loc of the
smallest element among A[K], A[K+1], . . . . .A[N-1].]
1. Set MIN = A[K] and LOC = K. [Initializes pointers.]
2. Repeat for J=K+1, K+2, . . . . . N:
If MIN > A[J], then: MIN = A[J] and LOC = J.
3. Return LOC.

Algorithm: (SELECTION SORT) SELECTION (A, N)

1. Repeat steps 2 and 3 for K=0,1,2, . . . . . N-2:
2. Call MIN (A, K, N, LOC).
3. [Interchange A[K] and A[LOC].]
Set TEMP = A[K], A[K] = A[LOC] and A[LOC] = TEMP.
[End of step 1 loop.]
4. Exit

Page 21 of 31
5.6.3 Complexity of Selection Sort Algorithm
The time and space complexity of selection sort in best case, average case,
and in worst case is shown in the table below:

Case Time Description

Complexity
Best Case O(n2) It occurs when there is no sorting required,
i.e. the array is already sorted. The best-case
time complexity of selection sort is O(n2).
Average Case O(n2) It occurs when there is no sorting required,
i.e. the array is already sorted. The best-case
time complexity of selection sort is O(n2).
Worst Case O(n2) It occurs when the array elements are
required to be sorted in reverse order. That
means suppose you have to sort the array
elements in ascending order, but its elements
are in descending order. The worst-case time
complexity of selection sort is O(n2).
Space O(1) The space complexity of selection sort is O(1).
Complexity It is because, in selection sort, an extra
variable is required for swapping.
Stability Yes

5.6.4 Implementation of Selection Sort Algorithm in C++ and Java

Implement the Selection sort algorithm using C++ and Java.

5.7 Quicksort Algorithm

Quicksort is a fast-sorting algorithm that works by splitting a large array of
data into smaller sub-arrays. This implies that each iteration works by
splitting the input into two components, sorting them, and then recombining
them. For big datasets, the technique is highly efficient since its average and
best-case complexity is O(n*logn).

It was created by Tony Hoare in 1961 and remains one of the most effective
general-purpose sorting algorithms available today. It works by recursively
sorting the sub-lists to either side of a given pivot and dynamically shifting
elements inside the list around that pivot.

As a result, the quick sort method can be summarized in three steps:

▪ Pick: Select an element.

Page 22 of 31
 ▪ Divide: Split the problem set, move smaller parts to the left of the pivot
and larger items to the right.
▪ Repeat and combine: Repeat the steps and combine the arrays that
have previously been sorted.

Quicksort picks an element as pivot, and then it partitions the given array
around the picked pivot element. In quick sort, a large array is divided into
two arrays in which one holds values that are smaller than the specified
value (Pivot), and another array holds the values that are greater than the
pivot. After that, left and right sub-arrays are also partitioned using the
same approach. It will continue until the single element remains in the sub-
array.

Choosing the pivot

Picking a good pivot is necessary for the fast implementation of quicksort.
However, it is typical to determine a good pivot. Some of the ways of
choosing a pivot are as follows:

▪ Pivot can be random, i.e., select the random pivot from the given
array.
▪ Pivot can either be the rightmost element of the leftmost element of
the given array.
▪ Select median as the pivot element.

5.7.1 How Quick Sort works

To understand the working of quick sort, lets take an unsorted array. Let the
elements of array be:

In the given array, we consider the leftmost element as pivot. So, in this case,
a[left] = 24, a[right] = 27 and a[pivot] = 24. Since, pivot is at left, so algorithm
starts from right and move towards left.

Page 23 of 31
Now, a[pivot] < a[right], so algorithm moves forward one position towards left,
i.e.

Now, a[left] = 24, a[right] = 19, and a[pivot] = 24. Because, a[pivot] > a[right],
so, algorithm will swap a[pivot] with a[right], and pivot moves to right, as:

Now, a[left] = 19, a[right] = 24, and a[pivot] = 24. Since, pivot is at right, so
algorithm starts from left and moves to right. As a[pivot] > a[left], so algorithm
moves one position to right as:

Now, a[left] = 9, a[right] = 24, and a[pivot] = 24. As a[pivot] > a[left], so
algorithm moves one position to right as:

Page 24 of 31
Now, a[left] = 29, a[right] = 24, and a[pivot] = 24. As a[pivot] < a[left], so, swap
a[pivot] and a[left], now pivot is at left, i.e.

Since, pivot is at left, so algorithm starts from right, and move to left. Now,
a[left] = 24, a[right] = 29, and a[pivot] = 24. As a[pivot] < a[right], so algorithm
moves one position to left, as:

Now, a[pivot] = 24, a[left] = 24, and a[right] = 14. As a[pivot] > a[right], so,
swap a[pivot] and a[right], now pivot is at right, i.e.

Now, a[pivot] = 24, a[left] = 14, and a[right] = 24. Pivot is at right, so the
algorithm starts from left and move to right.

Now, a[pivot] = 24, a[left] = 24, and a[right] = 24. So, pivot, left and right are
pointing the same element. It represents the termination of procedure.
Element 24, which is the pivot element is placed at its exact position.

Page 25 of 31
Elements that are right side of element 24 are greater than it, and the
elements that are left side of element 24 are smaller than it.

Now, in a similar manner, quick sort algorithm is separately applied to the

left and right sub-arrays. After sorting gets done, the array will be:

5.7.2 Quicksort Algorithm

Let A be a list of n data items. Quick sort is an algorithm of the divide-and-
conquer type. That is, the problem of sorting a set is reduced to the problem
of sorting two smaller sets.

Algorithm: QUICKSORT (A, LEFT, RIGHT)

1. If LEFT ≥ RIGHT, then: Return.
2. Set MIDDLE = PARTITION (A, LEFT, RIGHT).
3. Call QUICKSORT (A, LEFT, MIDDLE-1).
4. Call QUICKSORT (A, MIDDLE+1, RIGHT).
5. Return.

Algorithm: PARTITION (A, LEFT, RIGHT)

1. Set X = A[LEFT].
2. Set I = LEFT.
3. Repeat for j = LEFT+1,LEFT+2, . . . . . RIGHT
If A[j] < X, then:
Set i = i+1.
Call SWAP (A[i], A[j]).
4. Call SWAP (A[i], A[LEFT].
5. Return i.

Page 26 of 31
5.7.3 Complexity of Quicksort Algorithm
The time complexity of quicksort in best case, average case, and in worst case
and the space complexity of quicksort are shown in the table below:

Case Time Description

Complexity
Best Case O(n*log n) In Quicksort, the best-case occurs when the pivot
element is the middle element or near to the middle
element. The best-case time complexity of quicksort
is O(n*logn).
Average O(n*log n) It occurs when the array elements are in jumbled order
Case that is not properly ascending and not properly
descending. The average case time complexity of
quicksort is O(n*logn).
Worst Case O(n2) In quick sort, worst case occurs when the pivot
element is either greatest or smallest element.
Suppose, if the pivot element is always the last element
of the array, the worst case would occur when the
given array is sorted already in ascending or
descending order. The worst-case time complexity of
quicksort is O(n2). Worst case in quicksort can be
avoided by choosing the right pivot element. Though
the worst-case complexity of quicksort is more than
other sorting algorithms such as Merge
sort and Heap sort, still it is faster in practice. Worst
case in quick sort rarely occurs because by changing
the choice of pivot, it can be implemented in different
ways.

Space O(n*logn) The space complexity of quicksort is O(n*logn).

Complexity
Stability NO Quicksort is not a stable sorting algorithm

5.7.4 Implementation in C++and Java

Implement the Quick sort algorithm in C++ and Java

5.8 Merge Sort Algorithm

Suppose A is sorted list with r elements and B is a sorted list with s elements.
The operation that combines the elements of A and B into a single sorted list
C with n = r + s elements is called merging. One simple way to merge is to
place the elements of C after the elements of A and then use some sorting
algorithm on the entire list. This method does not take advantage of the fact

Page 27 of 31
that A and B are individually sorted. A much more efficient algorithm is Merge
sort algorithm.

Merge sort is similar to the quick sort algorithm as it uses the divide and
conquer approach to sort the elements. It is one of the most popular and
efficient sorting algorithms. It divides the given list into two equal halves, calls
itself for the two halves and then merges the two sorted halves. We have to
define the merge () function to perform the merging.

The sub-lists are divided again and again into halves until the list cannot be
divided further. Then we combine the pair of one element lists into two-
element lists, sorting them in the process. The sorted two-element pairs are
merged into the four-element lists, and so on until we get the sorted list.

In Merge sort, a problem is divided into multiple sub-problems. Each sub-

problem is solved individually. Finally, sub-problems are combined to form
the final solution. The diagram below shows how the Merge sort works:

Page 28 of 31
5.8.1 How Merge Sort works

To understand the working of the merge sort algorithm, lets take an unsorted
array whose elements are:

According to the merge sort, first divide the given array into two equal halves.
Merge sort keeps dividing the list into equal parts until it cannot be further
divided. As there are eight elements in the given array, so it is divided into two
arrays of size 4.

Now, again divide these two arrays into halves. As they are of size 4, so divide
them into new arrays of size 2.

Now, again divide these arrays to get the atomic value that cannot be further
divided.

Now, combine them in the same manner they were broken. In combining, first
compare the element of each array and then combine them into another array
in sorted order. So, first compare 12 and 31, both are in sorted positions.
Then compare 25 and 8, and in the list of two values, put 8 first followed by
25. Then compare 32 and 17, sort them and put 17 first followed by 32. After
that, compare 40 and 42, and place them sequentially.

Page 29 of 31
In the next iteration of combining, now compare the arrays with two data
values and merge them into an array of found values in sorted order.

Now, there is a final merging of the arrays. After the final merging of above
arrays, the array will look like:

Now, the array is completely sorted.

5.8.2 Merge Sort Algorithm

The Merge Sort algorithm and Merge algorithm are given below:

Algorithm: MERGESORT (A, N)

1. If N=1, Return.
2. Set N1:=N/2, N2:=N-N1.
3. Repeat for i=0,1,2 . . . . . (N1-1)
Set L [i]=A [i].
4. Repeat for j=0,1,2 . . . . . (N2-1)
Set R [j]=A [N1+j].
5. Call MERGESORT (L, N1).
6. Call MERGESORT (R, N2).
7. Call MERGE (A, L, N1, R,N2).
8. Return

Algorithm: MERGE (A, L, N1, R, N2)

1. Set i:=0, j:=0.
2. Repeat for k=0,1,2 . . . . . (N1+N2-1)
If i<N1, then:
If j=N2 or L [i] ≤ R [j], then:
Set A [k] =L [i].
Set i=i+1;
Else:
If j < N2, then:
Set A [k]=R [j].
Set j=j+1.
[Endif]
[Endif]

Page 30 of 31
 [End Repeat Loop]
3. Return

5.8.3 Complexity of Merge Sort Algorithm

The time complexity of merge sort in the best case, average case, and worst
case, and the space complexity of the merge sort are given in the table below:

Case Time Description

Complexity
Best Case O(n*log n) It occurs when there is no sorting required, i.e., the
array is already sorted. The best-case time complexity
of merge sort is O(n*logn).
Average O(n*log n) It occurs when the array elements are in a jumbled
Case order that is not properly ascending and not properly
descending. The average case time complexity of
merge sort is O(n*logn).
Worst Case O(n*log n) It occurs when the array elements are required to be
sorted in reverse order. That mean suppose you have
to sort the array elements in ascending order, but its
elements are in descending order. The worst-case time
complexity of merge sort is O(n*logn).

Space O(n) The space complexity of merge sort is O(n) and this is
Complexity because, in merge sort, an extra variable is required
for swapping.
Stability YES Merge sort is a stable sorting algorithm

5.8.4 Implementation in C++ andJava

Implement the Merge sort algorithm in C++ and Java.

Page 31 of 31