UNIT-

5
Sorting

Sorting is a process of ordering or placing a list of elements from a collection in

some kind of order. It is nothing but storage of data in sorted order. Sorting can be
done in ascending and descending order. It arranges the data in a sequence which
makes searching easier.

Insertion Sort

Insertion Sort is a sorting algorithm where the array is sorted by taking one element
at a time. The principle behind insertion sort is to take one element, iterate through
the sorted array & find its correct position in the sorted [Link] 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 'insert'ed in this sorted sub-list, has to find its appropriate
place and then it has to be inserted there. The array is searched sequentially and
unsorted items are moved and inserted into the sorted sub-list (in the same array).

How Insertion Sort Works?

Consider an unsorted array for our example.

Insertion sort compares the first two elements.

It finds that both 14 and 33 are already in ascending order. For now, 14 is in
sorted sub-list.

Insertion sort moves ahead and compares 33 with 27.

And finds that 33 is not in the correct position.

It swaps 33 with 27. It also checks with all the elements of sorted sub-list. Here
we see that the sorted sub-list has only one element 14, and 27 is greater than 14.
Hence, the sorted sub-list remains sorted after swapping.

By now we have 14 and 27 in the sorted sub-list. Next, it compares 33 with 10.

These values are not in a sorted order.

So we swap them.

However, swapping makes 27 and 10 unsorted.

Hence, swap them too.

Again we find 14 and 10 in an unsorted order.

Swap them again. By the end of the third iteration, a sorted sub-list of 4 items is
obtained.

Algorithm for Insertion Sort

● Step 1​ − If the element is the first one, it is already sorted.

● Step 2​ – Move to next element
● Step 3​ − Compare the current element with all elements in the sorted array
● Step 4​ – If the element in the sorted array is smaller than the current
element, iterate to the next element. Otherwise, shift all the greater element
in the array by one position towards the right
● Step 5​ − Insert the value at the correct position
● Step 6​ − Repeat until the complete list is sorted

Selection Sort

Selection sort is a simple sorting algorithm. This sorting algorithm is an in-place

comparison-based algorithm in which the list is divided into two parts, the sorted
part at the left end and the unsorted part at the right end. Initially, the sorted part is
empty and the unsorted part is the entire list. Selection sorting algorithm, iterates
through the array and selects the smallest number in the array and swaps it with
the first element if it is smaller than the first element. Next, it goes on to the
second element and so on until all elements are sorted.
This algorithm is not suitable for large data sets as its average and worst case
complexities are of Ο(n^2), where n is the number of items.

How Selection Sort Works?

Consider the following array as an example.
For the first position in the sorted list, the whole list is scanned sequentially and
finds that 10 is the lowest value. So replace 14 with 10. After one iteration 10, the
minimum value in the list, appears in the first position of the sorted list.

For the second position, where 33 is residing, start scanning the rest of the list in a
linear manner and find that 14 is the second lowest value in the list and it should
appear at the second place. Swap these values.
After two iterations, two least values are positioned at the beginning in a sorted
manner.

The same process is applied to the rest of the items in the array.
Following is a pictorial depiction of the entire sorting process −
Algorithm for Selection Sort:

Step 1 − Set min to the first location

Step 2 − Search the minimum element in the array

Step 3 – Swap the first location with the minimum value in the array

Step 4 – Assign the second element as min.

Step 5 − Repeat the process until we get a sorted array.

Bubble Sort

Bubble sort is one of the easiest sorting techniques in programming and it is very
simple to implement. ​This sorting algorithm is a comparison-based algorithm in
which each pair of adjacent elements is compared and the elements are swapped if
they are not in order. ​It compares the current element with the next element and
swaps it, if it is greater or less, depending on the condition. Each time an element is
compared with all other elements till it’s final place is found is called a pass.

If the array has total ​n elements, then this process is to be repeated for ​n-1 times. It
is known as ​bubble sort​, because with every complete iteration the largest element
in the given array, bubbles up towards the last place or the highest index, just like a
water bubble rises up to the water surface.
Sorting takes place by stepping through all the elements one-by-one and comparing
it with the adjacent element and swapping them if required.
This algorithm is not suitable for large data sets as its average and worst case
complexity are ​O(n^2) where n is the number of items. ​The best complexity of a
bubble sort can be O(n). O(n) is only possible if the array is sorted.

How Bubble Sort Works?

Consider an unsorted array for our example.
Bubble sort starts by comparing the first two elements to check which one is
greater.

In this case, value 33 is greater than 14, so it is already in sorted locations. Next,
compare 33 with 27.

27 is smaller than 33 and these two values must be swapped.

Next compare 33 and 35, both are in already sorted positions.

Compare the next two values, 35 and 10. 10 is smaller than 35, hence they are not
sorted.

Swap these values. After one iteration, the array will be−

After the second iteration, the array will be −

After each iteration, at least one value moves at the end.

And when there's no swap required, the array is completely sorted.

Algorithm for Bubble sort(for sorting a given array in ascending order)​:

Step 1: Starting with the first element(index = 0), compare the current element with
the next element of the array.

Step 2: If the current element is greater than the next element of the array, swap
them.

Step 3: If the current element is less than the next element, move to the next
element. Repeat Step 1.

Quick sort

Quick sort is a highly efficient sorting algorithm and is based on partitioning an

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.

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(nLogn) and O(n2), respectively.

The pivot value divides the list into two parts. And recursively, find the pivot for
each sub-lists until all lists contains only one element.
Consider the following array: 50, 23, 9, 18, 61, 32

Step 1: Decide any value to be the pivot from the list (generally the last value).
Suppose for two values “Low” and “High” corresponding to the first index, and
last index. Low is 0 and high is 5. Values at low and high are 50 and 32 and Value
of pivot is 32.

Hence, call for partitioning, rearranging the array in such a way that pivot (32)
comes to its actual position. And to the left of the pivot, the array has all the
elements less than it, and to the right greater than it.

In the partition function, start from the first element and compare it with the pivot.
Since 50 is greater than 32, no changes and move on to the next element 23.

Compare again with the pivot. Since 23 is less than 32, swap 50 and 23. The array
becomes 23, 50, 9, 18, 61, 32.
Move on to the next element 9 which is again less than pivot (32) thus swapping it
with 50 makes the array as

23, 9, 50, 18, 61, 32.

Similarly, for next element 18 which is less than 32, the array becomes

23, 9, 18, 50, 61, 32 Now 61 is greater than pivot (32), hence no changes.

Lastly, we swap our pivot with 50 so that it comes to the correct position.

Thus the pivot (32) comes at its actual position and all elements to its left are
lesser, and all elements to the right are greater than itself.

Step 2: Hence the array after the first step becomes

23, 9, 18, 32, 61, 50

Step 3: Now the list is divided into two parts:

1. Sublist before pivot

2. Sublist after pivot

Sub-list before and after Pivot

Step 4: Repeat the steps for these sublists again.

The final array thus becomes 9, 18, 23, 32, 50, 61.
Algorithm for Quick Sort
Step 1 − Choose the highest index value has pivot

Step 2 − Take two variables to point left and right of the list excluding pivot

Step 3 − left points to the low index

Step 4 − right points to the high

Step 5 − while value at left is less than pivot move right

Step 6 − while value at right is greater than pivot move left

Step 7 − if both step 5 and step 6 does not match swap left and right

Step 8 − if left ≥ right, the point where they met is new pivot

Merge sort
Merge sort is a sorting technique based on divide and conquer technique. Merge
sort first divides the array into equal halves and then combines them in a sorted
manner.

How Merge Sort Works?

Consider an unsorted array as the following −

Merge sort first divides the whole array iteratively into equal halves unless the
atomic values are achieved. This array of 8 items is divided into two arrays of size
4.
Now divide these two arrays into halves.

Further divide these arrays and atomic values are achieved which can no more be
divided.

Now combine them in exactly the same manner as they were broken down.
First compare the element for each list and then combine them into another list in
a sorted manner. 14 and 33 are in sorted positions. Compare 27 and 10 and in the
target list of 2 values put 10 first, followed by 27. Change the order of 19 and 35
whereas 42 and 44 are placed sequentially.

In the next iteration of the combining phase, 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 is sorted −

Algorithm for Merge Sort

Merge sort keeps on dividing the list into equal halves until it can no more be
divided. By definition, if it is only one element in the list, it is sorted. Then, merge
sort combines the smaller sorted lists keeping the new list sorted too.
Step 1 − If there 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.

Shell sort
Shell sort is a highly efficient sorting algorithm and is based on insertion sort
algorithm. This algorithm avoids large shifts as in case of insertion sort, if the
smaller value is to the far right and has to be moved to the far left. This algorithm
uses insertion sort on a widely spread elements, first to sort them and then sorts
the less widely spaced elements. This spacing is termed as [Link] interval is
calculated based on Knuth's formula as −
h=h*3+1 where − h is interval with initial value 1
This algorithm is quite efficient for medium-sized data sets as its average and
worst-case complexity of this algorithm depends on the gap sequence the best
known is Ο(n), where n is the number of items. And the worst case space
complexity is O(n).

How Shell Sort Works?

Consider an unsorted array and take the interval of 4−

Make a virtual sub-list of all values located at the interval of 4 positions. Here
these values are {35, 14}, {33, 19}, {42, 27} and {10, 44}
Compare values in each sub-list and swap them (if necessary) in the original array.
After this step, the new array will be −

Then, take interval of 1 and this gap generates two sub-lists - {14, 27, 35, 42},
{19, 10, 33, 44}

Compare and swap the values, if required, in the original array. After this step, the
array will be −

Finally, sort the rest of the array using interval of value 1.

Following is the step-by-step depiction −

Algorithm for Shell Sort

Step 1 − Initialize the value of h

Step 2 − Divide the list into smaller sub-list of equal interval h

Step 3 − Sort these sub-lists using insertion sort

Step 3 − Repeat until complete list is sorted

Radix Sort

Radix sort is a sorting technique that sorts the elements by first grouping the
individual digits of same place value. Then, sort the elements according to their
increasing/decreasing order. 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.

Consider an array of 8 elements. First, sort elements based on the value of the unit
place. Then, sort elements based on the value of the tenth place. This process goes
on until the last significant place.

Let the initial array be [121, 432, 564, 23, 1, 45, 788]. It is sorted according to
radix sort as shown in the figure below.

How Radix Sort Works?

1. Find the largest element in the array, i.e. max. Let X be the number of digits
in max. X is calculated because we have to go through all the significant
places of all elements.
In this array [121, 432, 564, 23, 1, 45, 788], we have the largest number 788.
It has 3 digits. Therefore, the loop should go up to hundreds place (3 times).
 2. Now, go through each significant place one by one.
Sort the elements based on the unit place digits (X=0).

3. Now, sort the elements based on digits at tens place.

4. Finally, sort the elements based on the digits at hundreds place.

Algorithm for Radix Sort

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 element to their respective queue based on the least significant
digit.

Step 4 - Group all members from Queue 0 to Queue 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.