Chapter – 8

Sorting
Sorting
The process of ordering elements in ascending or descending or any other specific order on
the basis of value, priority order etc is called sorting. Sorting can be categorized as internal
sorting and external sorting.
Internal sorting
Internal sorting means we are arranging the numbers within the array only which is in
computers primary memory.

External sorting
External sorting is the sorting of numbers from the external file by reading it from secondary
memory.
Use of sorting

We know that searching a sorted array is much easier than searching an unsorted array. The
following are some examples where sorting is used so that searching will be much easier.
➢ Words in a dictionary are sorted.
➢ The index of a book is sorted.
➢ The files in a directory are often listed in sorted order.
➢ A listing of course offering at university is sorted, first by department then by course
number.
➢ Many banks provide statements that list checks in increasing order by check number.

1. Bubble sort:
It is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements
if they are in wrong order. The basic idea of this sort is to pass through the array sequentially
several times. Each pass consists of comparing each element in the array with its adjacent
(successor) element (a [ i ] with a [ i + 1 ]) and interchanging the two elements if they are not
in the proper order.

Characteristics of Bubble sort

i. Large values are always sorted first.
ii. It only takes one iteration to detect that a collection is already sorted.
iii. The best time complexity for bubble sort is O(n). The average and worst time
complexity is O(𝑛2 ).
iv. The space complexity for bubble sort is O(1), because only single additional memory
space is required.

Compiled by: Nishanta Sharma

Algorithm
Step 1: Start

Step 2: For the first iterations, compare all the elements(n).

For the subsequent runs, compare(n - 1)(n - 2) and so on.
Step 3: Compare each element with its right side neighbour.
Step 4: Swap the smaller element to the left.

Step 5: Keep repeating steps 2,3 and 4 until whole list is covered.
Step 6: Stop.

Pseudo code

Compiled by: Nishanta Sharma

Time Complexity

Inner loop executes (n - 1) times when i = 0, (n - 2) times when i = 1 and so on:

Time Complexity = (n - 1) + (n - 2) + (n - 3) + … + 2 + 1
= n(n - 1) / 2 = O(𝑛2 )
There is no best case time complexity for this algorithm.

Compiled by: Nishanta Sharma

2. Selection Sort
Selection sort is about picking the smallest elements from the list and placing it in the sorted
portion of list. Initially, the first element is considered the minimum and compared with other
elements. During these Comparisions, if a smaller element is found then that is considered
the new minimum. After completion of one full round, the smallest element found is swapped
with the first element. This process continues till all the elements are sorted. The selection
sort works as follows:
Pass 1: Find the location loc of the smallest element from the list of n elements a[0], a[1],
a[2], … , a[n-1] and then interchange a[loc] and a[0].

Pass 2: Find the location loc of the smallest element from the sub – list of n – 1 elements
a[1], a[2], … , a[n-1] and then interchange a[loc] and a[1] such that a[0], a[1] are
sorted and so on.
Then finally we get the sorted list a[0] <= a[1] <= a[2]…,<=a [n-1]

Algorithm
Step 1: Start
Step 2: Consider the first element to be sorted and the rest to be unsorted.
Step 3: Assume the first element to be the smallest element.

Step 4: Check if the first element is smaller than each of other elements:
i. If yes, do nothing
ii. If no, choose the other smaller element as minimum and repeat step 3.
Step 5: After completion of one iteration through the list, swap the smallest element with
the first element of the list.
Step 6: Now consider the second with the first element of the list to be the smallest
element and so on till all the elements in the list are covered.
Step 7: Stop

Compiled by: Nishanta Sharma

Pseudo code

Compiled by: Nishanta Sharma

Time complexity:

Inner loop executes for (n - 1) times when i = 0, (n - 2) times when i = 1 and so on:
Time complexity = (n - 1) + (n - 2) + (n - 3) + … + 2 + 1
= O(𝑛2 )
There is no best case linear time complexity for this algorithm, but the number of swap
operations reduced greatly.
Space complexity:
Since no extra space besides 5 variables is needed for sorting.
Space Complexity = O(n)

Note: time complexity / Analysis is also called efficiency

Compiled by: Nishanta Sharma

3. Insertion Sort
In this method an element gets compared and inserted into the correct position in the list. To
apply this sort, we must consider one part of the list to be sorted and other to be unsorted.
To begin, consider the first element to be the sorted portion and the other elements of the
list to be unsorted. Now compare each element from the unsorted portion with the element
in the sorted portion. Then insert it in the correct position in the sorted part. This algorithm
works best with small number of elements.
The insertion sort works as follows:
Suppose an array a[n] with n elements.

Pass 1: a[0] by itself is trivially sorted.

Pass 2: a[1] is inserted either before or after a[0], a[1] is sorted.
Pass 3: a[2] is inserted into its proper place in a[0], a[1], a[2] is sorted.
Pass n: a[n - 1] is inserted into its proper place in a a[0], a[1], a[2],…,a[n - 2] so that a[0], a[1],
a[2],…,a[n-1] is sorted with n elements.

Algorithm
Step 1: Start
Step 2: Consider the first element to be sorted and rest to be unsorted.

Step 3: Compare with the second element

i. If the second element < the first element, insert the element in the correct position of
the sorted portion.
ii. Else, leave it as it is.

Step 4: Repeat 1 and 2 until all elements are sorted.

Step 5: Stop

Compiled by: Nishanta Sharma

Pseudo code

Compiled by: Nishanta Sharma

Time complexity:
The worst case runtime complexity of insertion sort is O(𝑛2 ) similar to that bubble sort.
However, insertion sort is considered better than bubble sort.
The best case time complexity is O(n).
Space complexity
Similar of selection sort[i.e O(n)]. Since no extra space requires besides 5 variable needed for
sorting.

Compiled by: Nishanta Sharma

4. Quick sort
Quick sort is developed by C.A.R Hoare which is unstable sorting. In practice this is the fastest
sorting method. It posses very good average case complexity among all the sorting algorithms.
This algorithm is based on the divide and conquer paradigm. The main idea behind this sorting
is partitioning of the elements.
Steps for Quick sort

Divide : Partition the array into two non – empty sub arrays.
Conquer : Two sub arrays are sorted recursively.
Combine: Two sub arrays are already sorted in place so no need to combine.

Algorithm
Step 1: Start
Step 2: Choose a pivot.
Step 3: Set a start pointer and end pointer.

Step 4: Compare the start pointer elements(start_element) with the pivot and the end pointer
element (end_element) with the pivot.
Step 5: Check if start_element <= pivot and end_element> pivot
i. If yes, increment the start pointer and decrement the end pointer.
ii. If not, swap the start_element and end_element.
Step 6: When start >= end, swap the pivot with end pointer.
Step 7: Repeat step 1 – 5 on the left half and the right half of the list till the entire list is
sorted.
Step 8: Stop

Compiled by: Nishanta Sharma

Pseudo code

Compiled by: Nishanta Sharma

Compiled by: Nishanta Sharma
Time complexity of quick sort algorithm
Best case:
Quick sort gives best time complexity when elements are divided into two partitions of equal
size therefore recurrence relation for this case is;
T(n) = 2T(n/2) + O(n)
By solving this recurrence, we get
T(n) = O(n logn)

Worst case:
Quick sort gives worst case when elements are already sorted. In this case one partition
contains the n – 1 elements and another partition contains no element.

T(n) = T(n-1) + O(n)

Therefore, its recurrence relation, we get
T(n) = O(𝑛2 )

Average case:

It is the case between best case and worst case. All permutation of the input numbers are
equally likely. On a random input array we will have a balanced and unbalanced splits. Good
and bad splits are randomly distributed across throughout the tree. Suppose we are alternate
Balanced, Unbalanced, Balanced.

B(n) = 2 UB(n/2)+© (n) Balanced

UB(n) = B(n-1) + ©(n) Unbalanced
𝑛
Solving B(n) = 2 (B(2 - - 1 ) + ©(n / 2) + © (n) )
𝑛
= 2 B (2 − 1 ) + © (n)

= © (n logn)

Compiled by: Nishanta Sharma

5. Merge Sort
It is an efficient sorting algorithm which involves merging two or more sorted files into a
third sorted file merging is the process of combining two or more sorted files into a third
sorted file. The merge sort algorithm is based on divide and conquer method.
The process of merge sort can be formalized into three basic operations

i. Divide the array into two sub arrays.

ii. Recursively sort the two sub arrays.
iii. Mere the newly sorted sub arrays.

Algorithm
Step 1: Start
Step 2: Split the unsorted list into groups recursively until there is one element per group.
Step 3: Compare each of the elements and then group them.

Step 4: Repeat step 2 until the whole list is merged and sorted in the process.
Step 5: Stop

Compiled by: Nishanta Sharma

Pseudo code

Compiled by: Nishanta Sharma

Compiled by: Nishanta Sharma
Time complexity
No of sub problems = 2

Size of each subproblem = n/2

Dividing cost = n
Thus recurrence relation for merge sort is;
T(n) = 1 , if n = 1

T(n) = 2T(n/2) + O(n) if n>1

By solving this recurrence relation, we get
Time complexity = T(n) =O(n logn)

6. Shell sort:
It is the first algorithm to improve on insertion sort. Its idea was to avoid the large amount of
data movement first by comparing elements that were far apart and then by comparing
elements that were less far apart and so on, gradually shrinking towards the basic insertion
sort.
The shell sort is a diminishing increment sort. This sort divides the original file into separate
sub files. These sub files contain every 𝑘 𝑡ℎ element of the original file. The value of k is called
increment.
For example, if there are n elements to be sorted and value of k is five then,

Sub – file 1: a[0] , a[5], a[10], a[15], …......

Sub – file 2: a[1] , a[6], a[11], a[16], …......
Sub – file 3: a[2] , a[7], a[12], a[17], ….....
Sub – file 4: a[3] , a[8], a[13], a[18], ….....
Sub – file 5: a[0] , a[5], a[10], a[15], …......

Algorithm:
Step 1: Start with an array ‘a’ of length ‘n’.

Step 2: Set the initial value of ‘gap’ to ‘n/2’.

Step 3: Repeat the following steps while ‘gap’ is greater than or equal to 1:

Compiled by: Nishanta Sharma

 i. Perform an insertion sort on the elements in the array ‘a’ using the current value of
‘gap’.
ii. Divide ‘gap’ by 2 to reduce it for the next iteration.

Step 4: The algorithm terminates when ‘gap’ becomes 0.

Pseudo code

Compiled by: Nishanta Sharma

Compiled by: Nishanta Sharma
Compiled by: Nishanta Sharma
Compiled by: Nishanta Sharma
7. Exchange sort:
The exchange is almost similar as the bubble sort. The exchange sort compares each
element of an array and swap those elements that are not in their proper position, just like
a bubble sort does. The only difference between the two sorting algorithms is the manner in
which they compares the elements.

Algorithm:
Step 1: Start
Step 2: Compares the element of the first position of the array with each elements of that
array and reverse them f they are not in the correct order.
Step 3: Repeat the same process for the elements of next position in the array.
Step 4: Continue the process until all the elements have been checked.
Step 5: The list of elements is now sorted.

Step 6: Stop

Pseudo code

Compiled by: Nishanta Sharma

Compiled by: Nishanta Sharma
Compiled by: Nishanta Sharma
8. Radix Sort
Radix sort is a linear sorting algorithm that sorts elements by processing them digit by digit.
It is an efficient sorting algorithm for integer or string with fixed – size keys. Rather than
comparing elements directly, Radix sort distributes the elements into buckets based on each
digit value. By repeatedly sorting the element by their significant digits, from the least
significant to the most significant, radix sort achieves the final sorted order.

Algorithm

Step 1: Define a function getMax(A,n) that takes an array ‘A’ and its length ‘n’ as input and
returns the maximum element max in the array.
Step 2: Define a function count_sort(A, n, pos) that takes an array A, its length n, and the
current digit position pos as inputs.
Step 3: Inside the count_sort function
i. Create an integer array count of size 10 and initialize all elements to 0.
ii. Loop through the array A to count the occurrences of each digit at the current
position pos and update the count array accordingly.
iii. Calculate the cumulative sum of the count array.
iv. Create a temporary array b of the same size as A to store the sorted elements.
Step 4: Perform the radix sort
i. Find the maximum element max in the array A using the getMax function.
ii. Start a loop with pos initialized to 1.

While max divided by pos is greater than 0, do the following:

i. Call the count_sort function passing A, n, and pos as arguments to sort the array
based on the current digit position pos.
ii. Multiply pos by 10 to move to the next digit position.
Step 5: After the loop in step 4 is completed, the array A will be sorted in ascending
order.

Compiled by: Nishanta Sharma

Pseudo code

Compiled by: Nishanta Sharma

Compiled by: Nishanta Sharma
Time complexity of radix sort = O(d *(n + k))
Space complexity = O(n + k)

Compiled by: Nishanta Sharma

9. Heap sort
Heap is a special tree based data structure, that satisfies the following special heap
properties;
i. Shape property:
Heap data structure is always a complete binary tree, which means all levels of the tree are
fully filled.
ii. Heap property:
Max heap
➢ For every node i, the value of node is less than or equal to its parent value except for the
root node.
A[ parent[ i ] ] >= A[i]

Compiled by: Nishanta Sharma

Min heap
➢ For every node i, the value of node is greater than or equal to its parents value except
for root node.
A[ parent[ i ] ] <= A[i]

Compiled by: Nishanta Sharma

Insertion in Heap Tree

Compiled by: Nishanta Sharma

Compiled by: Nishanta Sharma
Deletion in max heap

Compiled by: Nishanta Sharma

Compiled by: Nishanta Sharma
Example : heap sort

Compiled by: Nishanta Sharma

Compiled by: Nishanta Sharma
Heapify method
Heapify is the process of creating a heap data structure from a binary tree. It is used to create
a Min-heap or a max heap.

Algorithm
➢ Maxheapify takes three parameters: the array A, the size of the heap n, and the index
of the current node i.
➢ It initializes the variable largest to the current index i.
➢ It calculates the indices of the left and right children of the current node.
➢ It enters a while loop to find the largest element among the current node and its
children. If the left child is larger than the current largest node, it updates the largest
variable. Similarly, if the right child is larger, it also updates the largest variable.
➢ After the while loop, if the largest value is not the root (i.e., it's a child node), it swaps
the root with the largest element.
➢ Finally, if a swap occurred in the previous step, it recursively calls Maxheapify on the
affected sub-tree (the one with the new root, which was swapped in the previous
step).
➢ The heapsort function takes two parameters: the array A and the size of the array n.
➢ It first builds a max heap from the input array. Starting from the last non-leaf node
(which is at index n/2), it calls Maxheapify on each node to ensure that the entire
array becomes a valid max heap.
➢ After building the max heap, it enters a loop to delete elements from the heap and
place them in their correct positions to obtain the sorted array. It starts from the last
element of the array and iteratively swaps it with the root element (which is the
maximum value in the heap).
➢ After each swap, it reduces the size of the heap by one and calls Maxheapify on the
root to ensure that the remaining elements still form a max heap.

Compiled by: Nishanta Sharma

Compiled by: Nishanta Sharma
Compiled by: Nishanta Sharma
Heap as a priority queue

A heap is commonly used to implement a priority queue due to its efficient operations for
insertion and extraction of the highest (or lowest, depending on the type of heap) priority
element. A priority queue is an abstract data type that allows you to store a collection of
elements, each associated with a priority value. Elements with higher priority values are
dequeued before elements with lower priority values.
Here's how you can use a heap as a priority queue:
1. Create a Heap: To use a heap as a priority queue, you need to create a heap data structure
(e.g., binary heap, Fibonacci heap, etc.) that satisfies the heap property. For a max heap,
the parent's value is greater than its children, and for a min heap, the parent's value is
smaller than its children.
2. Enqueue (Insert) Operation: To insert an element with a given priority into the priority
queue, you perform the following steps:
a. Add the new element to the end of the heap (last position in the underlying array
representation).

Compiled by: Nishanta Sharma

 b. Bubble up the element by repeatedly swapping it with its parent until the heap
property is satisfied. In a max heap, the element will be swapped with its parent as
long as it has a higher priority.
3. Dequeue (Extract) Operation: To dequeue (remove) the highest-priority element from
the priority queue, you perform the following steps:
a. Swap the root element (highest priority) with the last element in the heap (last
position in the array).
b. Remove the last element (previously the root) from the heap.
c. Heapify the tree by performing the "heapify" operation (also known as "sink down" or
"trickle down") starting from the root node. This operation ensures that the heap
property is maintained.
The efficiency of using a heap as a priority queue comes from the logarithmic time complexity
of the insertion and extraction operations, which are O(log n) for binary heaps, where 'n' is
the number of elements in the heap.
Priority queues are commonly used in various algorithms and data structures, such as
Dijkstra's algorithm, Prim's algorithm, Huffman coding, and more. They provide a convenient
way to manage elements based on their priorities, allowing efficient access to the highest-
priority element at any given time.

Compiled by: Nishanta Sharma