Logo

Navigation
  • Home
  • Services
    • ERP Solutions
    • Implementation Solutions
    • Support and Maintenance Solutions
    • Custom Solutions
    • Upgrade Solutions
    • Training and Mentoring
    • Web Solutions
    • Production Support
    • Architecture Designing
    • Independent Validation and Testing Services
    • Infrastructure Management
  • Expertise
    • Microsoft Development Expertise
    • Mobile Development
    • SQL Server Database and BI
    • SAP BI, SAP Hana, SAP BO
    • Oracle and BI
    • Oracle RAC
  • Technical Training
    • Learn Data Management
      • Business Intelligence
      • Data Mining
      • Data Modeling
      • Data Warehousing
      • Disaster Recovery
    • Learn Concepts
      • Application Development
      • Client Server
      • Cloud Computing Tutorials
      • Cluster Computing
      • CRM Tutorial
      • EDI Tutorials
      • ERP Tutorials
      • NLP
      • OOPS
      • Concepts
      • SOA Tutorial
      • Supply Chain
      • Technology Trends
      • UML
      • Virtualization
      • Web 2.0
    • Learn Java
      • JavaScript Tutorial
      • JSP Tutorials
      • J2EE
    • Learn Microsoft
      • MSAS
      • ASP.NET
      • ASP.NET 2.0
      • C Sharp
      • MS Project Training
      • Silverlight
      • SQL Server 2005
      • VB.NET 2005
    • Learn Networking
      • Networking
      • Wireless
    • Learn Oracle
      • Oracle 10g
      • PL/SQL
      • Oracle 11g Tutorials
      • Oracle 9i
      • Oracle Apps
    • Learn Programming
      • Ajax Tutorial
      • C Language
      • C++ Tutorials
      • CSS Tutorial
      • CSS3 Tutorial
      • JavaScript Tutorial
      • jQuery Tutorial
      • MainFrame
      • PHP Tutorial
      • VBScript Tutorial
      • XML Tutorial
    • Learn Software Testing
      • Software Testing Types
      • SQA
      • Testing
  • Career Training
    • Career Improvement
      • Career Articles
      • Certification Articles
      • Conflict Management
      • Core Skills
      • Decision Making
      • Entrepreneurship
      • Goal Setting
      • Life Skills
      • Performance Development
      • Personal Excellence
      • Personality Development
      • Problem Solving
      • Relationship Management
      • Self Confidence
      • Self Supervision
      • Social Networking
      • Strategic Planning
      • Time Management
    • Education Help
      • Career Tracks
      • Essay Writing
      • Internship Tips
      • Online Education
      • Scholarships
      • Student Loans
    • Managerial Skills
      • Business Communication
      • Business Networking
      • Facilitator Skills
      • Managing Change
      • Marketing Management
      • Meeting Management
      • Process Management
      • Project Management
      • Project Management Life Cycle
      • Project Management Process
      • Project Risk Management
      • Relationship Management
      • Task Management
      • Team Building
      • Virtual Team Management
    • Essential Life Skills
      • Anger Management
      • Anxiety Management
      • Attitude Development
      • Coaching and Mentoring
      • Emotional Intelligence
      • Stress Management
      • Positive Thinking
    • Communication Skills
      • Conversation Skills
      • Cross Culture Competence
      • English Vocabulary
      • Listening Skills
      • Public Speaking Skills
      • Questioning Skills
    • Soft Skills
      • Assertive Skills
      • Influence Skills
      • Leadership Skills
      • Memory Skills
      • People Skills
      • Presentation Skills
    • Finding a Job
      • Etiquette Tips
      • Group Discussions
      • HR Interviews
      • Interview Notes
      • Job Search Tips
      • Resume Tips
      • Sample Resumes
 

C Algorithms – Radix Sort

By Exforsys | on September 10, 2011 |
C Algorithms

Radix sort is a sorting algorithm that sorts the data, integers for example, by splitting the numbers into individual digits and comparing the individual digits sharing the same significant position.

Also, a positional notation is required, because instead of integers there could be strings of characters or floating point numbers.

The radix sort can be classified into 2 types: LSD (least significant digit) or MSD (most significant digit). The LSD sorting type begins from the least significant digit to the most significant digit and the MSD works the other way around.

Note: having the number 150, the number 0 is the least significant digit and 1 is the most significant digit.

Step by step example :

Having the following list, let’s try to use radix sort to arrange the numbers from lowest to greatest:

Unsorted list: 12, 8, 92, 7, 100, 500. Because there are numbers with 3 digits, we can write the initial list like this: 012, 008, 092, 007, 100, 500.

Now by using the LSD, the sorting may begin with step 1:

Write all the numbers that have one of the following digit as the LSD of the numbers from the list:

0:100, 500

1:-

2:012, 092

3:-

4:-

5:-

6:-

7:007

8:008

9:-

Also, if you have two numbers with the same digit like 012 and 092, you write them in the order from the list.

Now, the order of the numbers according to step 1 is: 100, 500, 012, 092, 007, 008, which differs a bit from the initial list.

We repeat step 1, but now we use the second digit :

0:100, 500, 007, 008

1:012

2:-

3:-

4:-

5:-

6:-

7:-

8:-

9:092

After step 2, the order is: 100, 500, 007, 008, 012, 092.

Step 3, using the MSB:

0:007, 008, 012, 092

1: 100

2:-

3:-

4:-

5: 500

6:-

7:-

8:-

9:-

The final list is the sorted one: 007, 008, 012, 092, 100, 500.

Sample code:

  1.  #include < iostream >
  2. using namespace std;
  3.  #define MAX 100
  4.  
  5. void print(int *a, int n)	//Prints the numbers of an array
  6. {
  7. 	int i;
  8. 	for (i = 0; i < n; i++)
  9. 		cout << " " << a[i];
  10. }
  11.  
  12. void radixsort(int *a, int n)
  13. {
  14. 	int i, b[MAX], m = 0, exp = 1;
  15. 	for (i = 0; i < n; i++)
  16. 	{
  17. 		if (a[i] > m)
  18. 			m = a[i];
  19. 	}
  20.  
  21. 	while (m / exp > 0)
  22. 	{
  23. 		int bucket[10] ={0};
  24. 		for (i = 0; i < n; i++)
  25. 			bucket[a[i] / exp % 10]++;
  26. 		for (i = 1; i < 10; i++)
  27. 			bucket[i] += bucket[i - 1];
  28. 		for (i = n - 1; i >= 0; i--)
  29. 			b[--bucket[a[i] / exp % 10]] = a[i];
  30. 		for (i = 0; i < n; i++)
  31. 			a[i] = b[i];
  32. 		exp *= 10;
  33.  
  34.  
  35. 		cout << "nPASS   : ";
  36. 		print(a, n);	//Prints the results from the first pass
  37.  
  38. 	}
  39. }
  40.  
  41.  
  42. int main()
  43. {
  44. 	int arr[MAX];
  45. 	int i, n;
  46.  
  47. 	cout << "Enter total elements n < " << MAX << endl;	
  48. 	cin>>n;
  49.  
  50.  
  51. 	cout << "Enter " << n << " Elements : " << endl;
  52. 	for (i = 0; i < n; i++)
  53. 		cin>>arr[i];
  54.  
  55.  
  56. 	cout<<"nARRAY  : ";
  57. 	print(&arr[0], n);
  58.  
  59. 	radixsort(&arr[0], n);
  60.  
  61. 	cout << "nSORTED : ";
  62. 	print(&arr[0], n);
  63. 	printf("n");
  64.  
  65. 	return 0;
  66. }

Output:

Code explanation:

  1. int i, b[MAX], m = 0, exp = 1;
  2. 	for (i = 0; i < n; i++)
  3. 	{
  4. 		if (a[i] > m)
  5. 			m = a[i];
  6. 	}
  7.  
  8. 	while (m / exp > 0)
  9. 	{
  10. 		int bucket[10] ={0};
  11. 		for (i = 0; i < n; i++)
  12. 			bucket[a[i] / exp % 10]++;
  13. 		for (i = 1; i < 10; i++)
  14. 			bucket[i] += bucket[i - 1];
  15. 		for (i = n - 1; i >= 0; i--)
  16. 			b[--bucket[a[i] / exp % 10]] = a[i];
  17. 		for (i = 0; i < n; i++)
  18. 			a[i] = b[i];
  19. 		exp *= 10;
  20.  
  21.  
  22. 		cout << "nPASS   : ";
  23. 		print(a, n);	//Prints the results from the first pass
  24. }

At the first for loop, the variable m will store the highest number from the array.

At the while loop, the condition is to check if the number still has digits, and while this is true, a bucket (an array) with maxim 10 storage places (the values from 0 to 9) will store the proper numbers, just like in the example from above. At the end of the while loop the exp must increase by a factor of 10 compared to the previous one, and at the next check of the while loop, the condition will be tested to see of the number of digits is greater than 0.

Complexity:

The time complexity of the algorithm is as follows: Suppose that the n input numbers have maximum k digits. Then the Counting Sort procedure is called a total of k times. Counting Sort is a linear, or O(n) algorithm. So the entire Radix Sort procedure takes O(k*n) time. If the numbers are of finite size, the algorithm runs in O(n) asymptotic time.

Advantages:

  • if it’s implemented in Java, it would be faster than QuickSort or HeapSort;
  • is stable, meaning it preserves existing order of equal keys.
  • is quite good on small keys.

Disadvantages:

  • does not work well when you have very long keys, because the total sorting time is proportional to key length and to the number of items to sort.
  • you have to write an unconventional compare routine.
  • It requires fixed size keys, and some standard way of breaking the keys into pieces.

Conclusion:

Radix Sort is a clever and intuitive little sorting algorithm. Radix Sort can also take up more space than other sorting algorithms, since in addition to the array that will be sorted, you need to have a sub-list for each of the possible digits or letters. If you are sorting pure English words, you will need at least 26 different sub-lists, and if you are sorting alphanumeric words or sentences, you will probably need more than 40 sub-lists in all. Also, it depends on the digits or letters, so for every different type of data, the programmer has to rewrite the sorting algorithm, which is quite a big drawback.

« « C Algorithms – Shell Sort
C Algorithms – Selection Sort » »

Author Description

Avatar

Editorial Team at Exforsys is a team of IT Consulting and Training team led by Chandra Vennapoosa.

Free Training

RSSSubscribe 394 Followers
  • Popular
  • Recent
  • C Algorithms – Counting Sort

    September 12, 2011 - 0 Comment
  • C Algorithms – Shell Sort

    September 10, 2011 - 0 Comment
  • C Algorithms – The Problem of Sorting the Elements

    September 8, 2011 - 0 Comment
  • C Algorithms – Bucket Sort

    September 13, 2011 - 0 Comment
  • C Algorithms – Topological Sort

    September 15, 2011 - 0 Comment
  • C Algorithms – Graph Theory

    September 15, 2011 - 0 Comment
  • C Algorithms – Gnome Sort

    September 14, 2011 - 0 Comment
  • C Algorithms – Merge Sort

    September 12, 2011 - 0 Comment
  • C Algorithms – Insertion Sort

    September 9, 2011 - 0 Comment
  • C Algorithms – Dijkstra’s Algorithm

    September 17, 2011 - 0 Comment
  • C Algorithms – Dijkstra’s Algorithm

    September 17, 2011 - 0 Comment
  • C Algorithms – Breadth-First Search (BFS)

    September 16, 2011 - 0 Comment
  • C Algorithms – Depth-First Search (DFS)

    September 16, 2011 - 0 Comment
  • C Algorithms – Topological Sort

    September 15, 2011 - 0 Comment
  • C Algorithms – Graph Theory

    September 15, 2011 - 0 Comment
  • C Algorithms – Gnome Sort

    September 14, 2011 - 0 Comment
  • C Algorithms – Comb Sort

    September 14, 2011 - 0 Comment
  • C Algorithms – Bucket Sort

    September 13, 2011 - 0 Comment
  • C Algorithms – Quick Sort

    September 13, 2011 - 0 Comment
  • C Algorithms – Merge Sort

    September 12, 2011 - 0 Comment

Exforsys e-Newsletter

ebook
 

Related Articles

  • C Algorithms – Dijkstra’s Algorithm
  • C Algorithms – Breadth-First Search (BFS)
  • C Algorithms – Depth-First Search (DFS)
  • C Algorithms – Topological Sort
  • C Algorithms – Graph Theory

Latest Articles

  • Project Management Techniques
  • Product Development Best Practices
  • Importance of Quality Data Management
  • How to Maximize Quality Assurance
  • Utilizing Effective Quality Assurance Strategies
  • Sitemap
  • Privacy Policy
  • DMCA
  • Trademark Information
  • Contact Us
© 2023. All Rights Reserved.IT Training and Consulting
This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish.AcceptReject Read More
Privacy & Cookies Policy

Privacy Overview

This website uses cookies to improve your experience while you navigate through the website. Out of these, the cookies that are categorized as necessary are stored on your browser as they are essential for the working of basic functionalities of the website. We also use third-party cookies that help us analyze and understand how you use this website. These cookies will be stored in your browser only with your consent. You also have the option to opt-out of these cookies. But opting out of some of these cookies may affect your browsing experience.
Necessary
Always Enabled
Necessary cookies are absolutely essential for the website to function properly. This category only includes cookies that ensures basic functionalities and security features of the website. These cookies do not store any personal information.
Non-necessary
Any cookies that may not be particularly necessary for the website to function and is used specifically to collect user personal data via analytics, ads, other embedded contents are termed as non-necessary cookies. It is mandatory to procure user consent prior to running these cookies on your website.
SAVE & ACCEPT