The C programs in this section illustrate other special Sorting Algorithms. These include Insertion Sort, Postman Sort, LSDRadix Sort, Heap Sort and Gnome Sort. Insertion Sort sorts the array by shifting the elements one by one. Postman Sort is a type of Bucket Sort in which the elements of an array are divided into buckets and then each bucket is sorted individually. LSDRadix Algorithm is used to sort the keys in integer representation order. Heap Sort is based on binary heap data structure and sorts elements similar to selection sort where the maximum element is placed at the end of the list. Gnome sort method sorts the items by comparing the current item with the previous item. If they are in order, move to the next item; If they are out of order, swap them and move to the previous item. If there is no previous item, move to the next item.
This is a C Program to implement Insertion Sort Algorithm.
Problem Description
We have to input an array of numbers and sort them using Insertion Sort algorithm in C Language.
Problem Solution
1. Here in order to sort an array we will be using Insertion Sort Algorithm. There are many advantages associated with an insertion sort. It is simple to implement and is quite efficient for small sets of data, especially if it is substantially sorted.
2. Another advantage associated with insertion sort is the fact that it needs only a constant amount of memory space for the whole operation. It is more efficient than other similar algorithms such as bubble sort or selection sort.
For example:
If we have the array as {40,10,50,70,30}
and we apply insertion sort to sort the array,
then the resultant array after each iteration will be as follows:
Original array: {40, 10, 50, 70, 30}
Array after first iteration is 10 -> 40 -> 50 -> 70 -> 30
Array after second iteration is 10 -> 40 -> 50 -> 70 -> 30
Array after third iteration is 10 -> 40 -> 50 -> 70 -> 30
Array after fourth iteration is 10 -> 30 -> 40 -> 50 -> 70
Sorted array is 10 30 40 50 70
Expected Input and Output
1. Average case (Unsorted array): When the input array has random distribution of numbers.
For example:
If the input array is {4, 6, 1, 2, 5, 3}
the expected output array will have data as {1, 2, 3, 4, 5, 6}
2. Best case (Sorted Array): When the input array is already sorted, in that case we have to make minimum number of swaps.
For example:
If the input array has data as {-3, 31, 66}
then the expected output array will have data as {-3, 31, 66}
3. Worst Case (Reverse sorted array): When the array is sorted in reverse manner, in that case we have to make maximum number of swaps.
For example:
If the input array has elements as {9, 8, 6, 3, 1}
then the output array will have data as {1, 3, 6, 8, 9}
Program/Source Code
Here is source code of the C Program to sort an array of integers using Insertion Sort Algorithm. The program is successfully compiled and tested using Codeblocks gnu/gcc compiler on Windows 10. The program output is also shown below.
-
/* C Program to sort an array in ascending order using Insertion Sort */
-
#include <stdio.h>
-
int main()
-
{
-
int n, i, j, temp;
-
printf("Enter number of elements\n");
-
scanf("%d", &n);
-
int arr[n];
-
printf("Enter %d integers\n", n);
-
for (i = 0; i < n; i++)
-
{
-
scanf("%d", &arr[i]);
-
}
-
for (i = 1 ; i <= n - 1; i++)
-
{
-
j = i;
-
while ( j > 0 && arr[j-1] > arr[j])
-
{
-
temp = arr[j];
-
arr[j] = arr[j-1];
-
arr[j-1] = temp;
-
j--;
-
}
-
}
-
printf("Sorted list in ascending order:\n");
-
for (i = 0; i <= n - 1; i++)
-
{
-
printf("%d\n", arr[i]);
-
}
-
return 0;
-
}
Program Explanation
1. Insertion Sort is basically insertion of an element from a random set of numbers, to its correct position where it should actually be, by shifting the other elements if required.
2. The first element in the array is considered as sorted, even if it is an unsorted array. The array is sub-divided into two parts, the first part holds the first element of the array which is considered to be sorted and second part contains all the remaining elements of array.
3. With each iteration one element from the second part is picked and inserted into the first part of array at its correct position by shifting the existing elements if required.
4. This goes until the last element in second part of array is placed in correct position in the output array.
5. In some cases Insertion Sort is considered better than selection and bubble sort because insertion sort has time complexity of O(n) in best case, while selection and bubble sort have time complexities of the order O(n^2)
Runtime Test Cases
/* Average case */
Enter number of elements
6
Enter 6 integers
4 6 1 2 5 3
Sorted list in ascending order:
1
2
3
4
5
6
/* Best case */
Enter number of elements
3
Enter 3 integers
-3 31 66
Sorted list in ascending order:
-3
31
66
/* Worst case */
Enter number of elements
5
Enter 5 integers
9 8 6 3 1
Sorted list in ascending order:
1
3
6
8
9
This C Program implements Postman Sort Algorithm.
Here is source code of the C Program implements Postman Sort Algorithm. The C program is successfully compiled and run on a Linux system. The program output is also shown below.
-
/*
-
* C Program to Implement Postman Sort Algorithm
-
*/
-
#include <stdio.h>
-
-
void arrange(int,int);
-
int array[100], array1[100];
-
int i, j, temp, max, count, maxdigits = 0, c = 0;
-
-
void main()
-
{
-
int t1, t2, k, t, n = 1;
-
-
printf("Enter size of array :");
-
scanf("%d", &count);
-
printf("Enter elements into array :");
-
for (i = 0; i < count; i++)
-
{
-
scanf("%d", &array[i]);
-
array1[i] = array[i];
-
}
-
for (i = 0; i < count; i++)
-
{
-
t = array[i]; /*first element in t */
-
while(t > 0)
-
{
-
c++;
-
t = t / 10; /* Find MSB */
-
}
-
if (maxdigits < c)
-
maxdigits = c; /* number of digits of a each number */
-
c = 0;
-
}
-
while(--maxdigits)
-
n = n * 10;
-
-
for (i = 0; i < count; i++)
-
{
-
max = array[i] / n; /* MSB - Dividnng by perticular base */
-
t = i;
-
for (j = i + 1; j < count;j++)
-
{
-
if (max > (array[j] / n))
-
{
-
max = array[j] / n; /* greatest MSB */
-
t = j;
-
}
-
}
-
temp = array1[t];
-
array1[t] = array1[i];
-
array1[i] = temp;
-
temp = array[t];
-
array[t] = array[i];
-
array[i] = temp;
-
}
-
while (n >= 1)
-
{
-
for (i = 0; i < count;)
-
{
-
t1 = array[i] / n;
-
for (j = i + 1; t1 == (array[j] / n); j++);
-
arrange(i, j);
-
i = j;
-
}
-
n = n / 10;
-
}
-
printf("\nSorted Array (Postman sort) :");
-
for (i = 0; i < count; i++)
-
printf("%d ", array1[i]);
-
printf("\n");
-
}
-
-
/* Function to arrange the of sequence having same base */
-
void arrange(int k,int n)
-
{
-
for (i = k; i < n - 1; i++)
-
{
-
for (j = i + 1; j < n; j++)
-
{
-
if (array1[i] > array1[j])
-
{
-
temp = array1[i];
-
array1[i] = array1[j];
-
array1[j] = temp;
-
temp = (array[i] % 10);
-
array[i] = (array[j] % 10);
-
array[j] = temp;
-
}
-
}
-
}
-
}
$ cc postman.c
$ a.out
/* Average case */
Enter size of array :8
Enter elements into array :170
45
90
75
802
24
2
66
Sorted Array (Postman sort) :2 24 45 66 75 90 170 802
$ a.out
/* Best case */
Enter size of array :7
Enter elements into array :25
64
185
136
36
3645
45
Sorted Array (Postman sort) :25 36 45 64 136 185 3645
$ a.out
/* Worst case */
Enter size of array :8
Enter elements into array :15
214
166
0836
98
6254
73
642
Sorted Array (Postman sort) :15 73 98 166 214 642 836 6254
This C Program sorts an integer array using lsdradix sort algorithm.
Here is source code of the C Program to sort an integer array using lsdradix sort algorithm. The C program is successfully compiled and run on a Linux system. The program output is also shown below.
-
/*
-
* C Program to Sort an Integer Array using LSDRadix Sort Algorithm
-
*/
-
#include <stdio.h>
-
-
int min = 0, count = 0, array[100] = {0}, array1[100] = {0};
-
-
void main()
-
{
-
int k, i, j, temp, t, n;
-
-
printf("Enter size of array :");
-
scanf("%d", &count);
-
printf("Enter elements into array :");
-
for (i = 0; i < count; i++)
-
{
-
scanf("%d", &array[i]);
-
array1[i] = array[i];
-
}
-
for (k = 0; k < 3; k++)
-
{
-
for (i = 0; i < count; i++)
-
{
-
min = array[i] % 10; /* To find minimum lsd */
-
t = i;
-
for (j = i + 1; j < count; j++)
-
{
-
if (min > (array[j] % 10))
-
{
-
min = array[j] % 10;
-
t = j;
-
}
-
}
-
temp = array1[t];
-
array1[t] = array1[i];
-
array1[i] = temp;
-
temp = array[t];
-
array[t] = array[i];
-
array[i] = temp;
-
-
}
-
for (j = 0; j < count; j++) /*to find MSB */
-
array[j] = array[j] / 10;
-
}
-
printf("Sorted Array (lSdradix sort) : ");
-
for (i = 0; i < count; i++)
-
printf("%d ", array1[i]);
-
}
$ cc lsdradix.c
$ a.out
/* Average Case */
Enter size of array :7
Enter elements into array :170
45
90
75
802
24
2
Sorted Array (ladradix sort) : 2 24 45 75 90 170 802
$ a.out
/*Best case */
Enter size of array :7
Enter elements into array :22
64
121
78
159
206
348
Sorted Array (ladradix sort) : 22 64 78 159 121 206 348
$ a.out
/* Worst case */
Enter size of array :7
Enter elements into array :985
27
64
129
345
325
091
Sorted Array (ladradix sort) : 27 64 91 129 325 345 985
This C Program sorts an array based on heap sort algorithm.
Here is source code of the C Program to sort an array based on heap sort algorithm. The C program is successfully compiled and run on a Linux system. The program output is also shown below.
-
/*
-
* C Program to sort an array based on heap sort algorithm(MAX heap)
-
*/
-
#include <stdio.h>
-
-
void main()
-
{
-
int heap[10], no, i, j, c, root, temp;
-
-
printf("\n Enter no of elements :");
-
scanf("%d", &no);
-
printf("\n Enter the nos : ");
-
for (i = 0; i < no; i++)
-
scanf("%d", &heap[i]);
-
for (i = 1; i < no; i++)
-
{
-
c = i;
-
do
-
{
-
root = (c - 1) / 2;
-
if (heap[root] < heap[c]) /* to create MAX heap array */
-
{
-
temp = heap[root];
-
heap[root] = heap[c];
-
heap[c] = temp;
-
}
-
c = root;
-
} while (c != 0);
-
}
-
-
printf("Heap array : ");
-
for (i = 0; i < no; i++)
-
printf("%d\t ", heap[i]);
-
for (j = no - 1; j >= 0; j--)
-
{
-
temp = heap[0];
-
heap[0] = heap[j /* swap max element with rightmost leaf element */
-
heap[j] = temp;
-
root = 0;
-
do
-
{
-
c = 2 * root + 1; /* left node of root element */
-
if ((heap[c] < heap[c + 1]) && c < j-1)
-
c++;
-
if (heap[root]<heap[c] && c<j) /* again rearrange to max heap array */
-
{
-
temp = heap[root];
-
heap[root] = heap[c];
-
heap[c] = temp;
-
}
-
root = c;
-
} while (c < j);
-
}
-
printf("\n The sorted array is : ");
-
for (i = 0; i < no; i++)
-
printf("\t %d", heap[i]);
-
printf("\n Complexity : \n Best case = Avg case = Worst case = O(n logn) \n");
-
}
$ cc heap.c
$ a.out
Average case
Enter no of elements :7
Enter the nos : 6
5
3
1
8
7
2
Heap array : 8 6 7 1 5 3 2
The sorted array is : 1 2 3 5 6 7 8
Complexity :
Best case = Avg case = Worst case = O(n logn)
$ a.out
/* Best case
Enter no of elements :7
Enter the nos : 12
10
8
9
7
4
2
Heap array : 12 10 8 9 7 4 2
The sorted array is : 2 4 7 8 9 10 12
Complexity :
Best case = Avg case = Worst case = O(n logn)
$ a.out
/* Worst case
Enter no of elements :7
Enter the nos : 5
7
12
6
9
10
14
Heap array : 14 9 12 5 6 7 10
The sorted array is : 5 6 7 9 10 12 14
Complexity :
Best case = Avg case = Worst case = O(n logn)
*/
This C Program sort the array elements using gnome sort. Gnome sort(stupid sort) is a sorting algorithm which is similar to insertion sort, except that moving an element to its proper place is accomplished by a series of swaps, as in bubble sort. It is conceptually simple, requiring no nested loops.
Here is source code of the C Program to sort array elements using gnome sort. The C program is successfully compiled and run on a Linux system. The program output is also shown below.
-
/*
-
* C Program to Sort the Array Elements using Gnome Sort
-
*/
-
#include <stdio.h>
-
-
void main()
-
{
-
int i, temp, ar[10], n;
-
-
printf("\nenter the elemts number u would like to enter:");
-
scanf("%d", &n);
-
printf("\nenter the elements to be sorted through gnome sort:\n");
-
for (i = 0; i < n; i++)
-
scanf("%d", &ar[i]);
-
i = 0;
-
while (i < n)
-
{
-
if (i == 0 || ar[i - 1] <= ar[i])
-
i++;
-
else
-
{
-
temp = ar[i-1];
-
ar[i - 1] = ar[i];
-
ar[i] = temp;
-
i = i - 1;
-
}
-
}
-
for (i = 0;i < n;i++)
-
printf("%d\t", ar[i]);
-
}
$ cc gnomesort.c
$ a.out
enter the elemts number u would like to enter:7
enter the elements to be sorted through gnome sort:
6
0
9
5
2
4
3
0 2 3 4 5 6 9
$ a.out
enter the elemts number u would like to enter:6
enter the elements to be sorted through gnome sort:
1
2
4
5
6
7
1 2 4 5 6 7
$ a.out
enter the elemts number u would like to enter:9
enter the elements to be sorted through gnome sort:
9
8
7
6
5
4
3
3
2
2 3 3 4 5 6 7 8 9
