Bucket Sort

Aspecte teoretice:

Ipoteză: Elementele a[i] sunt distribuite uniform peste intervalul [0,1).

Principiul este următorul:

• se divide intervalul [0,1) în n subintervale de mărimi egale, numerotate de la 0 la n−1;
• se distribuie elementele a[i] în intervalul corespunzător: n·a[i];
• se sortează fiecare pachet folosind o altă metodă;
• se combină cele n pachete într-o listă sortată.

Analiza complexității:

Cazul nefavorabil: O(N^2)
Cazul mediu: O(k+n)
Cazul favorabil: O(k+n)

Exemplu Pas cu Pas:

Implementare:

Cod Sursa C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace BucketSortCS
{
	class Program
	{
		static void BucketSort(int[] v, int n)
		{
			int[] buckets = new int[20];
			int i,j,k;
			for (j=0; j<20; ++j)
				buckets[j]=0;
			for (i=0; i<n; ++i)
				++buckets[v[i]];
			for (i=0 , j=0 ; j<20; ++j)
				for (k=buckets[j];k>0; --k)
					v[i++]=j;
		}
 
		static void Main(string[] args)
		{
			int[] v = new int[20];
			int i, len;
			Console.Write("Dati numarul de elemente n: ");
			len = Convert.ToInt32(Console.ReadLine());
			for (i = 0; i < len; i++)
			{
				Console.Write("v[" + i + "]=");
				v[i] = Convert.ToInt32(Console.ReadLine());
			}
			BucketSort(v, len);
			for (i = 0; i < len; i++)
				Console.Write(v[i] + " ");
			Console.ReadLine();
		}
	}
}

Cod Sursa C++

// BucketSortCPP.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <iostream>
#include <conio.h>
 
using namespace std;
 
int v[20];
 
void BucketSort (int v[] , int n)
{
	int buckets[20];
	int i,j,k;
	for (j=0; j<20; ++j)
		buckets[j]=0;
	for (i=0; i<n; ++i)
		++buckets[v[i]];
	for (i=0 , j=0 ; j<20; ++j)
		for (k=buckets[j];k>0; --k)
			v[i++]=j;
}
 
int main(void)
{
	int i;
	int len;
	cout<<"Dati numarul de elemente din vector: ";
	cin>>len;
	for (i=0; i<len; i++)
	{
		cout<<"v["<<i<<"]=";
		cin>>v[i];
	}
	BucketSort(v, len);
	for (i=0; i<len; i++)
		cout<<v[i]<<" ";
	system("pause");
}

Cod Sursa PHP

<?php

 
//license under the MIT https://goo.gl/JNRTRM
function bucket_sort($my_array) {
    $n = sizeof($my_array);
    $buckets = array();
    // Initialize the buckets.
    for ($i = 0; $i < $n; $i++) {
        $buckets[$i] = array();
    }
    // Put each element into matched bucket.
    foreach ($my_array as $el) {
        array_push($buckets[ceil($el/10)], $el);
    }
    // Sort elements in each bucket using insertion sort. 
    $j = 0;
    for ($i = 0; $i < $n; $i++)
    {
        // sort only non-empty bucket
        if (!empty($buckets[$i])) {
            insertion_sort($buckets[$i]);
            // Move sorted elements in the bucket into original array.
            foreach ($buckets[$i] as $el) {
                $my_array[$j++] = $el;
            }
        }
    }
    return $my_array;
}
 
function insertion_sort($my_array, $fn = 'comparison_function') {
    if (!is_array($my_array) || !is_callable($fn)) return;
    for ($i = 1; $i < sizeof($my_array); $i++) {
        $key = $my_array[$i]; 
        // This will be $a in comparison function.
        // $key will be the right side element that will be
        // compared against the left sorted elements. For
        // min to max sort, $key should be higher than
        // $elements[0] to $elements[$j] 
        $j = $i - 1; // this will be in $b in comparison function
        while ( $j >= 0 && $fn($key, $my_array[$j]) ) {
            $my_array[$j + 1] = $my_array[$j];
            $j = $j - 1; // shift right
        }
        $my_array[$j + 1] = $key;
    }
}
 
//Following function used to compare each element.
function comparison_function($a, $b) {
    return $a < $b;
}
 
$test_array = array(3, 0, 2, 5, -1, 4, 1);
echo "Vector original :\n";
echo implode(', ',$test_array );
echo "\nVector Sortat :\n";
echo implode(', ',bucket_sort($test_array)). PHP_EOL;
sleep(10);
?>

Cod Sursa Java

//Complexitate: Nefavorabil: O(n^2); Mediu: O(k+n); Favorabil: O(k+n)class BucketSortJAVA {   public static void BucketSort(int[] v, int n)         {             int[] buckets = new int[20];           int i,j,k;           for (j=0; j<20; ++j)             buckets[j]=0;           for (i=0; i<n; ++I)             ++buckets[v[i]];           for (i=0 , j=0 ; j<20; ++j)             for (k=buckets[j];k>0; –k)               v[i++]=j;         }    public static void main(String args[])   {     int a[]={7,4,5,3,1,8,9,2,6,0};     int i;     BucketSort(a,10);     for (i=0;i<10;i++)     System.out.println(a[i]+” “);   } }

Rezultat: