radixSort.
1 /* Name : Vaibhav Yadav
2
3 Roll No.59
4
5 Implementation on Radix Sort algorithm in C
6
7 C Program to sort an array in ascending order using Radix sort
8
9 */
10 #include <stdio.h>
11
12 // Function to get the maximum value in an array
13 int getMax(int arr[], int n)
14 {
15 int max = arr[0];
16 for (int i = 1; i < n; i++)
17 if (arr[i] > max)
18 max = arr[i];
19 return max;
20 }
21
22 // Function to perform counting sort based on a specific digit
23 void countingSort(int arr[], int n, int exp)
24 {
25 int output[n]; // Output array
26 int count[10] = {0};
27
28 // Count occurrences of each digit
29 for (int i = 0; i < n; i++)
30 count[(arr[i] / exp) % 10]++;
31
32 // Update count[i] so that it contains the position of this digit in the output array
33 for (int i = 1; i < 10; i++)
34 count[i] += count[i - 1];
35
36 // Build the output array
37 for (int i = n - 1; i >= 0; i--)
38 {
39 output[count[(arr[i] / exp) % 10] - 1] = arr[i];
40 count[(arr[i] / exp) % 10]--;
41 }
42
43 // Copy the output array to arr[], so that arr[] now contains sorted numbers
44 for (int i = 0; i < n; i++)
45 arr[i] = output[i];
46 }
47
48 // Radix Sort function
49 void radixSort(int arr[], int n)
50 {
51 // Find the maximum number to determine the number of digits
52 int max = getMax(arr, n);
53
54 // Perform counting sort for each digit, moving from least significant to most significant
55 for (int exp = 1; max / exp > 0; exp *= 10)
56 countingSort(arr, n, exp);
57 }
58
59 // Main function
60 int main()
61 {
62 int n;
63 printf("Enter the number of elements in the array: ");
64 scanf("%d", &n);
65
66 int arr[n];
67 printf("Enter the array elements:\n");
68 for (int i = 0; i < n; i++)
69 scanf("%d", &arr[i]);
70
71 // Call Radix Sort
72 radixSort(arr, n);
73
74 // Print the sorted array
75 printf("Sorted array is:\n");
76 for (int i = 0; i < n; i++)
77 printf("%d\t", arr[i]);
78
79 return 0;
80 }
81 /*
82 Best Case: O(n)
83 Average Case: O(nlogn)
84 Worst Case: O(n^2)
85
86
87 */
