Merge Sort

 Merge sort is the sorting technique that follows the divide and conquer approach.
 it uses the divide and conquer approach to sort the elements.
 It is one of the most popular and efficient sorting algorithm.
 It divides the given list into two equal halves, calls itself for the two halves and then
merges the two sorted halves.
 The sub-lists are divided again and again into halves until the list cannot be divided
further.
 Then we combine the pair of one element lists into two-element lists, sorting them in
the process.
 The sorted two-element pairs is merged into the four-element lists, and so on until
we get the sorted list.

Working of Merge sort Algorithm

Let the elements of array are –

According to the merge sort, first divide the given array into two equal halves. Merge sort
keeps dividing the list into equal parts until it cannot be further divided.

As there are eight elements in the given array, so it is divided into two arrays of size 4.

Now, again divide these two arrays into halves. As they are of size 4, so divide them into
new arrays of size 2.

Now, again divide these arrays to get the atomic value that cannot be further divided.
 Now, combine them in the same manner they were broken.

In combining, first compare the element of each array and then combine them into another
array in sorted order.

So, first compare 12 and 31, both are in sorted positions. Then compare 25 and 8, and in
the list of two values, put 8 first followed by 25. Then compare 32 and 17, sort them and put
17 first followed by 32. After that, compare 40 and 42, and place them sequentially.

In the next iteration of combining, now compare the arrays with two data values and merge
them into an array of found values in sorted order.

Now, there is a final merging of the arrays. After the final merging of above arrays, the array
will look like -

Now, the array is completely sorted.

Program: Write a program to implement merge sort in C language.

#include <stdio.h>

/* Function to merge the subarrays of a[] */

void merge(int a[], int beg, int mid, int end)
{
int i, j, k;
int n1 = mid - beg + 1;
int n2 = end - mid;

int LeftArray[8], RightArray[8]; //temporary arrays

/* copy data to temp arrays */

for (int i = 0; i < n1; i++)
 LeftArray[i] = a[beg + i];
for (int j = 0; j < n2; j++)
RightArray[j] = a[mid + 1 + j];

i = 0; /* initial index of first sub-array */

j = 0; /* initial index of second sub-array */
k = beg; /* initial index of merged sub-array */

while (i < n1 && j < n2)

{
if(LeftArray[i] <= RightArray[j])
{
a[k] = LeftArray[i];
i++;
}
else
{
a[k] = RightArray[j];
j++;
}
k++;
}
while (i<n1)
{
a[k] = LeftArray[i];
i++;
k++;
}

while (j<n2)
{
a[k] = RightArray[j];
j++;
k++;
}
}

void mergeSort(int a[], int beg, int end)

{
if (beg < end)
{
int mid = (beg + end) / 2;
mergeSort(a, beg, mid);
mergeSort(a, mid + 1, end);
merge(a, beg, mid, end);
}
}

/* Function to print the array */

void printArray(int a[], int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
printf("\n");
}

int main()
{
int a[] = { 12, 31, 25, 8, 32, 17, 40, 42 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArray(a, n);
mergeSort(a, 0, n - 1);
printf("After sorting array elements are - \n");
printArray(a, n);
return 0;
}
Quick Sort
 Quicksort is the widely used sorting algorithm that makes n log n comparisons in
average case for sorting an array of n elements.
 It is a faster and highly efficient sorting algorithm.
 This algorithm follows the divide and conquer approach.
 Divide and conquer is a technique of breaking down the algorithms into
subproblems, then solving the subproblems, and combining the results back together
to solve the original problem.

 Divide: In Divide, first pick a pivot element. After that, partition or rearrange the array
into two sub-arrays such that each element in the left sub-array is less than or equal
to the pivot element and each element in the right sub-array is larger than the pivot
element.

 Conquer: Recursively, sort two subarrays with Quicksort.

 Combine: Combine the already sorted array.

 Quicksort picks an element as pivot, and then it partitions the given array around the
picked pivot element.

 In quick sort, a large array is divided into two arrays in which one holds values that
are smaller than the specified value (Pivot), and another array holds the values that
are greater than the pivot.

 After that, left and right sub-arrays are also partitioned using the same approach.

 It will continue until the single element remains in the sub-array.

.
Choosing the pivot
Picking a good pivot is necessary for the fast implementation of quicksort. However, it is
typical to determine a good pivot. Some of the ways of choosing a pivot are as follows -

o Pivot can be random, i.e. select the random pivot from the given array.
o Pivot can either be the rightmost element or the leftmost element of the given
array.
o Select median as the pivot element.
o Working of Quick Sort Algorithm
o Now, let's see the working of the Quicksort Algorithm.
o To understand the working of quick sort, let's take an unsorted array. It will make the
concept more clear and understandable.
o Let the elements of array are -

o
o 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.
o Since, pivot is at left, so algorithm starts from right and move towards left.
o
o Now, a[pivot] < a[right], so algorithm moves forward one position towards left, i.e. -

o
o Now, a[left] = 24, a[right] = 19, and a[pivot] = 24.
o Because, a[pivot] > a[right], so, algorithm will swap a[pivot] with a[right], and pivot
moves to right, as -

o
o 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.
o As a[pivot] > a[left], so algorithm moves one position to right as -
o
o Now, a[left] = 9, a[right] = 24, and a[pivot] = 24. As a[pivot] > a[left], so algorithm
moves one position to right as -

o
o 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. -

o
o 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 -
o
o 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. -

o
o 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.

o
o 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.
o Element 24, which is the pivot element is placed at its exact position.
o 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.
 o
o 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 -

Program: Write a program to implement quicksort in C language.

#include <stdio.h>
/* function that consider last element as pivot,place the pivot at its exact position, and place
smaller elements to left of pivot and greater elements to right of pivot. */

int partition (int a[], int start, int end)

{
int pivot = a[end]; // pivot element
int i = (start - 1);

for (int j = start; j <= end - 1; j++)

{
// If current element is smaller than the pivot
if (a[j] < pivot)
{
i++; // increment index of smaller element
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
int t = a[i+1];
a[i+1] = a[end];
a[end] = t;
return (i + 1);
}

/* function to implement quick sort */

void quick(int a[], int start, int end) /* a[] = array to be sorted, start = Starting index, end =
Ending index */
{
 if (start < end)
{
int p = partition(a, start, end); //p is the partitioning index
quick(a, start, p - 1);
quick(a, p + 1, end);
}
}

/* function to print an array */

void printArr(int a[], int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
}
int main()
{
int a[] = { 24, 9, 29, 14, 19, 27 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArr(a, n);
quick(a, 0, n - 1);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);

return 0;
}
Counting Sort
 Counting sort is a sorting technique that is based on the keys between specific
ranges.

 This sorting technique doesn't perform sorting by comparing elements.

 It performs sorting by counting objects having distinct key values like hashing.

 After that, it performs some arithmetic operations to calculate each object's index
position in the output sequence.

 Counting sort is not used as a general-purpose sorting algorithm.

 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.

 Working of counting sort Algorithm

 Now, let's see the working of the counting sort Algorithm.
 To understand the working of the counting sort algorithm, let's take an unsorted
array. It will be easier to understand the counting sort via an example.
 Let the elements of array are -


 1. Find the maximum element from the given array. Let max be the maximum
element.


 2. Now, initialize array of length max + 1 having all 0 elements. This array will be
used to store the count of the elements in the given array.


 3. Now, we have to store the count of each array element at their corresponding
index in the count array.
 The count of an element will be stored as - Suppose array element '4' is appeared
two times, so the count of element 4 is 2. Hence, 2 is stored at the 4 th position of
the count array. If any element is not present in the array, place 0, i.e. suppose
element '3' is not present in the array, so, 0 will be stored at 3rd position.

 Now, store the cumulative sum of count array elements. It will help to place the
elements at the correct index of the sorted array.

 Similarly, the cumulative count of the count array is -


 4. Now, find the index of each element of the original array
 
 After placing element at its place, decrease its count by one. Before placing
element 2, its count was 2, but after placing it at its correct position, the new count
for element 2 is 1.


 Similarly, after sorting, the array elements are -


 Now, the array is completely sorted.

Program: Write a program to implement counting sort in C language.

1. #include<stdio.h>
2.
3. int getMax(int a[], int n) {
4. int max = a[0];
5. for(int i = 1; i<n; i++) {
6. if(a[i] > max)
7. max = a[i];
8. }
9. return max; //maximum element from the array
10. }
11.
12. void countSort(int a[], int n) // function to perform counting sort
13. {
14. int output[n+1];
15. int max = getMax(a, n);
16. int count[max+1]; //create count array with size [max+1]
17.
18.
19. for (int i = 0; i <= max; ++i)
20. {
21. count[i] = 0; // Initialize count array with all zeros
22. }
23.
24. for (int i = 0; i < n; i++) // Store the count of each element
25. {
26. count[a[i]]++;
27. }
28.
29. for(int i = 1; i<=max; i++)
30. count[i] += count[i-1]; //find cumulative frequency
31.
32. /* This loop will find the index of each element of the original array in count array, and
33. place the elements in output array*/
34. for (int i = n - 1; i >= 0; i--) {
35. output[count[a[i]] - 1] = a[i];
36. count[a[i]]--; // decrease count for same numbers
37. }
38.
39. for(int i = 0; i<n; i++) {
40. a[i] = output[i]; //store the sorted elements into main array
41. }
42. }
43.
44. void printArr(int a[], int n) /* function to print the array */
45. {
46. int i;
47. for (i = 0; i < n; i++)
48. printf("%d ", a[i]);
49. }
50.
51. int main() {
52. int a[] = { 11, 30, 24, 7, 31, 16 };
53. int n = sizeof(a)/sizeof(a[0]);
54. printf("Before sorting array elements are - \n");
55. printArr(a, n);
56. countSort(a, n);
57. printf("\nAfter sorting array elements are - \n");
58. printArr(a, n);
59. return 0;
60.
61. }
Radix Sort
 Radix sort is the linear sorting algorithm that is used for integers.

 In Radix sort, there is digit by digit sorting is performed that is started from the least
significant digit to the most significant digit.

 The process of radix sort works similar to the sorting of students names, according to
the alphabetical order.

 In this case, there are 26 radix formed due to the 26 alphabets in English. In the first
pass, the names of students are grouped according to the ascending order of the
first letter of their names.

 After that, in the second pass, their names are grouped according to the ascending
order of the second letter of their name.

 And the process continues until we find the sorted list.

Working of Radix sort Algorithm

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

The steps used in the sorting of radix sort are listed as follows -

o First, we have to find the largest element (suppose max) from the given array.
Suppose 'x' be the number of digits in max. The 'x' is calculated because we need to go
through the significant places of all elements.
o After that, go through one by one each significant place. Here, we have to use any
stable sorting algorithm to sort the digits of each significant place.
Now let's see the working of radix sort in detail by using an example. To understand it more
clearly, let's take an unsorted array and try to sort it using radix sort. It will make the
explanation clearer and easier.

In the given array, the largest element is 736 that have 3 digits in it. So, the loop will run up
to three times (i.e., to the hundreds place). That means three passes are required to sort
the array.

Now, first sort the elements on the basis of unit place digits (i.e., x = 0). Here, we are using
the counting sort algorithm to sort the elements.
Pass 1:
In the first pass, the list is sorted on the basis of the digits at 0's place.

After the first pass, the array elements are -

Pass 2:
In this pass, the list is sorted on the basis of the next significant digits (i.e., digits at
10th place).
After the second pass, the array elements are -

Pass 3:
In this pass, the list is sorted on the basis of the next significant digits (i.e., digits at
100th place).
 After the third pass, the array elements are -

Now, the array is sorted in ascending order.

Program: Write a program to implement Radix sort in C language.

1. #include <stdio.h>
2.
3. int getMax(int a[], int n) {
4. int max = a[0];
5. for(int i = 1; i<n; i++) {
6. if(a[i] > max)
7. max = a[i];
8. }
9. return max; //maximum element from the array
10. }
11.
12. void countingSort(int a[], int n, int place) // function to implement counting sort
13. {
14. int output[n + 1];
15. int count[10] = {0};
16.
17. // Calculate count of elements
18. for (int i = 0; i < n; i++)
19. count[(a[i] / place) % 10]++;
20.
21. // Calculate cumulative frequency
22. for (int i = 1; i < 10; i++)
23. count[i] += count[i - 1];
24.
25. // Place the elements in sorted order
26. for (int i = n - 1; i >= 0; i--) {
27. output[count[(a[i] / place) % 10] - 1] = a[i];
28. count[(a[i] / place) % 10]--;
29. }
30.
31. for (int i = 0; i < n; i++)
32. a[i] = output[i];
33. }
34.
35. // function to implement radix sort
36. void radixsort(int a[], int n) {
37.
38. // get maximum element from array
39. int max = getMax(a, n);
40.
41. // Apply counting sort to sort elements based on place value
42. for (int place = 1; max / place > 0; place *= 10)
43. countingSort(a, n, place);
44. }
45.
46. // function to print array elements
47. void printArray(int a[], int n) {
48. for (int i = 0; i < n; ++i) {
49. printf("%d ", a[i]);
50. }
51. printf("\n");
52. }
53.
54. int main() {
55. int a[] = {181, 289, 390, 121, 145, 736, 514, 888, 122};
56. int n = sizeof(a) / sizeof(a[0]);
57. printf("Before sorting array elements are - \n");
58. printArray(a,n);
59. radixsort(a, n);
60. printf("After applying Radix sort, the array elements are - \n");
61. printArray(a, n);
62. }
Output:

After the execution of the above code, the output will be -

Heap Sort
Heap sort processes the elements by creating the min-heap or max-heap using the
elements of the given array. Min-heap or max-heap represents the ordering of array in
which the root element represents the minimum or maximum element of the array.

Heap sort basically recursively performs two main operations -

o Build a heap H, using the elements of array.

o Repeatedly delete the root element of the heap formed in 1st phase.
Before knowing more about the heap sort, let's first see a brief description of Heap.

What is a heap?
A heap is a complete binary tree, and the binary tree is a tree in which the node can have
the utmost two children. A complete binary tree is a binary tree in which all the levels except
the last level, i.e., leaf node, should be completely filled, and all the nodes should be left-
justified.

What is heap sort?

Heapsort is a popular and efficient sorting algorithm. The concept of heap sort is to
eliminate the elements one by one from the heap part of the list, and then insert them into
the sorted part of the list.

Heapsort is the in-place sorting algorithm.

Working of Heap sort Algorithm

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

In heap sort, basically, there are two phases involved in the sorting of elements. By using
the heap sort algorithm, they are as follows -

o The first step includes the creation of a heap by adjusting the elements of the
array.
o After the creation of heap, now remove the root element of the heap repeatedly
by shifting it to the end of the array, and then store the heap structure with the
remaining elements.
Now let's see the working of heap sort in detail by using an example. To understand it more
clearly, let's take an unsorted array and try to sort it using heap sort. It will make the
explanation clearer and easier.
First, we have to construct a heap from the given array and convert it into max heap.

After converting the given heap into max heap, the array elements are -

Next, we have to delete the root element (89) from the max heap. To delete this node, we
have to swap it with the last node, i.e. (11). After deleting the root element, we again have
to heapify it to convert it into max heap.

After swapping the array element 89 with 11, and converting the heap into max-heap, the
elements of array are -
In the next step, again, we have to delete the root element (81) from the max heap. To
delete this node, we have to swap it with the last node, i.e. (54). After deleting the root
element, we again have to heapify it to convert it into max heap.

After swapping the array element 81 with 54 and converting the heap into max-heap, the
elements of array are -

In the next step, we have to delete the root element (76) from the max heap again. To
delete this node, we have to swap it with the last node, i.e. (9). After deleting the root
element, we again have to heapify it to convert it into max heap.

After swapping the array element 76 with 9 and converting the heap into max-heap, the
elements of array are -
In the next step, again we have to delete the root element (54) from the max heap. To
delete this node, we have to swap it with the last node, i.e. (14). After deleting the root
element, we again have to heapify it to convert it into max heap.

After swapping the array element 54 with 14 and converting the heap into max-heap, the
elements of array are -

In the next step, again we have to delete the root element (22) from the max heap. To
delete this node, we have to swap it with the last node, i.e. (11). After deleting the root
element, we again have to heapify it to convert it into max heap.

After swapping the array element 22 with 11 and converting the heap into max-heap, the
elements of array are -
In the next step, again we have to delete the root element (14) from the max heap. To
delete this node, we have to swap it with the last node, i.e. (9). After deleting the root
element, we again have to heapify it to convert it into max heap.

After swapping the array element 14 with 9 and converting the heap into max-heap, the
elements of array are -

In the next step, again we have to delete the root element (11) from the max heap. To
delete this node, we have to swap it with the last node, i.e. (9). After deleting the root
element, we again have to heapify it to convert it into max heap.

After swapping the array element 11 with 9, the elements of array are -

Now, heap has only one element left. After deleting it, heap will be empty.

After completion of sorting, the array elements are -

 Now, the array is completely sorted.

Program: Write a program to implement heap sort in C language.

1. #include <stdio.h>
2. /* function to heapify a subtree. Here 'i' is the
3. index of root node in array a[], and 'n' is the size of heap. */
4. void heapify(int a[], int n, int i)
5. {
6. int largest = i; // Initialize largest as root
7. int left = 2 * i + 1; // left child
8. int right = 2 * i + 2; // right child
9. // If left child is larger than root
10. if (left < n && a[left] > a[largest])
11. largest = left;
12. // If right child is larger than root
13. if (right < n && a[right] > a[largest])
14. largest = right;
15. // If root is not largest
16. if (largest != i) {
17. // swap a[i] with a[largest]
18. int temp = a[i];
19. a[i] = a[largest];
20. a[largest] = temp;
21.
22. heapify(a, n, largest);
23. }
24. }
25. /*Function to implement the heap sort*/
26. void heapSort(int a[], int n)
27. {
28. for (int i = n / 2 - 1; i >= 0; i--)
29. heapify(a, n, i);
30. // One by one extract an element from heap
31. for (int i = n - 1; i >= 0; i--) {
32. /* Move current root element to end*/
33. // swap a[0] with a[i]
34. int temp = a[0];
35. a[0] = a[i];
36. a[i] = temp;
37.
38. heapify(a, i, 0);
39. }
40. }
41. /* function to print the array elements */
42. void printArr(int arr[], int n)
43. {
44. for (int i = 0; i < n; ++i)
45. {
46. printf("%d", arr[i]);
47. printf(" ");
48. }
49.
50. }
51. int main()
52. {
53. int a[] = {48, 10, 23, 43, 28, 26, 1};
54. int n = sizeof(a) / sizeof(a[0]);
55. printf("Before sorting array elements are - \n");
56. printArr(a, n);
57. heapSort(a, n);
58. printf("\nAfter sorting array elements are - \n");
59. printArr(a, n);
60. return 0;
61. }
Output