C++ Program to Implement Sorting of Less than 100 Numbers in O(n) Complexity

This is a C++ Program to Sort the Numbers lesser than 100 in O(n) Complexity.

Problem Description

1. We can implement the task best using Radix sort.
2. In this algorithm sorting of data is done from least significant digit to most significant digit.
3. Here we need 10 different spaces labeled 0 to 9.
4. Assume we have ‘n’ number of inputs.
5. Let ‘d’ be the maximum number of digit the input data has, here d can have values either 1 or 2 or 3.
6. The time complexity for radix sort is O(n*3) that is O(n).
7. Radix sort solves the problem of card sorting by sorting on the least significant digit first.

Problem Solution

1. Get the maximum value from the input array which has ‘d’ digits.
2. Starting from least significant digit, sort the data.
3. Take this data as input for next significant digit.
4. Run the iteration till d digit.
5. Display the result.
6. Exit.

Program/Source Code

C++ program to Sort the Numbers lesser than 100 in O(n) Complexity using Radix Sort.
This program is successfully run on Dev-C++ using TDM-GCC 4.9.2 MinGW compiler on a Windows system.

#include <iostream>
 
using namespace std;
 
// Get maximum value from array.
int getMax(int arr[], int n)
{
	int max = arr[0];
	for (int i = 1; i < n; i++)
		if (arr[i] > max)
			max = arr[i];
	return max;
}
 
// Count sort of arr[].
void countSort(int arr[], int n, int exp)
{
	// Count[i] array will be counting the number of array values having that 'i' digit at their (exp)th place.  
	int output[n], i, count[10] = {0};
 
	// Count the number of times each digit occurred at (exp)th place in every input.
	for (i = 0; i < n; i++)
		count[(arr[i] / exp) % 10]++;
 
	// Calculating their cumulative count.
	for (i = 1; i < 10; i++)
		count[i] += count[i-1];
 
	// Inserting values according to the digit '(arr[i] / exp) % 10' fetched into count[(arr[i] / exp) % 10].
	for (i = n - 1; i >= 0; i--)
	{
		output[count[(arr[i] / exp) % 10] - 1] = arr[i];
		count[(arr[i] / exp) % 10]--;
	}
 
	// Assigning the result to the arr pointer of main().
	for (i = 0; i < n; i++)
		arr[i] = output[i];
}
 
// Sort arr[] of size n using Radix Sort.
void radixsort(int arr[], int n)
{
	int exp, m;
	m = getMax(arr, n);
 
	// Calling countSort() for digit at (exp)th place in every input.
	for (exp = 1; m/exp > 0; exp *= 10)
		countSort(arr, n, exp);
}
 
int main()
{
	int n, i;
	cout<<"\nEnter the number of data element to be sorted: ";
	cin>>n;
 
	int arr[n];
	for(i = 0; i < n; i++)
	{
		cout<<"Enter element "<<i+1<<": ";
		cin>>arr[i];
	}
 
	radixsort(arr, n);
 
	// Printing the sorted data.
	cout<<"\nSorted Data ";
	for (i = 0; i < n; i++)
		cout<<"->"<<arr[i];
	return 0;
}
Program Explanation

1. Take input of data.
2. Get the maximum of input data.
3. Run the countSort() till (m/exp) > 0.
4. Sort the data on the basis of the digit at (exp)th place.
5. Assign the sorted data back to arr[] array.
6. Check the condition in step 3.
7. If false, print the sorted output.
8. Exit.

advertisement
advertisement
Runtime Test Cases
 
Case 1:
Enter the number of data element to be sorted: 10
Enter element 1: 56
Enter element 2: 32
Enter element 3: 14
Enter element 4: 26
Enter element 5: 3
Enter element 6: 84
Enter element 7: 95
Enter element 8: 61
Enter element 9: 35
Enter element 10: 8
 
Sorted Data ->3->8->14->26->32->35->56->61->84->95

Sanfoundry Global Education & Learning Series – C++ Algorithms.
To practice all C++ Algorithms, here is complete set of 1000 C++ Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.