shell sort and radix sort

1. #include <stdio.h>

2. void shellsort(int arr[], int num)

3. {

4.     int i, j, k, tmp;

5.     for (i = num / 2; i > 0; i = i / 2)

6.     {

7.         for (j = i; j < num; j++)

8.         {

9.             for(k = j - i; k >= 0; k = k - i)

10.             {

11.                 if (arr[k+i] >= arr[k])

12.                     break;

13.                 else

14.                 {

15.                     tmp = arr[k];

16.                     arr[k] = arr[k+i];

17.                     arr[k+i] = tmp;

18.                 }

19.             }

20.         }

21.     }

22. }

radix sort:

// C implementation of Radix Sort 

#include <stdio.h>

#include <stdlib.h>

int getMax(int arr[], int n) 

{ 

int mx = arr[0]; 

for (int i = 1; i < n; i++) 

if (arr[i] > mx) 

mx = arr[i]; 

return mx; 

} 

// A function to do counting sort of arr[] according to 

// the digit represented by exp. 

void countSort(int arr[], int n, int exp) 

{ 

int output[n]; // output array 

int i, count[10] = {0}; 

// Store count of occurrences in count[] 

for (i = 0; i < n; i++) 

count[ (arr[i]/exp)%10 ]++; 

// Change count[i] so that count[i] now contains actual 

// position of this digit in output[] 

for (i = 1; i < 10; i++) 

count[i] += count[i - 1]; 

// Build the output array 

for (i = n - 1; i >= 0; i--) 

{ 

output[count[ (arr[i]/exp)%10 ] - 1] = arr[i]; 

count[ (arr[i]/exp)%10 ]--; 

} 

// Copy the output array to arr[], so that arr[] now 

// contains sorted numbers according to current digit 

for (i = 0; i < n; i++) 

arr[i] = output[i]; 

} 

// The main function to that sorts arr[] of size n using 

// Radix Sort 

void radixsort(int arr[], int n) 

{ 

// Find the maximum number to know number of digits 

int m = getMax(arr, n); 

// Do counting sort for every digit. Note that instead 

// of passing digit number, exp is passed. exp is 10^i 

// where i is current digit number 

for (int exp = 1; m/exp > 0; exp *= 10) 

countSort(arr, n, exp); 

} 

void print(int arr[], int n) 

{ 

for (int i = 0; i < n; i++) 

   printf("%d  ",arr[i]); 

} 

// Driver program to test above functions 

int main() 

{ 

int arr[] = {170, 45, 75, 90, 802, 24, 2, 66}; 

int n = sizeof(arr)/sizeof(arr[0]); 

radixsort(arr, n); 

print(arr, n); 

return 0; 

}