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

By Exforsys | on September 13, 2011 |
C Algorithms

Bucket sort is a sorting algorithm that works by inserting the elements of the sorting array intro buckets, then, each bucket is sorted individually. The idea behind bucket sort is that if we know the range of our elements to be sorted, we can set up buckets for each possible element, and just toss elements into their corresponding buckets. We then empty the buckets in order, and the result is a sorted list. It is similar to radix sort.

How it works:

Initially we have to set up an array of empty buckets, then put each object into its bucket. After this, we sort each bucket with elements, and then we pass through each bucket in order and gather all the elements into the original array. Also, the number of buckets can be determined by the programmer.

Step by step example :

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

Unsorted list:

6 9 7 1 5 4 2 8 3

For this example, let us use 3 buckets, first is 1-3, second is 4-6, and last is 7-9.

                 
1 – 3 4 – 6 7 – 9

At the first run, the algorithm passes through the array, and selects the proper elements which then are moved into the bucket:

      1 5 4 2 8 3
      6     9 7  
1 – 3 4 – 6 7 – 9

And the same happens for the rest of elements, at the end of the pass, it will look like this:

1 2 3 6 5 4 9 7 8
1 – 3 4 – 6 7 – 9

Now, we sort each bucket individually, using either bucket sort or a different algorithm :

1 2 3 4 5 6 7 8 9
1 – 3 4 – 6 7 – 9

Now, we take the elements in the order from the buckets, and insert them into the original array. Also, the elements are in the proper order.

Sample code:

  1.  #include < iostream >
  2. using namespace std;
  3.  #define m 10	
  4. void bucketsort (int *a, int n)
  5. {
  6. 	int buckets [m];
  7.  
  8. 	for (int j=0; j < m; ++j)
  9. 		buckets[j]=0;
  10. 	for (int i=0; i < n; ++i)
  11. 		++buckets[a[i]];
  12. 	for (int i=0, j=0; j < m; ++j)
  13. 		for (int k=buckets[j]; k > 0; --k)
  14. 			a[i++]=j;
  15.  
  16. }
  17. int main ()
  18. {
  19. 	int n;
  20. 	int *a;
  21. 	cout << "Please insert the number of elements to be sorted: ";
  22. 	cin >> n;	// The total number of elements
  23. 	a = (int *)calloc(n, sizeof(int));
  24. 	cout << "nThe elements must be lower than the value of m = " << m << endl;
  25. 	for(int i=0;i< n;i++)
  26. 	{
  27.  
  28. 		cout << "Input " << i << " element: ";
  29. 		cin >>a[i]; // Adding the elements to the array
  30. 	}
  31. 	cout << "Unsorted list:" << endl;	// Displaying the unsorted array
  32. 	for(int i=0;i< n;i++)
  33. 	{
  34. 		cout << a[i] << " ";
  35. 	}
  36.  
  37. 	bucketsort(a,n);
  38. 	cout << "nSorted list:" << endl;	// Display the sorted array
  39. 	for(int i=0;i < n;i++)
  40. 	{
  41. 		cout << a[i] << " ";
  42. 	}
  43. 	return 0;
  44. }

Output :

Code explanation :

At first, we define the value of m, which means that all the elements we will introduce for the array will have to be lower than m. Next, we make buckets for the size of m, and we make them null and in the end, we add the elements to the proper buckets. It is not required another type of sorting algorithm, in this example we use bucket sort only, as we use a bucket for each element of the array, this might seem familiar with radix sort.

Complexity:

Bucket sort can be seen as a generalization of counting sort; in fact, if each bucket has size 1 then bucket sort degenerates to counting sort. The variable bucket size of bucket sort allows it to use O(n) memory instead of O(M) memory, where M is the number of distinct values; in exchange, it gives up counting sort’s O(n + M) worst-case behavior.

The time complexity of bucket sort is: O(n + m) where: m is the range input values, n is the total number of values in the array. Bucket sort beats all other sorting routines in time complexity. It should only be used when the range of input values is small compared with the number of values. In other words, occasions when there are a lot of repeated values in the input. Bucket sort works by counting the number of instances of each input value throughout the array. It then reconstructs the array from this auxiliary data. This implementation has a configurable input range, and will use the least amount of memory possible.

Advantages:

  • the user knows the range of the elements;
  • time complexity is good compared to other algorithms.

Disadvantages:

  • you are limited to having to know the greatest element;
  • extra memory is required;

Conclusion:

If you know the range of the elements, the bucket sort is quite good, with a time complexity of only O(n+k). At the same time, this is a major drawback, since it is a must to know the greatest elements. It is a distribution sort and a cousin of radix sort.

« « C Algorithms – Quick Sort
C Algorithms – Comb 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 – Bubble Sort

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

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

    September 14, 2011 - 0 Comment
  • 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 – Radix Sort

    September 10, 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 – 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 – Quick Sort

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

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