Unit -2

Sorting

What is sorting?
Sorting refers to the operation or technique of arranging and rearranging sets of data in some
specific order. Sorting data allows a user to find information faster and easier. A dictionary is
a simple example of sorting.

What is Sorting Algorithm?

Sorting algorithms are a set of instructions that take an array or list as an input and arrange
the items into a particular order.

Sorts are most commonly in numerical or a form of alphabetical (or lexicographical) order,
and can be in ascending (A-Z, 0-9) or descending (Z-A, 9-0) order.

Figure: Sorting

Example: Selection Sort, Insertion Sort, Bubble Sort, Merge Sort, Quick Sort, etc.

Page 1 of 22
Different types of sorting algorithms

Bubble Sort Algorithm

Bubble sort is a simple sorting algorithm. This sorting algorithm is comparison-based

algorithm in which each pair of adjacent elements is compared and the elements are swapped
if they are not in order. This algorithm is not suitable for large data sets as its average and
worst case complexity are of Ο(n2) where n is the number of items.

Bubble Sort Algorithm:

Following are the steps involved in bubble sort (for sorting a given array in ascending order):

1. Starting with the first element (index = 0), compare the current element with the
next element of the array.
2. If the current element is greater than the next element of the array, swap them.
3. If the current element is less than the next element, move to the next element.
Repeat Step 1.

Example:

Working of Algorithm:

Let the elements of array are –

First Pass

Sorting will start from the initial two elements. Let compare them to check which is greater.

Here, 32 is greater than 13 (32 > 13), so it is already sorted. Now, compare 32 with 26.

Here, 26 is smaller than 36. So, swapping is required. After swapping new array will look
like –

Now, compare 32 and 35.

Page 2 of 22
Here, 35 is greater than 32. So, there is no swapping required as they are already sorted.

Now, the comparison will be in between 35 and 10.

Here, 10 is smaller than 35 that are not sorted. So, swapping is required. Now, we reach at the
end of the array. After first pass, the array will be –

Now, move to the second iteration.

Second Pass

The same process will be followed for second iteration.

Here, 10 is smaller than 32. So, swapping is required. After swapping, the array will be –

Now, move to the third iteration.

Third Pass

The same process will be followed for third iteration.

Page 3 of 22
Here, 10 is smaller than 26. So, swapping is required. After swapping, the array will be –

Now, move to the fourth iteration.

Fourth pass

Similarly, after the fourth iteration, the array will be –

Hence, there is no swapping required, so the array is completely sorted.

Bubble sort complexity

Now, let's see the time complexity of bubble sort in the best case, average case, and worst
case.

Time Complexity

 Best Case: O(n)

 Average Case: O(n2)
 Worst Case: O(n2)

Best Case Complexity - 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 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 bubble
sort is O(n2).

Page 4 of 22
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 bubble sort is O(n2).

Space Complexity

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

Properties of Bubble Sort Algorithm

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.

Advantages of Bubble Sort Algorithm

Advantages:

 The primary advantage of the bubble sort is that it is popular and easy to implement.
 In the bubble sort, elements are swapped in place without using additional temporary
storage.
 The space requirement is at a minimum

Disadvantages of Bubble Sort Algorithm

Disadvantages:

 It does not work well when we have large unsorted lists, and it necessitates more
resources that end up taking so much of time.
 It is only meant for academic purposes, not for practical implementations.
 It involves the n2 order of steps to sort an algorithm.

Selection Sort Algorithm

Selection sort is a sorting algorithm that selects the smallest element from an unsorted list in
each iteration and places that element at the beginning of the unsorted list.

This algorithm is not suitable for large data sets as its average and worst case complexities
are of Ο(n2), where n is the number of items.

Page 5 of 22
Algorithm of Selection Sort:

Step 1 − Set MIN to location 0

Step 2 − Search the minimum element in the list

Step 3 − Swap with value at location MIN

Step 4 − Increment MIN to point to next element

Step 5 − Repeat until list is sorted

Working of Selection Sort

Now, let's see the working of the Selection sort Algorithm.

To understand the working of the Selection sort algorithm, let's take an unsorted array. It will
be easier to understand the Selection sort via an example.

Let the elements of array are –

Now, for the first position in the sorted array, the entire array is to be scanned sequentially.

At present, 12 is stored at the first position, after searching the entire array, it is found that 8
is the smallest value.

So, swap 12 with 8. After the first iteration, 8 will appear at the first position in the sorted
array.

For the second position, where 29 is stored presently, we again sequentially scan the rest of
the items of unsorted array. After scanning, we find that 12 is the second lowest element in
the array that should be appeared at second position.

Page 6 of 22
Now, swap 29 with 12. After the second iteration, 12 will appear at the second position in the
sorted array. So, after two iterations, the two smallest values are placed at the beginning in a
sorted way.

The same process is applied to the rest of the array elements. Now, we are showing a pictorial
representation of the entire sorting process.

Now, the array is completely sorted.

Time Complexity

 Worst Case Complexity: O(n2)

If we want to sort in ascending order and the array is in descending order then, the
worst case occurs.

 Best Case Complexity: O(n2)

It occurs when the array is already sorted

 Average Case Complexity: O(n2)

Page 7 of 22
 It occurs when the elements of the array are in jumbled order (neither ascending nor
descending).

Space Complexity

Space complexity is O(1) because an extra variable temp is used.

Advantages of Selection Sort Algorithm

 Simple and easy to understand.

 Works well with small datasets.

Disadvantages of Selection Sort Algorithm

 Selection sort has a time complexity of O(n^2) in the worst and average case.
 Does not work well on large datasets.
 Does not preserve the relative order of items with equal keys which means it is not
stable.

Selection is generally used when-

 A small array is to be sorted

 Swapping cost doesn't matter
 It is compulsory to check all elements

Insertion Sort Algorithm

Insertion sort is a sorting algorithm that places an unsorted element at its suitable place in
each iteration. Insertion sort works similarly as we sort cards in our hand in a card game.

We assume that the first card is already sorted then, we select an unsorted card. If the
unsorted card is greater than the card in hand, it is placed on the right otherwise, to the left. In
the same way, other unsorted cards are taken and put in their right place.

A similar approach is used by insertion sort.

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.

Algorithm of Insertion Sort:

tep 1 − If it is the first element, it is already sorted. return 1;

Step 2 − Pick next element

Step 3 − Compare with all elements in the sorted sub-list

Page 8 of 22
Step 4 − Shift all the elements in the sorted sub-list that is greater than the

value to be sorted

Step 5 − Insert the value

Step 6 − Repeat until list is sorted

Working of Insertion sort Algorithm

Now, let's see the working of the insertion sort Algorithm.

To understand the working of the insertion sort algorithm, let's take an unsorted array. It will
be easier to understand the insertion sort via an example.

Let the elements of array are –

Initially, the first two elements are compared in insertion sort.

Here, 31 is greater than 12. That means both elements are already in ascending order. So, for
now, 12 is stored in a sorted sub-array.

Now, move to the next two elements and compare them.

Here, 25 is smaller than 31. So, 31 is not at correct position. Now, swap 31 with 25. Along
with swapping, insertion sort will also check it with all elements in the sorted array.

For now, the sorted array has only one element, i.e. 12. So, 25 is greater than 12. Hence, the
sorted array remains sorted after swapping.

Page 9 of 22
Now, two elements in the sorted array are 12 and 25. Move forward to the next elements that
are 31 and 8.

Both 31 and 8 are not sorted. So, swap them.

After swapping, elements 25 and 8 are unsorted.

So, swap them.

Now, elements 12 and 8 are unsorted.

So, swap them too.

Now, the sorted array has three items that are 8, 12 and 25. Move to the next items that are 31
and 32.

Hence, they are already sorted. Now, the sorted array includes 8, 12, 25 and 31.

Move to the next elements that are 32 and 17.

Page 10 of 22
17 is smaller than 32. So, swap them.

Swapping makes 31 and 17 unsorted. So, swap them too.

Now, swapping makes 25 and 17 unsorted. So, perform swapping again.

Now, the array is completely sorted.

Time Complexity of Insertion Sort Algorithm

 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 insertion sort is O(n).
 Average Case: O(n2)
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 insertion 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 insertion sort is
O(n2).

Space Complexity of Insertion Sort Algorithm

The space complexity of insertion sort is O(1). It is because, in insertion sort, an extra
variable is required for swapping.

Characteristics of Insertion Sort Algorithm

Page 11 of 22
  This algorithm is one of the simplest algorithms with a simple implementation
 Basically, Insertion sort is efficient for small data values
 Insertion sort is adaptive in nature, i.e. it is appropriate for data sets that are already
partially sorted.

Advantages of Insertion Sort Algorithm

 It, like other quadratic sorting algorithms, is efficient for small data sets.
 It just necessitates a constant amount of O(1) extra memory space.
 It works well with data sets that have been sorted in a significant way.
 It does not affect the relative order of elements with the same key.

Disadvantages of Insertion Sort Algorithm

 Insertion sort is inefficient against more extensive data sets

 The insertion sort exhibits the worst-case time complexity of O(n2)
 It does not perform well than other, more advanced sorting algorithms
 Does not preserve the relative order of items with equal keys which means it is not
stable.

Merge Sort Algorithm

Merge Sort is one of the most popular sorting algorithms that is based on the principle of
Divide and Conquer Algorithm.

Here, a problem is divided into multiple sub-problems. Each sub-problem is solved

individually. Finally, sub-problems are combined to form the final solution.

Divide and Conquer Strategy

Using the Divide and Conquer technique, we divide a problem into subproblems. When the
solution to each subproblem is ready, we 'combine' the results from the subproblems to solve
the main problem.

Suppose we had to sort an array A. A subproblem would be to sort a sub-section of this array
starting at index p and ending at index r, denoted as A[p..r]

Divide

If q is the half-way point between p and r, then we can split the subarray A[p..r] into two
arrays A[p..q] and A[q+1, r].

Conquer

In the conquer step, we try to sort both the subarrays A[p..q] and A[q+1, r]. If we haven't yet
reached the base case, we again divide both these subarrays and try to sort them.

Combine

Page 12 of 22
When the conquer step reaches the base step and we get two sorted subarrays A[p..q] and
A[q+1, r] for array A[p..r], we combine the results by creating a sorted array A[p..r] from two
sorted subarrays A[p..q] and A[q+1, r].

In Short:

Figure: Divide and Conquer Technique

Algorithm of Merge Sort

Step 1 − if it is only one element in the list it is already sorted, return.

Step 2 − divide the list recursively into two halves until it can no more be divided.

Step 3 − merge the smaller lists into new list in sorted order.

Working of Merge Sort Algorithm

For Example: To understand merge sort, we take an unsorted array as the following –

We know that merge sort first divides the whole array iteratively into equal halves unless the
atomic values are achieved. We see here that an array of 8 items is divided into two arrays of
size 4.

Page 13 of 22
This does not change the sequence of appearance of items in the original. Now we divide
these two arrays into halves.

We further divide these arrays and we achieve atomic value which can no more be divided.

Now, we combine them in exactly the same manner as they were broken down.

We first compare the element for each list and then combine them into another list in a sorted
manner. We see that 14 and 33 are in sorted positions. We compare 27 and 10 and in the
target list of 2 values we put 10 first, followed by 27. We change the order of 19 and 35
whereas 42 and 44 are placed sequentially.

In the next iteration of the combining phase, we compare lists of two data values, and merge
them into a list of found data values placing all in a sorted order.

After the final merging, the list should look like this –

Applications of Merge Sort

 Sorting large datasets: Merge sort is particularly well-suited for sorting large datasets
due to its guaranteed worst-case time complexity of O(n log n).
 External sorting: Merge sort is commonly used in external sorting, where the data to
be sorted is too large to fit into memory.
 Custom sorting: Merge sort can be adapted to handle different input distributions,
such as partially sorted, nearly sorted, or completely unsorted data.
 Used for Counting inversions in a List.

Advantages of Merge Sort Algorithm

Page 14 of 22
  Stability: Merge sort is a stable sorting algorithm, which means it maintains the
relative order of equal elements in the input array.
 Guaranteed worst-case performance: Merge sort has a worst-case time complexity of
O(N logN), which means it performs well even on large datasets.
 Parallelizable: Merge sort is a naturally parallelizable algorithm, which means it can
be easily parallelized to take advantage of multiple processors or threads.

Disadvantages of Merge Sort

 Space complexity: Merge sort requires additional memory to store the merged sub-
arrays during the sorting process.
 Not in-place: Merge sort is not an in-place sorting algorithm, which means it requires
additional memory to store the sorted data. This can be a disadvantage in applications
where memory usage is a concern.
 Not always optimal for small datasets: For small datasets, Merge sort has a higher
time complexity than some other sorting algorithms, such as insertion sort. This can
result in slower performance for very small datasets.

Time Complexity of Merge Sort Algorithm

 Best Case Complexity - 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 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 merge 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
merge sort is O(n*logn).

Space Complexity of Merge Sort Algorithm

The space complexity of merge sort is O(n). It is because, in merge sort, an extra variable is
required for swapping.

Quick Sort Algorithm

Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of data
into smaller arrays. A large array is partitioned into two arrays one of which holds values
smaller than the specified value, say pivot, based on which the partition is made and another
array holds values greater than the pivot value.

Pivot element can be any element from the array, it can be the first element, the last element
or any random element.

Page 15 of 22
Quicksort partitions an array and then calls itself recursively twice to sort the two resulting
subarrays. This algorithm is quite efficient for large-sized data sets as its average and worst-
case complexity are O(n2), respectively.

Figure: Correct Position of Pivot

Algorithm of Quick Sort

Step 1: Select a pivot element

Page 16 of 22
Step 2: Partition the array around the pivot element.

Move all the elements < pivot to the left of the pivot and move all elements >= pivot to the
pivot’s right

Step 3: After Step 2, the pivot element is in its correct position

Step 4: Apply the quicksort recursively on the left partition

Step 5: Apply the quicksort recursively on the right partition

Step 6: Stop the recursion when the base case is reached. The base case is an array of size
zero or one

Working of Quick Sort Algorithm

Now, let's see the working of the Quicksort Algorithm.

To understand the working of quick sort, let's take an unsorted array. It will make the concept
more clear and understandable.

Let the elements of array are –

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.

Now, a[pivot] < a[right], so algorithm moves forward one position towards left, i.e. –

Page 17 of 22
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 –

Page 18 of 22
Now, a[left] = 9, a[right] = 24, and a[pivot] = 24. As a[pivot] > a[left], so algorithm moves
one position to right as –

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 –

Page 19 of 22
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.

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.

Page 20 of 22
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 –

Time Complexity

 Best Case Complexity - 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 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 quicksort is O(n*logn).
 Worst Case Complexity - 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).

Space Complexity

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

Advantages of Quick Sort Algorithm

 It is a divide-and-conquer algorithm that makes it easier to solve problems.

 It is efficient on large data sets.
 It has a low overhead, as it only requires a small amount of memory to function.

Disadvantages of Quick Sort Algorithm

 It has a worst-case time complexity of O(N2), which occurs when the pivot is chosen
poorly.
 It is not a good choice for small data sets.
 It is not a stable sort, meaning that if two elements have the same key, their relative
order will not be preserved in the sorted output in case of quick sort, because here we
are swapping elements according to the pivot’s position (without considering their
original positions).

Application of Quicksort

Page 21 of 22
  Commercial Computing is used in various government and private organizations for
the purpose of sorting various data like sorting files by name/date/price, sorting of
students by their roll no., sorting of account profile by given id, etc.
 The sorting algorithm is used for information searching and as Quicksort is the fastest
algorithm so it is widely used as a better way of searching.
 It is used everywhere where a stable sort is not needed.
 It is an in-place sort that does not require any extra storage memory.
 Numerical computations and in scientific research, for accuracy in calculations most
of the efficiently developed algorithm uses priority queue and quick sort is used for
sorting.
 Quicksort is a cache-friendly algorithm as it has a good locality of reference when
used for arrays.
 It is used in operational research and event-driven simulation.

Characteristics of quick sort

 In efficient implementations Quick Sort is not a stable sort, meaning that the relative
order of equal sort items is not preserved.
 Overall time complexity of Quick Sort is O(nLogn). In the worst case, it makes O(n2)
comparisons, though this behavior is rare.
 The space complexity of Quick Sort is O(nLogn). It is an in-place sort (i.e. it doesn’t
require any extra storage)

***

Page 22 of 22