Bucket Sort:

Like as Quick sort and insertion sort, there is another sort called Bucket sort. Bucket sort assumes that the input is drawn from a uniform distribution. Bucket sort runs in linear time on the average which is 0(n). It assumes that the input is generated by a random process that distributes elements uniformly over the interval [0, 1].

Bucket sort works as follows:

  •     Set up an array of initially empty buckets
  •     Go over the original array, putting each object in its bucket.
  •     Sort each non-empty bucket.
  •     Visit the buckets in order and put all elements back into the original array.
Suppose we need to sort an array of positive integers.
A= {3,4,11,0,2,8,5,9,1,5,6,2,8,0,2,4,1,3,10,4,7,9}.
A bucket sort works as follows: create an array of size 11. Then, go through the input array and place integer 3 into a second array at index 3, integer 11 at index 11 and so on. We will end up with a sorted list in the second array.
We start with an array of 11 counters set to zero.

Array A:


Moving through the array we increment counters:

Array B:


Next, we simply read off the number of each occurrence :

0,0,1,1,2,2,2,3,3,4,4,4,5,5,6,7,8,8,9,9,10,11

The code of Bucket sort in C is given below:


Output:

Output Screen
We can say Bucket sort is asymptotically fast (O(n) when distribution is uniform) . It is a simple to code and good for a rough sort.

Related post :

Radix sort algorithm                                                    Bubble sort in java 

Topological sort of directed graph in java                 Binary search  in C

Binary search in java                                                   Breadth First Search(BFS)

Depth First Search ( DFS )

For More Algorithm like Bucket Sort algorithm, click here.

Radix sort in an intuitive non-comparative integer title sorting algorithm Radix sort puts the elements in order by comparing the individual digits of the numbers which share the same significant position and value. Radix sort processes the digits either by Least Significant Digit (LSD) method or by Most Significant Digit (MSD) method.

The algorithm of Radix sort follows the following pattern :

Let's try to print some of the following pattern in java:

We can play with * and print them in many ways, many style. Let's see some awesome pattern of stars and try to do this by computer.
At first try yourself, then go to see code.
Pattern 1:

Code for this above pattern in Java.                                      Code for this above pattern in C.

MARI themes

Powered by Blogger.