Sorting Algorithms

Sorting is the process of arranging the elements of an array so that they can be placed either
in ascending or descending order.

1. Bubble Sort
Bubble sort is a sorting algorithm that compares two adjacent elements and swaps them until
they are in the intended order.
Working of Bubble Sort
Suppose we are trying to sort the elements in ascending order.
1. First Iteration (Compare and Swap)
2. Starting from the first index, compare the first and the second elements.
3. If the first element is greater than the second element, they are swapped.
Now, compare the second and the third elements. Swap them if they are not in order.

To understand the working of bubble sort algorithm, let's take an unsorted array. We are taking
a short and accurate array, as we know the complexity of bubble sort is O(n2).

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.

Now, compare 32 and 35.

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 -
Second Pass
The same process will be followed for second iteration.

Now, move to the third iteration.

Third Pass
The same process will be followed for third iteration.

Now, move to the fourth iteration.

Fourth pass
Similarly, after the fourth iteration, the array will be -

Python Code:
 Advantages Disadvantages
The primary advantage of the bubble The main disadvantage of the bubble
sort is that it is popular and easy tosort is the fact that it does not deal well
implement. with a list containing a huge number of
items.
In the bubble sort, elements are The bubble sort requires n-squared
swapped in place without using processing steps for every n number of
additional temporary storage. elements to be sorted.
The space requirement is at a minimum The bubble sort is mostly suitable for
academic teaching but not for real-life
applications.

2. Selection Sort
What Is a Selection Sort Algorithm?

• Selection sort is an effective and efficient sort algorithm based on comparison operations.
• It adds one element in each iteration.
• You need to select the smallest element in the array and move it to the beginning of the
array by swapping with the front element.
• You can also accomplish this by selecting the most potent element and positioning it at the
back end.
• In each iteration, selection sort selects an element and places it in the appropriate position.
How Does the Selection Sort Algorithm Work?
Selection sort works by taking the smallest element in an unsorted array and bringing it to the
front. You’ll go through each item (from left to right) until you find the smallest one. The first
item in the array is now sorted, while the rest of the array is unsorted.

• The entire list is scanned sequentially for the first position in the sorted list. You search the
whole list and find that 10 is the lowest value in the first position, where 15 is stored.

• As a result, you replaced 15 with 10. After one iteration, the number 10, which happens to
be the lowest value on the list, appears at the top of the sorted list.

• You discovered that 15 is the second lowest value on the list and should be placed second.
You must switch these values.

The same procedure is followed for the remaining array items.

The following is a visual representation of the entire sorting process.
Algorithm of the Selection Sort Algorithm
The selection sort algorithm is as follows:
Step 1: Set Min to location 0 in Step 1.
Step 2: Look for the smallest element on the list.
Step 3: Replace the value at location Min with a different value.
Step 4: Increase Min to point to the next element
Step 5: Continue until the list is sorted.

Selection sort is generally used when -

▪ A small array is to be sorted
▪ Swapping cost doesn't matter
▪ It is compulsory to check all elements

Python Code:

Advantages Disadvantages
The main advantage of the selection sort The primary disadvantage of the selection
is that it performs well on a small list. sort is its poor efficiency when dealing
with a huge list of items.
Because it is an in-place sorting The selection sort requires n-squared
algorithm, no additional temporary number of steps for sorting n elements.
storage is required beyond what is
needed to hold the original list.
Its performance is easily influenced by the Selection sort is less efficient as
initial ordering of the items before the compared to quick sort.
sorting process.
3. Insertion Sort
Insertion sort is a very simple method to sort numbers in an ascending or descending order.
This method follows the incremental method. It can be compared with the technique how cards
are sorted at the time of playing a game.

This is an in-place comparison-based sorting algorithm. Here, a sub-list is maintained which is

always sorted. For example, the lower part of an array is maintained to be sorted. An element
which is to be 'inserted' in this sorted sub-list, has to find its appropriate place and then it has
to be inserted there. Hence the name, insertion sort.

How Insertion Sort Works

1. We will start by assuming the very first element of the array is already sorted. Inside the key,
we will store the second element.
2. Next, we will compare our first element with the key, such that if the key is found to be
smaller than the first element, we will interchange their indexes or place the key at the first
index. After doing this, we will notice that the first two elements are sorted.
3. Now, we will move on to the third element and compare it with the left-hand side elements.
If it is the smallest element, then we will place the third element at the first index.

Else if it is greater than the first element and smaller than the second element, then we will
interchange its position with the third element and place it after the first element. After doing
this, we will have our first three elements in a sorted manner.

Consider an example: arr[]: {12, 11, 13, 5, 6}

12 11 13 5 6

First Pass:
• Initially, the first two elements of the array are compared in insertion sort.

12 11 13 5 6

• Here, 12 is greater than 11 hence they are not in the ascending order and 12 is not at its
correct position. Thus, swap 11 and 12.
• So, for now 11 is stored in a sorted sub-array.

11 12 13 5 6

Second Pass:

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

11 12 13 5 6

• Here, 13 is greater than 12, thus both elements seems to be in ascending order, and
hence, no swapping will occur. 12 also stored in a sorted sub-array along with 11.

Third Pass:
• Now, two elements are present in the sorted sub-array which are 11 and 12
• Moving forward to the next two elements which are 13 and 5
 11 12 13 5 6

• Both 5 and 13 are not present at their correct place so swap them

11 12 5 13 6

• After swapping, elements 12 and 5 are not sorted, thus swap again

11 5 12 13 6

• Here, again 11 and 5 are not sorted, hence swap again

5 11 12 13 6

• Here, 5 is at its correct position

Fourth Pass:
• Now, the elements which are present in the sorted sub-array are 5, 11 and 12
• Moving to the next two elements 13 and 6

5 11 12 13 6

• Clearly, they are not sorted, thus perform swap between both

5 11 12 6 13

• Now, 6 is smaller than 12, hence, swap again

5 11 6 12 13

• Here, also swapping makes 11 and 6 unsorted hence, swap again

5 6 11 12 13

Finally, the array is completely sorted.

Python Code:
 Advantages Disadvantages

The main advantage of the insertion sort The disadvantage of the insertion sort is
is its simplicity. that it does not perform as well as other,
better sorting algorithms
It also exhibits a good performance when With n-squared steps required for every n
dealing with a small list. element to be sorted, the insertion sort
does not deal well with a huge list.
The insertion sort is an in-place sorting The insertion sort is particularly useful
algorithm so the space requirement is only when sorting a list of few items.
minimal.

4. Counting Sort
Counting sort is a sorting technique that is based on the keys between specific ranges. Memory
is allocated according to range. This sorting technique doesn't perform sorting by comparing
elements. It performs sorting by counting objects having distinct key values like hashing. And
frequency of every element is updated in relevant memory location. After that, array becomes
sorted after getting out from memory. Counting sort is effective when range is not greater than
number of objects to be sorted. It can be used to sort the negative input values.

How does Counting Sort Algorithm work?

Step1 :
• Find out the maximum element from the given array.

Step 2:
• Initialize a countArray[] of length max+1 with all elements as 0. This array will be used
for storing the occurrences of the elements of the input array.

Step 3:
• In the countArray[], store the count of each unique element of the input array at their
respective indices.
• For Example: The count of element 2 in the input array is 2. So, store 2 at index 2 in
the countArray[]. Similarly, the count of element 5 in the input array is 1, hence store 1 at
index 5 in the countArray[].

Step 4:
• Store the cumulative sum or prefix sum of the elements of the countArray[] by
doing countArray[i] = countArray[i – 1] + countArray[i]. This will help in placing the
elements of the input array at the correct index in the output array.

Step 5:
• Iterate from end of the input array and because traversing input array from end
preserves the order of equal elements, which eventually makes this sorting
algorithm stable.

Step 6: For i = 6,
Update outputArray[ countArray[ inputArray[6] ] – 1] = inputArray[6]
Also, update countArray[ inputArray[6] ] = countArray[ inputArray[6] ]- –
Counting Sort Algorithm:
• Declare an auxiliary array countArray[] of size max(inputArray[])+1 and initialize it
with 0.
• Traverse array inputArray[] and map each element of inputArray[] as an index
of countArray[] array, i.e., execute countArray[inputArray[i]]++ for 0 <= i < N.
• Calculate the prefix sum at every index of array inputArray[].
• Create an array outputArray[] of size N.
• Traverse array inputArray[] from end and update outputArray[ countArray[
inputArray[i] ] – 1] = inputArray[i]. Also, update countArray[ inputArray[i] ] =
countArray[ inputArray[i] ]- – .

Applications of Counting Sort Algorithm

1. If the range of input data is not much bigger than the number of objects to be sorted, counting
sort is efficient. Consider the following scenario: the data is 10, 5, 10K, 5K, and the input
sequence is 1 to 10K.

2. It isn't a sorting system based on comparisons. It has an O(n) running time complexity, with
space proportional to the data range.

3. It's frequently used as a subroutine in other sorting algorithms, such as radix sort.

4. Counting sort counts the occurrences of the data object in O using partial hashing (1).

5. The counting sort can also be used with negative inputs.

Python Code:
5. Radix Sort
The key idea behind Radix Sort is to exploit the concept of place value. It assumes that sorting
numbers digit by digit will eventually result in a fully sorted list. Radix Sort can be performed
using different variations, such as Least Significant Digit (LSD) Radix Sort or Most Significant
Digit (MSD) Radix Sort. Radix Sort is a linear sorting algorithm. It is not an in-place sorting
algorithm because it requires extra space. Radix Sort is a stable sort because it maintains the
relative order of elements with equal values. Radix sort algorithm may be slower than other
sorting algorithms such as merge sort and Quicksort if the operations are inefficient. These
operations include sub-inset lists and delete functions, and the process of isolating the desired
digits. Because it is based on digits or letters, radix sort is less flexible than other sorts. If
the type of data changes, the Radix sort must be rewritten.

How does Radix Sort Algorithm work?

Step 1: Find the largest element in the array, which is 802. It has three digits, so we will iterate
three times, once for each significant place.
Step 2: Sort the elements based on the unit place digits (X=0). We use a stable sorting
technique, such as counting sort, to sort the digits at each significant place.
Step 3: Sort the elements based on the tens place digits.
Step 4: Sort the elements based on the hundreds place digits.
Step 5: The array is now sorted in ascending order.

Input Array: 132, 7, 898, 49, 783, 543, 63

898 is highest number and it is 3 digit number. Now append 0’s to remaining numbers in array
to make them 3 digit number.
After appending zeros
132, 007, 898, 049, 783, 543, 063

Python Code:
Advantages Radix Sort Algorithm

• Fast when the keys are short, i.e. when the array element range is small.
• Used in suffix arrays construction algorithms such as Manber's and the DC3 algorithm.
• Radix Sort is a stable sort because it maintains the relative order of elements with equal
values.
Disadvantages of Radix Sort Algorithm

• The Radix Sort algorithm is less flexible than other sorts because it is based on digits or
letters. As a result, for each different type of data, it must be rewritten.
• Radix sort has a higher constant than other sorting algorithms.
• It takes up more space than Quicksort, which is used for in-place sorting.
• Radix sort may be slower than other sorting algorithms such as merge sort and Quicksort if
the operations are inefficient. These operations include sub-inset lists and delete functions,
as well as the process of isolating the desired digits.

6. Bucket Sort
Bucket sort is a sorting technique that involves dividing elements into various groups, or
buckets. These buckets are formed by uniformly distributing the elements. Once the elements
are divided into buckets, they can be sorted using any other sorting algorithm. Finally, the sorted
elements are gathered together in an ordered fashion.

How does Bucket Sort work?

To apply bucket sort on the input array [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23,
0.68], we follow these steps:
Step 1: Create an array of size 10, where each slot represents a bucket.
Step 2: Insert elements into the buckets from the input array based on their range.
Inserting elements into the buckets:
• Take each element from the input array.
• Multiply the element by the size of the bucket array (10 in this case). For example, for
element 0.23, we get 0.23 * 10 = 2.3.
• Calculate the floor value of 2.3, which is 2.
• Insert the element into the bucket corresponding to the calculated index.
• Repeat these steps for all elements in the input array.

Step 3: Sort the elements within each bucket by applying insertion sort.

Step 4: Gather the elements from each bucket and put them back into the original array.
Gathering elements from each bucket:
• Iterate through each bucket in order.
• Insert each individual element from the bucket into the original array.
• Once an element is copied, it is removed from the bucket.
• Repeat this process for all buckets until all elements have been gathered.
Python Code:

Bucket Sort Applications

Bucket sort is used when:
▪ Input is uniformly distributed over a range.
▪ There are floating point values
 Time Complexity comparison of various algorithms

Sorting Time Complexity - Time Complexity - Time Complexity -

Algorithm Best Worst Average

Bubble Sort n n2 n2

Selection Sort n2 n2 n2
Insertion Sort n n2 n2
Merge Sort nlog n nlog n nlog n

Quicksort nlog n n2 nlog n

Counting Sort n+k n+k n+k

Radix Sort nk nk nk
Bucket Sort n+k n2 n

Updated Code of Merge Sort: