Bucket sort

Bucket Sort is a sorting method that subdivides the given data into various buckets depending on certain characteristic order, thus partially sorting them in the first go.
Then depending on the number of entities in each bucket, it employs either bucket sort again or some other ad hoc sort.



Algorithm of Bucket-SORT


BUCKET SORT (A)

1. n ← length [A]

2. For i = 1 to n do

3. Insert A[i] into list B[A[i]/b] where b is the bucket size

4. For i = 0 to n-1 do

5. Sort list B with Insertion sort

6. Concatenate the lists B[0], B[1], . . B[n-1] together in order.

Assumptions :




c Fuction for BUCKET SORT


void Bucket_Sort(int array[], int n)

{

	int i, j;

	int count[n];

	for(i=0; i < n; i++)

	{

		count[i] = 0;

	}

	for(i=0; i < n; i++)

	{

		(count[array[i]])++;

	}

	for(i=0,j=0; i < n; i++)

	{

		for(; count[i]>0;(count[i])--)

		{

			array[j++] = i;

		}

	}

}




Implementation of BUCKET SORT


#include<stdio.h>

#include<conio.h>

void Bucket_Sort(int array[], int n)

{

	int i, j;

	int count[n];

	for(i=0; i < n; i++)

	{

		count[i] = 0;

	}

	for(i=0; i < n; i++)

	{

		(count[array[i]])++;

	}

	for(i=0,j=0; i < n; i++)

	{

		for(; count[i]>0;(count[i])--)

		{

			array[j++] = i;

		}

	}

}

int main()

{

	int array[100];

	int n,i;

	clrscr();

	printf("Enter How many Numbers : ");

	scanf("%d",&n);

	printf("Enter the %d elements to be sorted:\n",n);

	for(i = 0; i < n; i++ )

	{

		scanf("%d",&array[i]);

	}

	printf("\nThe array of elements before sorting : \n");

	for (i = 0;i < n;i++)

	{

		printf("%d ", array[i]);

	}

	printf("\nThe array of elements after sorting : \n");

	Bucket_Sort(array, n);

	for (i = 0;i < n;i++)

	{

		printf("%d ", array[i]);

	}

	printf("\n");

	return 0;

}






Analysis Of Radix sort

Class Sorting algoritdm
Data structure Array
Worst case performance O(n^2)
Average case performance O(n+k)
Worst case space complexity O(n.K)



Quantitative Aptitude
Reasoning
Programming
Interview