UNIT – VII

SORTING
def:-
 Sorting refers to arranging data in a particular format. Sorting algorithm specifies the way to
arrange data in a particular order. Most common orders are in numerical or lexicographical order.
 The importance of sorting lies in the fact that data searching can be optimized to a very high
level if data is stored in a sorted manner.
 Sorting is also used to represent data in more readable formats.

 Following are some of the examples of sorting in real-life scenarios −

 Telephone Directory − The telephone directory stores the telephone numbers of people sorted
by their names, so that the names can be searched easily.
 Dictionary − The dictionary stores words in an alphabetical order so that searching of any word
becomes easy.
 Contact List in Your Mobile Phone also contains all contacts arranged alphabetically
(lexicographically). So, if we look for contact then you don’t have to look randomly and can be
searched easily and many others like Apps on your phone.
 Keywords in Your book are also in a lexicographical manner and you can find it according to
2
There are two different categories in sorting:

 Internal sorting: If the input data is such that it can be adjusted in the main memory at once, it is called internal sorting.

 External sorting: If the input data is such that it cannot be adjusted in the memory entirely at once, it needs to be stored in a

hard disk, floppy disk, or any other storage device. This is called external sorting.

 In-place Sorting and Not-in-place Sorting

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

•These algorithms do not require any extra space and sorting is said to happen in-place, or for example, within the array itself.

•This is called in-place sorting. Bubble sort is an example of in-place sorting.

•However, in some sorting algorithms, the program requires space which is more than or equal to the elements being sorted.

•Sorting which uses equal or more space is called not-in-place sorting. Merge-sort is an example of not-in-place sorting.

3
Stable and Not Stable Sorting

 If a sorting algorithm, after sorting the contents, does not change the sequence of similar content in which they appear, it is
called stable sorting.

• If a sorting algorithm, after sorting the contents, changes the sequence of similar content in which they appear, it is
called unstable sorting.
• Stability of an algorithm matters when we wish to maintain the sequence of original elements, like in a tuple for example.

4
 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 algorithms will take this into account and will try
not to re-order them.
 A non-adaptive algorithm is one which does not take into account the elements which are already sorted. They try to force
every single element to be re-ordered to confirm their sortedness.
 For example, Insertion sort is an adaptive sorting algorithm like in the case if input is already sorted then we know that time
complexity will be O(n). That’s why If the input array is almost sorted then choose insertion sort, though this is not the only
thing to be kept in mind for Insertion sort over other sorting algorithms.
 Merge Sort is a “Non-Adaptive” Sorting algorithm because the order of the elements in the array doesn’t matter So the time
complexity of algorithm will always be O(nlogn).
Adaptive sorting algorithms:
Bubble Sort
Insertion Sort
Quick Sort
Non-adaptive sorting algorithms:
Selection Sort
Merge Sort
5
Heap Sort
 Important Terms

Some terms are generally coined while discussing sorting techniques, here is a brief introduction to them −
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.
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.
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.
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.
6
Asymptotic Analysis
•The efficiency of an algorithm depends on the amount of time, storage and other resources required to execute the
algorithm. The efficiency is measured with the help of asymptotic notations.
•An algorithm may not have the same performance for different types of inputs. With the increase in the input size,
the performance will change.

• The study of change in performance of the algorithm with the change in the order of the input size is defined as
asymptotic analysis.

Asymptotic Notations
 Asymptotic notations are the mathematical notations used to describe the running time of an algorithm when the
input tends towards a particular value or a limiting value.
 For example: In bubble sort, when the input array is already sorted, the time taken by the algorithm is linear i.e. the
best case.
 But, when the input array is in reverse condition, the algorithm takes the maximum time (quadratic) to sort the
elements i.e. the worst case.
 When the input array is neither sorted nor in reverse order, then it takes average time. These durations are denoted
using asymptotic notations.
 There are mainly three asymptotic notations: Big-O notation Omega notation Theta notation 7
Big-O Notation (O-notation)
 Big-O notation represents the upper bound of the running time of an algorithm.
 Thus, it gives the worst-case complexity of an algorithm.
 Big-O gives the upper bound of a function
O(g(n)) = { f(n): there exist positive constants c and n0

such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n }

 The above expression can be described0 as a
function f(n) belongs to the set O(g(n)) if there exists a
positive constant c such that it lies between 0 and cg(n), for
sufficiently large n.

 For any value of n, the running time of an algorithm does

not cross the time provided by O(g(n)).

 Since it gives the worst-case running time of an algorithm, it

is widely used to analyze an algorithm as we are always
interested in the worst-case scenario.

8
Omega Notation (Ω-notation)

 Omega notation represents the lower bound of the running time of an algorithm.
 Thus, it provides the best case complexity of an algorithm.
 Omega gives the lower bound of a function

Ω(g(n)) = { f(n): there exist positive constants c and n0

such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0 }

 The above expression can be described as a

function f(n) belongs to the set Ω(g(n)) if there exists a positive
constant c such that it lies above cg(n), for sufficiently large n.

 For any value of n, the minimum time required by the algorithm

is given by Omega Ω(g(n)).

9
Theta Notation (Θ-notation)
 Theta notation encloses the function from above and below. Since it represents the upper and the lower bound of
the running time of an algorithm, it is used for analyzing the average-case complexity of an algorithm.
 Theta bounds the function within constants factors
 For a function g(n), Θ(g(n)) is given by the relation:

Θ(g(n)) = { f(n): there exist positive constants c1, c2 and n0

such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0 }

 The above expression can be described as a function f(n) belongs
to the set Θ(g(n)) if there exist positive constants c 1 and c2 such that
it can be sandwiched between c1g(n) and c2g(n), for sufficiently
large n.

 If a function f(n) lies anywhere in between c1g(n) and c2g(n) for all n
≥ n0, then f(n) is said to be asymptotically tight bound.

10
Common Asymptotic Notations

Following is a list of some common asymptotic notations −

constant − Ο(1)
logarithmic − Ο(log n)
linear − Ο(n)
binary − Ο(n log n)
quadratic − Ο(n2)
cubic − Ο(n3)
polynomial − nO(1)
exponential − 2Ο(n)
11
Efficiency of Sorting:-

Which sorting is best in data structures?

•Every sorting algorithms have their own advantages and disadvantages.
•Select the sorting algorithm that is best fitted for your data.
•If you’re constrained in space, then choose heap sort.
•If you need something stable choosing merge sort will help you.
•For almost sorted data, considering insertion sort is O(n) time!
•Inbuilt sorting algorithms use hybrid sorts which are combination of different basic sorting algorithms.
•Introsort (std::sort in C++) which runs quick sort and switches to heap sort when the recursion gets too deep.
•This way, we’ll get the fast performance of quick sort in practice while guaranteeing a worst-case O(nlogn) run time.

Which sort is the fastest?

•Quicksort is one of the fastest sorting algorithms. It is also considered to be the best sorting algorithm.
•Some of its features are that it is basically a comparison sort and can be done in-place in an array, however,
inefficient implementation, it’s not a stable sort.
•Though the worst-case complexity is O(n^2), on an average it gives us O(nlogn) time complexity.
•We can also think of considering Merge sort, which is very similar to Quicksort but has more complexity than 12
Bubble Sort

13
Bubble Sort

 Bubble sort is the easiest sorting algorithm to implement.

 It is inspired by observing the behavior of air bubbles over foam.
 It is an in-place sorting algorithm.
 It uses no auxiliary data structures (extra space) while sorting.

How Bubble Sort Works?

 Bubble sort uses multiple passes (scans) through an array.

 In each pass, bubble sort compares the adjacent elements of the array.
 It then swaps the two elements if they are in the wrong order.
 In each pass, bubble sort places the next largest element to its proper position.
 In short, it bubbles down the largest element to its correct position.

14
The bubble sort algorithm is given below- Optimization Of Bubble Sort Algorithm-
for(int pass=1 ; pass<=n-1 ; ++pass)  If the array gets sorted after a few passes like one or two, then ideally the
{ algorithm should terminate.
for(int i=0 ; i<=n-2 ; ++i)
{  But still the above algorithm executes the remaining passes which costs extra
if(A[i] > A[i+1]) comparisons.
swap(i,i+1,A);
} The optimized bubble sort algorithm is shown below-
}
void swap(int x, int y, int[] A) for (int pass=1 ; pass<=n-1 ; ++pass)
{ {
int temp = A[x]; flag=0 // flag denotes are there any swaps done in pass
A[x] = A[y]; for (int i=0 ; i<=n-2 ; ++i)
A[y] = temp; {
return ; if(A[i] > A[i+1])
} {
swap(i,i+1,A);
flag=1 // After swap, set flag to 1
}
}
if(flag == 0) break; // No swaps indicates we can terminate loop
}
void swap(int x, int y, int[] A)
{
int temp = A[x];
A[x] = A[y];
A[y] = temp;
return; 15
}
Explanation-

 To avoid extra comparisons, we maintain a flag variable.

 The flag variable helps to break the outer loop of passes after obtaining the sorted array.
 The initial value of the flag variable is set to 0.
 The zero value of flag variable denotes that we have not encountered any swaps.
 Once we need to swap adjacent values for correcting their wrong order, the value of flag variable is set to 1.
 If we encounter a pass where flag == 0, then it is safe to break the outer loop and declare the array is sorted.

16
Time Complexity Analysis-
 Bubble sort uses two loops- inner loop and outer loop.
 The inner loop deterministically performs O(n) comparisons.
Worst Case-
• In worst case, the outer loop runs O(n) times.
 Hence, the worst case time complexity of bubble sort is O(n x n) = O(n 2).
Best Case-
• In best case, the array is already sorted but still to check, bubble sort performs O(n) comparisons.
 Hence, the best case time complexity of bubble sort is O(n).
Average Case-
• In average case, bubble sort may require (n/2) passes and O(n) comparisons for each pass.
 Hence, the average case time complexity of bubble sort is O(n/2 x n) = Θ(n 2).
Time Complexity

The following table summarizes the time complexities of bubble sort in each case- Best Case O(n)
Average Case Θ(n2)
Worst Case O(n2)
17
From here, it is clear that bubble sort is not at all efficient in terms of time complexity of its algorithm.
Space Complexity Analysis-

 Bubble sort uses only a constant amount of extra space for variables like flag, i, n.
 Hence, the space complexity of bubble sort is O(1).
 It is an in-place sorting algorithm i.e.; it modifies elements of the original array to sort the given array.

Properties-

Some of the important properties of bubble sort algorithm are-

 Bubble sort is a stable sorting algorithm.
 Bubble sort is an in-place sorting algorithm.
 The worst-case time complexity of bubble sort algorithm is O(n2).
 The space complexity of bubble sort algorithm is O(1).
 Number of swaps in bubble sort = Number of inversion pairs present in the given array.
 Bubble sort is beneficial when array elements are less, and the array is nearly sorted.

18
Bubble Sort Example-
•Consider the following array A-

•Now, we shall implement the above bubble sort algorithm on this array.
Step-1:
 We have pass=1 and i=0.
 We perform the comparison A[0] > A[1] and swaps if the 0th element is greater than the 1st element.
 Since 6 > 2, so we swap the two elements.

Step-2:
 We have pass=1 and i=1.
 We perform the comparison A[1] > A[2] and swaps if the 1st element is greater than the 2nd element.
 Since 6 < 11, so no swapping is required.

19
Step-3:
• We have pass=1 and i=2.
 We perform the comparison A[2] > A[3] and swaps if the 2nd element is greater than the 3rd element.
 Since 11 > 7, so we swap the two elements.

Step-4:
 We have pass=1 and i=3.
 We perform the comparison A[3] > A[4] and swaps if the 3rd element is greater than the 4th element.
 Since 11 > 5, so we swap the two elements.

20
Finally, after the first pass, we see that the largest element 11 reaches its correct position.
Step-5:
 Similarly, after pass=2, element 7 reaches its correct position.
 The modified array after pass=2 is shown below-

Step-6:
 Similarly, after pass=3, element 6 reaches its correct position.
 The modified array after pass=3 is shown below-

Step-7:
 No further improvement is done in pass=4.
 This is because at this point, elements 2 and 5 are already present at their correct positions.
 The loop terminates after pass=4.
 Finally, the array after pass=4 is shown below-

21
Quick Sort

22
Quick Sort

 Quick Sort is a famous sorting algorithm.

 It sorts the given data items in ascending order.
 It uses the idea of divide and conquer approach.
 It follows a recursive algorithm.

How Does Quick Sort Works?

 Quick Sort follows a recursive algorithm.

 It divides the given array into two sections using a partitioning element called as pivot.
 The division performed is such that-
All the elements to the left side of pivot are smaller than pivot.
All the elements to the right side of pivot are greater than pivot.
• After dividing the array into two sections, the pivot is set at its correct position.
• Then, sub arrays are sorted separately by applying quick sort algorithm recursively.

23
Quick Sort Algorithm-
Partition_Array (a , beg , end , loc)
Begin
Consider- Set left = beg , right = end , loc = beg
Set done = false
 a = Linear Array in memory While (not done) do
While ( (a[loc] <= a[right] ) and (loc ≠ right) ) do
 beg = Lower bound of the sub array in question Set right = right - 1
 end while
end = Upper bound of the sub array in question if (loc = right) then
Set done = true
else if (a[loc] > a[right]) then
Interchange a[loc] and a[right]
Then, Quick Sort Algorithm is as follows- Set loc = right
end if
if (not done) then
While ( (a[loc] >= a[left] ) and (loc ≠ left) ) do
Set left = left + 1
end while
if (loc = left) then
Set done = true
else if (a[loc] < a[left]) then
Interchange a[loc] and a[left]
Set loc = left
end if
end if
end while
End
24
Quick Sort Analysis

 To find the location of an element that splits the array into two parts, O(n) operations are required.
 This is because every element in the array is compared to the partitioning element.
 After the division, each section is examined separately.
 If the array is split approximately in half (which is not usually), then there will be log 2n splits.
 Therefore, total comparisons required are f(n) = n x log2n = O(nlog2n).

Order of Quick Sort = O(nlog2n)

Worst Case-
 Quick Sort is sensitive to the order of input data.
 It gives the worst performance when elements are already in the ascending order.
 It then divides the array into sections of 1 and (n-1) elements in each call.
 Then, there are (n-1) divisions in all.
 Therefore, here total comparisons required are f(n) = n x (n-1) = O(n 2).

Order of Quick Sort in worst case = O(n2)

25
Advantages of Quick Sort-

 Quick Sort is an in-place sort, so it requires no temporary memory.

 Quick Sort is typically faster than other algorithms. (because its inner loop can be efficiently implemented on most
architectures)
 Quick Sort tends to make excellent usage of the memory hierarchy like virtual memory or caches.
 Quick Sort can be easily parallelized due to its divide and conquer nature.

Disadvantages of Quick Sort-

 The worst-case complexity of quick sort is O(n2).

 This complexity is worse than O(nlogn) worst case complexity of algorithms like merge sort, heap sort etc.
 It is not a stable sort i.e. the order of equal elements may not be preserved.

26
Quick Sort Example-

Consider the following array to be sorted in ascending order using quick sort algorithm-

Quick Sort Algorithm works in the following steps-

Step-1:
Initially-
 Left and Loc (pivot) points to the first element of the array.
 Right points to the last element of the array.
So to begin with, we set loc = 0, left = 0 and right = 5 as-

27
Step-2:
Since loc points at left, so algorithm starts from right and move towards left.
As a[loc] < a[right], so algorithm moves right one position towards left as-
Now, loc = 0, left = 0 and right = 4.

Step-3:
Since loc points at left, so algorithm starts from right and move towards left.
As a[loc] > a[right], so algorithm swaps a[loc] and a[right] and loc points at right as-
Now, loc = 4, left = 0 and right = 4.

Step-4:
Since loc points at right, so algorithm starts from left and move towards right.
As a[loc] > a[left], so algorithm moves left one position towards right as-
Now, loc = 4, left = 1 and right = 4

28
Step-5:

Since loc points at right, so algorithm starts from left and move towards right.
As a[loc] > a[left], so algorithm moves left one position towards right as-
Now, loc = 4, left = 2 and right = 4.

Step-6:

Since loc points at right, so algorithm starts from left and move towards right.
As a[loc] < a[left], so we algorithm swaps a[loc] and a[left] and loc points at left as-
Now, loc = 2, left = 2 and right = 4.

Step-7:

Since loc points at left, so algorithm starts from right and move towards left.
As a[loc] < a[right], so algorithm moves right one position towards left as-
Now, loc = 2, left = 2 and right = 3. 29
Step-8:
Since loc points at left, so algorithm starts from right and move towards left.
As a[loc] > a[right], so algorithm swaps a[loc] and a[right] and loc points at right as-
Now, loc = 3, left = 2 and right = 3.
Step-9:
Since loc points at right, so algorithm starts from left and move towards right.
As a[loc] > a[left], so algorithm moves left one position towards right as-
Now, loc = 3, left = 3 and right = 3.
Now,
 loc, left and right points at the same element.
 This indicates the termination of procedure.
 The pivot element 25 is placed in its final position.
 All elements to the right side of element 25 are greater than it.
 All elements to the left side of element 25 are smaller than it.

Now, quick sort algorithm is applied on the left and right sub arrays separately the similar manner. 30
Selection Sort

31
Selection Sort
 Selection sort is one of the easiest approaches to sorting.
 It is inspired from the way in which we sort things out in day-to-day life.
 It is an in-place sorting algorithm because it uses no auxiliary data structures while sorting.

How Selection Sort Works?

Consider the following elements are to be sorted in ascending order using selection sort-
6, 2, 11, 7, 5
Selection sort works as-
 It finds the first smallest element (2).
 It swaps it with the first element of the unordered list.
 It finds the second smallest element (5).
 It swaps it with the second element of the unordered list.
 Similarly, it continues to sort the given elements.
As a result, sorted elements in ascending order are-
2, 5, 6, 7, 11
32
Selection Sort Algorithm-
Let A be an array with n elements. Then, selection sort algorithm used for sorting is as follows-
for (i = 0 ; i < n-1 ; i++)
{
index = i;
for(j = i+1 ; j < n ; j++)
{
if(A[j] < A[index])
index = j;
}
temp = A[i];
A[i] = A[index];
A[index] = temp;
}
Here,
 i = variable to traverse the array A
 index = variable to store the index of minimum element
 j = variable to traverse the unsorted sub-array
 temp = temporary variable used for swapping 33
Time Complexity Analysis-
Time Complexity
 Selection sort algorithm consists of two nested loops. Best Case n2
 Owing to the two nested loops, it has O(n2) time complexity. Average Case n2

Space Complexity Analysis- Worst Case n2

 Selection sort is an in-place algorithm.

 It performs all computation in the original array and no other array is used.
 Hence, the space complexity works out to be O(1).

Important Notes-

 Selection sort is not a very efficient algorithm when data sets are large.
 This is indicated by the average and worst case complexities.
 Selection sort uses minimum number of swap operations O(n) among all the sorting algorithms

34
Selection Sort Example-

Consider the following elements are to be sorted in ascending order-

6, 2, 11, 7, 5

The above selection sort algorithm works as illustrated below-

Step-1: For i = 0

Step-2: For i = 1

35
Step-3: For i = 2

Step-4: For i = 3

Step-5: For i = 4
Loop gets terminated as ‘i’ becomes 4.
The state of array after the loops are finished is as shown-
 With each loop cycle,

The minimum element in unsorted sub-array is selected.

It is then placed at the correct location in the sorted sub-array until array A is completely sorted. 36
Insertion Sort

37
Insertion Sort

 Insertion sort is an in-place sorting algorithm.

 It uses no auxiliary data structures while sorting.
 It is inspired from the way in which we sort playing cards.

How Insertion Sort Works?

Consider the following elements are to be sorted in ascending order-

6, 2, 11, 7, 5
Insertion sort works as-
Firstly,
 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.
38
Secondly,
 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,
 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,
 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 39
Insertion Sort Algorithm-

Let A be an array with n elements. The insertion sort algorithm used for sorting is as follows-

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

{
key = A [ i ];
j = i - 1;
while(j > 0 && A [ j ] > key)
{
A [ j+1 ] = A [ j ];
j--;
}
A [ j+1 ] = key;
}
Here,
 i = variable to traverse the array A
 key = variable to store the new number to be inserted into the sorted sub-array
 j = variable to traverse the sorted sub-array
40
Time Complexity Analysis-
Time Complexity

 Best Case n
Selection sort algorithm consists of two nested loops.
 Owing to the two nested loops, it has O(n2) time complexity. Average Case n2
Worst Case n2

Space Complexity Analysis-

 Selection sort is an in-place algorithm.

 It performs all computation in the original array and no other array is used.
 Hence, the space complexity works out to be O(1).

Important Notes-

 Insertion sort is not a very efficient algorithm when data sets are large.
 This is indicated by the average and worst case complexities.
 Insertion sort is adaptive and number of comparisons are less if array is partially sorted.
41
Insertion Sort Example-

Consider the following elements are to be sorted in ascending order-

6, 2, 11, 7, 5

The above insertion sort algorithm works as illustrated below-

Step-1: For i = 1

Step-2: For i = 2

42
Step-3: For i = 3

2 5 11 7 6 For j = 2; 11 > 7 so A[3] = 11

2 5 11 11 6 For j = 1; 5 < 7 so loop stops and A[2] = 7
2 5 7 11 6 After inner loop ends
Working of inner loop when i = 3
Step-4: For i = 4

Loop gets terminated as ‘i’ becomes 5. The state of array after the loops are finished-

With each loop cycle,

 One element is placed at the correct location in the sorted sub-array until array A is completely sorted.
43
Merge Sort

44
Merge Sort

 Merge sort is a famous sorting algorithm.

 It uses a divide and conquer paradigm for sorting.
 It divides the problem into sub problems and solves them individually.
 It then combines the results of sub problems to get the solution of the original problem.

How Merge Sort Works?

 Before learning how merge sort works, let us learn about the merge procedure of merge sort algorithm.
 The merge procedure of merge sort algorithm is used to merge two sorted arrays into a third array in sorted
order.
 Consider we want to merge the following two sorted sub arrays into a third array in sorted order-

45
The merge procedure of merge sort algorithm is given below-
Step-1:

 Create two variables i and j for left and right sub arrays.
 Create variable k for sorted output array.

Step-02:

 We have i = 0, j = 0, k = 0.
 Since L[0] < R[0], so we perform A[0] = L[0] i.e. we copy the first element from left sub
array to our sorted output array.
 Then, we increment i and k by 1.

Then, we have-

46
Step-3:

 We have i = 1, j = 0, k = 1.
 Since L[1] > R[0], so we perform A[1] = R[0] i.e. we copy the first
element from right sub array to our sorted output array.
 Then, we increment j and k by 1.
Then, we have-

Step-4:

 We have i = 1, j = 1, k = 2.
 Since L[1] > R[1], so we perform A[2] = R[1].
 Then, we increment j and k by 1.
Then, we have-

47
Step-5:

 We have i = 1, j = 2, k = 3.
 Since L[1] < R[2], so we perform A[3] = L[1].
 Then, we increment i and k by 1.
Then, we have-

Step-6:

 We have i = 2, j = 2, k = 4.
 Since L[2] > R[2], so we perform A[4] = R[2].
 Then, we increment j and k by 1.

Then, we have-

48
Step-7:

 Clearly, all the elements from right sub array have been added to the sorted output array.
 So, we exit the first while loop with the condition while(i<nL && j<nR) since now j>nR.
 Then, we add remaining elements from the left sub array to the sorted output array using next while loop.

Finally, our sorted output array is-

Basically,
 After finishing elements from any of the sub arrays, we can add
the remaining elements from the other sub array to our sorted
output array as it is.
 This is because left and right sub arrays are already sorted.

Time Complexity
 The above mentioned merge procedure takes Θ(n) time.
 This is because we are just filling an array of size n from left & right sub arrays by incrementing i and j at most Θ(n) times.

49
Merge Sort Algorithm-

Merge Sort Algorithm works in the following steps-

 It divides the given unsorted array into two halves- left and right sub arrays.
 The sub arrays are divided recursively.
 This division continues until the size of each sub array becomes 1.
 After each sub array contains only a single element, each sub array is sorted trivially.
 Then, the above discussed merge procedure is called.
 The merge procedure combines these trivially sorted arrays to produce a final sorted array.

The division procedure of merge sort algorithm which uses recursion is in next slide….

50
The merge procedure of merge sort algorithm is given below-
// L : Left Sub Array , R : Right Sub Array , A : Array
merge(L, R, A)
{
nL = length(L) // Size of Left Sub Array
nR = length(R) // Size of Right Sub Array
i=j=k=0
while(i<nL && j<nR){ /* When both i and j are valid i.e. when both the sub arrays have elements to insert in A */
if(L[i] <= R[j])
{ MergeSort(A) // A : Array that needs to be sorted
A[k] = L[i] {
k = k+1 n = length(A)
i = i+1 if n<2 return
}
else{ mid = n/2
A[k] = R[j] left = new_array_of_size(mid) // Creating temporary array
k = k+1 for left
j = j+1 right = new_array_of_size(n-mid) // and right sub arrays
}}// Adding Remaining elements from left sub array to array A for(int i=0 ; i<=mid-1 ; ++i)
while(i<nL) { {
A[k] = L[i]
i = i+1 left[i] = A[i] // Copying elements from A to left
k = k+1 }
}// Adding Remaining elements from right sub array to array A for(int i=mid ; i<=n-1 ; ++i)
while(j<nR) { {
A[k] = R[j] right[i-mid] = A[i] // Copying elements from A to right
j = j+1
k = k+1 }
} MergeSort(left) // Recursively solving for left sub array
} MergeSort(right) // Recursively solving for right sub array
merge(left, right, A) // Merging two sorted left/right sub 51
Merge Sort Example-
Ex.1 Consider the following elements have to be sorted in ascending order-

Ex.2 The merge sort algorithm works as-

52
Time Complexity Analysis-
 In merge sort, we divide the array into two (nearly) equal halves and solve them recursively using merge sort only.
 So, we have-

 Finally, we merge these two sub arrays using merge procedure which takes Θ(n) time as explained above.
 If T(n) is the time required by merge sort for sorting an array of size n, then the recurrence relation for time
complexity of merge sort is-

 On solving this recurrence relation, we will get T(n) = Θ(nlogn).

53
 Thus, time complexity of merge sort algorithm is T(n) = Θ(nlogn).
Space Complexity Analysis-

 Merge sort uses additional memory for left and right sub arrays.
 Hence, total Θ(n) extra memory is needed.

Properties-

Some of the important properties of merge sort algorithm are-

 Merge sort uses a divide and conquer paradigm for sorting.
 Merge sort is a recursive sorting algorithm.
 Merge sort is a stable sorting algorithm.
 Merge sort is not an in-place sorting algorithm.
 The time complexity of merge sort algorithm is Θ(nlogn).
 The space complexity of merge sort algorithm is Θ(n).

NOTE
Merge sort is the best sorting algorithm in terms of time complexity Θ(nlogn)
if we are not concerned with auxiliary space used. 54
Shell Sort

55
Shell Sort
 Shell sort is the generalization of insertion sort, which overcomes the drawbacks of insertion sort by comparing
elements separated by a gap of several positions.
 It is a sorting algorithm that is an extended version of insertion sort. Shell sort has improved the average time
complexity of insertion sort. As like insertion sort, it is a comparison-based and in-place sorting algorithm. Shell
sort is efficient for medium-sized data sets.
 In insertion sort, at a time, elements can be moved ahead by one position only. To move an element to a far-
away position, many movements are required that increase the algorithm's execution time.
 But shell sort overcomes this drawback of insertion sort. It allows the movement and swapping of far-away
elements as well.
 This algorithm first sorts the elements that are far away from each other, then it subsequently reduces the gap
between them. This gap is called as interval.
 This interval can be calculated by using the Knuth's formula given below -

1. hh = h * 3 + 1
2. where, 'h' is the interval having initial value 1. 56
Shell sort Algorithm

The simple steps of achieving the shell sort are listed as follows –

1. ShellSort(a, n) // 'a' is the given array, 'n' is the size of array

2. for (interval = n/2; interval > 0; interval /= 2)
3. for ( i = interval; i < n; i += 1)
4. temp = a[i];
5. for (j = i; j >= interval && a[j - interval] > temp; j -= interval)
6. a[j] = a[j - interval];
7. a[j] = temp;
8. End ShellSort

57
Working of Shell sort Algorithm

Let the elements of array are -

 We will use the original sequence of shell sort, i.e., N/2, N/4,....,1 as the intervals.
 In the first loop, n is equal to 8 (size of the array), so the elements are lying at the interval of 4 (n/2 = 4).
 Elements will be compared and swapped if they are not in order.
 Here, in the first loop, the element at the 0th position will be compared with the element at 4th position.
 If the 0th element is greater, it will be swapped with the element at 4th position. Otherwise, it remains the same.
This process will continue for the remaining elements.
 At the interval of 4, the sublists are {33, 12}, {31, 17}, {40, 25}, {8, 42}.

58
 Now, we have to compare the values in every sub-list.
 After comparing, we need to swap them if required in the original array.
 After comparing and swapping, the updated array will look as follows –

 In the second loop, elements are lying at the interval of 2 (n/4 = 2), where n = 8.
 Now, we are taking the interval of 2 to sort the rest of the array.
 With an interval of 2, two sublists will be generated - {12, 25, 33, 40}, and {17, 8, 31, 42}.

 Now, we again have to compare the values in every sub-list.

 After comparing, we have to swap them if required in the original array.
 After comparing and swapping, the updated array will look as follows -

59
 In the third loop, elements are lying at the interval of 1 (n/8 = 1), where n = 8.
 At last, we use the interval of value 1 to sort the rest of the array elements.
 In this step, shell sort uses insertion sort to sort the array elements.

Now, the array is sorted in ascending order.

60
Shell sort complexity

1. Time Complexity
 Best Case Complexity - It occurs when there is no sorting required, i.e., the array is already
sorted. The best-case time complexity of Shell sort is O(n*logn).
 Average Case Complexity - It occurs when the array elements are in jumbled order that is
not properly ascending and not properly descending. The average case time complexity of
Shell sort is O(n*logn).
 Worst Case Complexity - 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 Shell sort
is O(n2). Case Time Complexity

Best Case O(n*logn)

Average Case O(n*log(n)2)
Worst Case O(n2)

2. Space Complexity
Space Complexity O(1)
Stable NO

 The space complexity of Shell sort is O(1). 61

Radix Sort

62
Radix Sort
 Radix sort is one of the sorting algorithms used to sort a list of integer numbers in order.

 In radix sort algorithm, a list of integer numbers will be sorted based on the digits of individual numbers.

 Sorting is performed from least significant digit to the most significant digit.

 Radix sort algorithm requires the number of passes which are equal to the number of digits present in the largest
number among the list of numbers.

 For example, if the largest number is a 3 digit number, then that list is sorted with 3 passes.

 Radix sort is classified based on how it works internally:

1. least significant digit (LSD) radix sort:

Processing starts from the least significant digit and moves towards the most significant digit.

2. Most significant digit (MSD) radix sort:

Processing starts from the most significant digit and moves towards the least significant digit. 63
Radix sort algorithm is performed using the following steps...

Step 1 - Define 10 queues each representing a bucket for each digit from 0 to 9.
Step 2 - Consider the least significant digit of each number in the list which is to be sorted.
Step 3 - Insert each number into their respective queue based on the least significant digit.
Step 4 - Group all the numbers from queue 0 to 9 in the order they have inserted into their respective queues.
Step 5 - Repeat from step 3 based on the next least significant digit.
Step 6 - Repeat from step 2 until all the numbers are grouped based on the most significant digit.

Complexity of the Radix Sort Algorithm

To sort an unsorted list with 'n' number of elements, Radix sort algorithm needs the following complexities...

Worst Case : O(n)

Best Case : O(n)
Average Case : O(n)

64
Example

65
66
Binary Search
Tree Sort

67
Binary Tree
 A binary tree is a tree data structure in which, each node has at most two child nodes.
 The child nodes are called the left child and right child.
 A binary tree could have different types: rooted, full, complete, perfect, balanced, or degenerate.
 The illustration shows a complete binary tree, which has each level completely filled, but with a possible exception
for the last level:

Binary trees have two common representations:

 Array representation: fills the array in a top-down approach, from left to right in each level, and an empty slot
for any missing child

 Linked list representation represents node object by node data, left pointer, and right pointer

68
Types of Binary Tree
1. Full Binary Tree
 A full Binary tree is a special type of binary tree in which every parent node/internal node has either two or no
children.

2. Perfect Binary Tree

 A perfect binary tree is a type of binary tree in which every internal node has exactly two child nodes and all the
leaf nodes are at the same level.

69
3. Complete Binary Tree
 A complete binary tree is just like a full binary tree, but with two major differences
 Every level must be completely filled
 All the leaf elements must lean towards the left.
 The last leaf element might not have a right sibling i.e. a complete binary tree doesn't have to be a full binary
tree.

4. Degenerate or Pathological Tree

 A degenerate or pathological tree is the tree having a single child either left or right.

5. Skewed Binary Tree

 A skewed binary tree is a pathological/degenerate tree in which the tree is either dominated by
the left nodes or the right nodes.
 Thus, there are two types of skewed binary tree: left-skewed binary tree and right-skewed
binary tree.

70
6. Balanced Binary Tree
 It is a type of binary tree in which the difference between the height of the left and the right subtree for each node
is either 0 or 1.

Binary Tree Representation

 A node of a binary tree is represented by a structure containing a data part and two pointers to other structures of
the same type.
struct node
{
int data;
struct node *left;
struct node *right;
}

71
Binary Search Tree (Binary Sorted Tree) :
Binary Search Tree, Binary Sorted Tree or BST, is a binary tree satisfies the following condition:
 For each node, the left sub-tree contains only nodes with values less than that node’s value
 For each node, the right sub-tree contains only nodes with values greater than that node’s value
 Left and right sub-trees are also BSTs
 The illustration shows a binary search tree of size 9 and depth 3

 Tree sort is an online sorting algorithm that builds a binary search tree from the elements input to be sorted, and
then traverses the tree, in-order, so that the elements come out in sorted order.
Steps to Process :
 Takes the elements as input in an array
 Creates a binary search tree by inserting data items from the array into the tree
 Performs in-order traversal on the tree to get the elements in sorted order
72
Algorithm for Binary Tree Sort :

73
Efficiency of Binary Tree Sort :
 The calculations of the worst-case assume an unbalanced BST.

 To maintain the average case, a balanced BST is needed.

 To build a balanced binary search tree, we need a different data structure to maintain the balancing, and we call it
a self-balancing (or height balancing) binary search tree.

 Most known implementations of the self-balancing BST are AVL Tree, B-Tree, Red-Black Tree, and Splay Tree.
 Time Complexity : Here , n is the number of nodes in the tree.
Best Case Average Case Worst Case
Operation
Complexity Complexity Complexity

Search O(log n) O(log n) O(n)

Insertion O(log n) O(log n) O(n)

Deletion O(log n) O(log n) O(n)

 Space Complexity : The space complexity for all the operations is O(n).

74
Heap Sort

75
Heap Sort
 Heap sort is one of the sorting algorithms used to arrange a list of elements in order.

 Heapsort algorithm uses one of the tree concepts called Heap Tree.

 In this sorting algorithm, we use Max Heap to arrange list of elements in Ascending order and Min Heap to arrange
list of elements in Descending order.
How Heap Sort works?
The Heap sort algorithm to arrange a list of elements in ascending order is performed using following steps...

Step 1 - Build a Binary tree from the input data.

Step 2 - Transform the Binary Tree into Max Heap.
Step 3 - At this point, the largest item is stored at the root of the heap.
Step 4 - Replace it with the last item of the heap followed by reducing the size of heap by 1.
Step 5 - Put the deleted element into the Sorted list.
Step 6 - Finally, heapify the root of the tree.
Step 7 - Repeat the same until Max Heap becomes empty.
Step 8 - Display the sorted list.
76
How to build the heap?

 Since a Binary Heap is a Complete Binary Tree, it can be easily represented as an array and the array-based
representation is space-efficient.
 If the parent node is stored at index i, the left child can be calculated by 2*i+1 and the right child by 2*i+2
(assuming the indexing starts at 0).
 The process of reshaping a binary tree into a Heap data structure is known as ‘heapify’.
 A binary tree is a tree data structure that has two child nodes at max.
 If a node’s children nodes are ‘heapified’, then only ‘heapify’ process can be applied over that node.
 A heap should always be a complete binary tree.
 Starting from a complete binary tree, we can modify it to become a Max-Heap by running a function called
‘heapify’ on all the non-leaf elements of the heap. i.e., ‘heapify’ uses recursion.
 Heapify procedure can be applied to a node only if its children nodes are heapified.
 So, the heapification must be performed in the bottom-up order.

77
Example :

78
79
Complexity of the Heap Sort Algorithm
Time Complexity: O(n logn),
Time complexity of heapify is O(Logn).
Time complexity of createAndBuildHeap() is O(n) and
Hence the overall time complexity of Heap Sort is O(nLogn).
Note: Heap sort is an in-place algorithm. Its typical implementation is not stable but can be made stable.

Advantages of heapsort –

 Efficiency – The time required to perform Heap sort increases logarithmically while other algorithms may grow
exponentially slower as the number of items to sort increases. This sorting algorithm is very efficient.
 Memory Usage – Memory usage is minimal because apart from what is necessary to hold the initial list of items
to be sorted, it needs no additional memory space to work
 Simplicity – It is simpler to understand than other equally efficient sorting algorithms because it does not use
advanced computer science concepts such as recursion

Applications of HeapSort

 Sort a nearly sorted (or K sorted) array

 k largest(or smallest) elements in an array
 Heap sort algorithm has limited uses because Quicksort and Mergesort are better in practice.
 Nevertheless, the Heap data structure itself is enormously used.
80