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 – Counting Sort

By Exforsys | on September 12, 2011 |
C Algorithms

Counting sort is a sorting algorithm that is not based on comparison like most other methods. This method of sorting is used when all elements to be sorted fall in a known, finite and reasonably small range.

How it works:

The algorithm refers to finding for each element a[i] the number of elements from the array that are lower than it.

Step by step example :

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

Unsorted list, the array A contains the elements to be sorted:

We count the number of occurrences from the list into the array C, and for example we found one occurrence for the element 3 so far :

PS: A – list of sorting elements, B – Sorted list, C – number of occurences.

The next element is 2, so we increment by 1 the array C and so on until the end of the array:

The next element is 3, so we increment by 1 :

The next element is 9, so we increment by 1 :

The next element is 2, so we increment by 1 :

The next element is 8, so we increment by 1 :

The next element is 1, so we increment by 1 :

The next element is 4, so we increment by 1 :

The next element is 10, so we increment by 1 :

The next element is 1, so we increment by 1 :

Now, using the elements of the C array, we add the current element with the one from below:

Now let us sort things out a bit. First, look at the last element from the sorting list, which is 1, next look at what number is on the position with 1 as the index from the C array – where all the occurrences are. That number will point to the position in the final sorted array B, which is 2:

Decrease the number of occurrences by 1 since we found a place for a number:

Now, we do the same for the next element which is 10, and the position for it is 10:

Decrease the number of occurrences by 1 since we found a place for a number:

4 is the next element, after which we decrease the number of occurrences:

1 is the next element, after which we decrease the number of occurrences:

8 is the next element, after which we decrease the number of occurrences:

2 is the next element, after which we decrease the number of occurrences:

9 is the next element, after which we decrease the number of occurrences:

3 is the next element, after which we decrease the number of occurrences:

2 is the next element, after which we decrease the number of occurrences:

3 is the next element, after which we decrease the number of occurrences:

The data has been sorted! Look at the B array!

Sample code:

  1.  #include < iostream >
  2. using namespace std;
  3. int main()
  4. {
  5. 	long int A[10000];
  6. 	long int n = 100;
  7. 	int *p=new int[50];
  8. 	int i;
  9. 	int B[10];
  10. 	cout << "Please insert the number of elements to be sorted: ";
  11. 	cin >> n;	// The total number of elements
  12. 	for(int i=0;i< n;i++)
  13. 	{
  14. 		cout << "Input " << i << " element: ";
  15. 		cin >>A[i]; // Adding the elements to the array
  16. 	}
  17. 	cout << "Unsorted list:" << endl;	// Displaying the unsorted array
  18. 	for(int i=0;i < n;i++)
  19. 	{
  20. 		cout << A[i] << " ";
  21. 	}
  22. 	int k=A[0];
  23. 	for(int i=1;i< n;++i)
  24. 	{
  25. 		if(k< A[i])
  26. 		{
  27. 			k=A[i];
  28. 		}
  29. 	}
  30. 	for(int i=0;i< =k;++i)
  31. 	{
  32. 		p[i]=0;
  33. 	}
  34. 	for(int j=0;j< n;++j)
  35. 	{
  36. 		p[A[j]]=p[A[j]]+1;
  37. 	}
  38. 	for(int i=1;i< =k;++i)
  39. 	{
  40. 		p[i]=p[i-1]+p[i];
  41. 	}
  42.  
  43. 	for(int j=n-1;j>=0;--j)
  44. 	{
  45. 		i=A[j];
  46. 		B[p[i]-1]=i;
  47. 		p[i]=p[i]-1;
  48. 	}
  49. 	cout << "nSorted list:" << endl;	// Displaying the sorted array
  50. 	for(int i=0;i< n;i++)
  51. 	{
  52. 		cout << B[i] << " ";
  53. 	}
  54. 	return 0; 
  55. }

Output:

Code explanation:

  1. for(int i=0;i< =k;++i)
  2. 	{
  3. 		p[i]=0;
  4. 	}

The array that holds the number of occurrences is p, and at first, all the values will be set to 0.

  1. 	for(int j=0;j< n;++j)
  2. 	{
  3. 		p[A[j]]=p[A[j]]+1;
  4. 	}

The array p is filled up with the number of occurrences for each element.

  1. for(int i=1;i< =k;++i)
  2. 	{
  3. 		p[i]=p[i-1]+p[i];
  4. 	}

The sum of the previous element + current element is calculated.

  1. for(int j=n-1;j>=0;--j)
  2. 	{
  3. 		i=A[j];
  4. 		B[p[i]-1]=i;
  5. 		p[i]=p[i]-1;
  6. 	}

The elements are inserted into the proper places, and the last instruction decrements the number of occurrences.

Complexity:

Counting sort has a running time of O(n + k), where n is the number of elements to be sorted and k is the range of those numbers. If k = O(n), this algorithm has O(n) performance. Counting sort does not sort in place, since it creates two other arrays, counting array C and output array. The space complexity is O(n + k), where n and k are the length of the array A and C, respectively. No swap operations is performed during the process.

Advantages:

  • is stable;
  • is fast.

Disadvantages:

  • unsuitable for strings;
  • memory requirement, it requires both an array and a heap of size n;
  • not recommended on large sets of data.

Conclusion:

Counting sort may for example be the best algorithm for sorting numbers whose range is between 0 and 100, but it is probably unsuitable for sorting a list of names alphabetically. However, counting sort can be used with radix sort to sort a list of integers whose range is too large for counting sort to be suitable alone.

« « C Algorithms – Heap Sort
What is Exploratory Testing » »

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 – Quick Sort

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

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

    September 16, 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 – Radix Sort

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

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

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

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

    September 14, 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