Radix sort Shell sort
The idea of Radix Sort is to do digit by digit sort starting Shell sort is a generalized version of the insertion sort algorithm. It first sorts elements
from least significant digit to most significant digit. that are far apart from each other and successively reduces the interval between the
elements to be sorted.
In base 10, radix sort would sort by the digits in the The interval between the elements is reduced based on the sequence used.
one's place, then the ten's place, and so on.
Interval : N/2 , N/4 , …, 1
1. Find the maximum element of the array, let it 1. Step1 : Follow the steps until interval = 1
be maxmax 2. 1.1 Find interval
2. Find the number of digits in maxmax, let it be kk. 3. 1.2 create sublist
3. For each, ii ranging from 11 To kk, apply the 4. 1.3 Sort within the sublist
counting sort algorithm for the ith least-significant
digit of each element. Step 2:
Note : If any element has less than i digits consider 00 at When interval = 1, perform insertion sort.
its place (Because 29 can also be represented as 029).
Step1: Let the elements of array are -
Perform sorting on the LSB bits [at ONES position]
Let the interval of shell sort, are ., N/2, N/4,....,1 as the interval.
In the first loop, n is equal to 8 (size of the array), so the elements are lying at the interval
of 4 (n/2 = 4). Elements will be compared and swapped if they are not in order.
The resultant array after sorting is
Here, in the first loop, the element at the 0th position will be compared with the element at
4th position. If the 0th element is greater, it will be swapped with the element at 4th position.
Otherwise, it remains the same. This process will continue for the remaining element
At the interval of 4, the sublists are {33, 12}, {31, 17}, {40, 25}, {8, 42}.
Step 2:
Perform sorting on TENS Position , Now, we have to compare the values in every sub-list. After comparing, we have to swap
them if required in the original array. After comparing and swapping, the updated array
will look as follows -
In the second loop, elements are lying at the interval of 2 (n/4 = 2), where n = 8.
after sorting the resultant array is
Now, we are taking the interval of 2 to sort the rest of the array. With an interval of 2, two
th sublists will be generated - {12, 25, 33, 40}, and {17, 8, 31, 42}.
Step 3: Perform sorting on HUNDRED position .
The result after sorting HUNDRED th position
is
Now, we again have to compare the values in every sub-list. After comparing, we have to
swap them if required in the original array. After comparing and swapping, the updated
array will look as follows -
In the third loop, elements are lying at the interval of 1 (n/8 = 1), where n = 8. At last, we
use the interval of value 1 to sort the rest of the array elements. In this step, shell sort uses
insertion sort to sort the array elements.
Now, the array is sorted in ascending order.
#include <stdio.h>
int getMax(int list[], int n)
{
int mx = list[0];
int i; #include <stdio.h>
for (i = 1; i < n; i++) #include <stdlib.h>
if (list[i] > mx)
mx = list[i]; void shellSort(int a[], int n)
return mx; {
} int i, j, m;
int temp;
for (m = n / 2; m > 0; m /= 2)
{
void countSort(int list[], int n, int exp) for (j = m; j < n; j++)
{ {
int output[n]; for (i = j - m; i >= 0; i -= m)
int i, count[10] = { 0 }; {
if (a[i + m] >= a[i])
for (i = 0; i < n; i++) {
count[(list[i] / exp) % 10]++; break;
for (i = 1; i < 10; i++) }
count[i] += count[i - 1]; else
{
for (i = n - 1; i >= 0; i--) temp = a[i];
{ a[i] = a[i + m];
output[count[(list[i] / exp) % 10] - 1]=list[i]; a[i + m] = temp;
count[(list[i] / exp) % 10]--; }
} }
}
for (i = 0; i < n; i++) }
list[i] = output[i]; printf("\n");
} printf("\nThe sorted array elements are given below\n");
void radixsort(int list[], int n) for (i = 0; i < n; i++)
{ {
int m = getMax(list, n); printf("a[%d]=%d ", i, a[i]);
}
int exp;
}
for (exp = 1; m / exp > 0; exp *= 10)
countSort(list, n, exp); int main()
} {
void print(int list[], int n) int i, n = 6;
{ int a[] = {15, 8, 17, 12, 38, 19};
int i; printf("\n:: Shell Sort ::\n");
for (i = 0; i < n; i++) printf("\nInput array elements\n");
printf("%d\t", list[i]); for (i = 0; i < n; i++)
}
{
int main() printf("a[%d]=%d ", i, a[i]);
{ }
int list[] = { 82, 901, 100, 12, 150, 77, 55, 23 }; shellSort(a, n);
int i, n = sizeof(list) / sizeof(list[0]); }
radixsort(list, n);
printf("\n\nList of numbers after sort: \n");
print(list, n);
return 0;
}
