aFizyka logo

Algorytm sortowania kubełkowego

Algorytm sortowania kubełkowego ma złożoność czasową przebiegającą liniowo (O(n)). Dobrze pracuje na zbiorach z danymi, których elementy są rozłożone równomiernie. Koniecznym warunkiem poprawnego działania algorytmu jest podanie przewidywanego zakresu sortowanych danych. Nieposortowane dane są wstępnie układane w tak zwanych kubełkach przypisanych do zakresów wyznaczonych z podziału maksymalnej przewidywanej wartość ze zbioru podzielonej przez rozmiar zbioru.

Na przykład dla n liczb niewiększych niż 1 000 000 000 tworzy się kubełki według idei jak poniżej

i tak dalej

Po przypisaniu liczb do odpowiedniego kubełka, sortuje się tylko kubełki, które zawierają więcej niż jedną daną. Wynik końcowy jest wypisaniem danych z kolejnych kubełków. Algorytm zyskuje na czasie przez skrócenie operacji sortowania na dużo mniej licznych kubełkach.

Schemat algorytmu sortowania kubełkowego

Algorytm jest zapisany dla języka C#. Przez kubełki rozumiemy strukturę danych zawierająca listę, której rozmiar zmienia się w trakcie działania algorytmu. Wszystkie kubełki są przypisane do listy głównej (co zaobserwujesz w kodzie programu podanym pod koniec strony)

Schemat algorytmu sortowania kubełkowego Visual studio C#

Kod ciała funkcji sortującej algorytmem kubełkowym

Wskazówka:


void sortKubelkowy(Int32[] t,List<Kubelek> lis,int roz)
{
	//zkares kubełków ustaw na max liczbę podzieloną przez
	//ilośc liczb które będą sortowane
	int z = 1000000000 / roz;
	//przygotuj kubełki
	for (int i = 0; i < roz; i++) {
		Kubelek k = new Kubelek();
		k.t= new List<Int32>();
		lis.Add(k);
	}
	//przenies liczby do odpowiedniego kubełka
	for (int i = 0; i < roz; i++)
		lis[t[i] / z].t.Add(t[i]);
	//sortuj w kubełkach
	//gdy w kubełku są co najmniej 2 liczby
	for (int i = 0; i < roz; i++)
		if (lis[i].t.Count > 1) lis[i].t.Sort();
}

Przykładowa aplikacja wykorzystująca sortowanie kubełkowe

aplikacja wykorzystująca sortowanie kubełkowe Visual studio C#

Pełny kod klasy Form utworzonej formatki aplikacji sortującej algorytmem sortowania kubełkowego

Form1.cs:


using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
using static System.Windows.Forms.VisualStyles.VisualStyleElement;

namespace _15AlgSortKubelkowy
{
    struct Kubelek
    {
        public List<Int32> t;
    }
    public partial class Form1 : Form
    {
        //dane będa przechowywane w liście a nie w tablicy
        List<Kubelek> lista=new List<Kubelek>();
        int rozmiar;
 
        Int32[] tab;
        void losujTablice(Int32[] t, int zakres)
        {
            Random r = new Random();
            int i = 0;
            //mogą występować powtórzenia wylosowanych elementów
            while (i < t.Length)
            {
                t[i] = r.Next(zakres) + 1;
                i++;
            }
        }

        void sortKubelkowy(Int32[] t,List<Kubelek> lis,int roz)
        {
            //zkares kubełków ustaw na max liczbę podzieloną przez
            //ilośc liczb które będą sortowane
            int z = 1000000000 / roz;
            //przygotuj kubełki
            for (int i = 0; i < roz; i++) {
                Kubelek k = new Kubelek();
                k.t= new List<Int32>();
                lis.Add(k);
            }
            //przenies liczby do odpowiedniego kubełka
            for (int i = 0; i < roz; i++)
                lis[t[i] / z].t.Add(t[i]);
            //sortuj w kubełkach
            //gdy w kubełku są co najmniej 2 liczby
            for (int i = 0; i < roz; i++)
                if (lis[i].t.Count > 1) lis[i].t.Sort();
        }

        public Form1()
        {
            InitializeComponent();
        }

        private void button1_Click(object sender, EventArgs e)
        {
            //losowanie nowej tablicy
            if (textBox1.Text.Length < 1) return;
            //wyczysc stary zbiór
            lista.Clear();
            //ustaw nowy rozmiar
            rozmiar = int.Parse(textBox1.Text);
            if (tab != null) Array.Clear(tab, 0, tab.Length);
            tab = new int[rozmiar];
            //przy losowaniu ustaw zakres na 2 razy większy od rozmiaru
            losujTablice(tab, 2 * rozmiar);
            //pokaz wylosowany zbior
            textBox2.Clear();
            for (int i = 0; i < tab.Length; i++)
                textBox2.AppendText(tab[i].ToString() + Environment.NewLine);
        }

        private void textBox1_KeyPress(object sender, KeyPressEventArgs e)
        {
            if (e.KeyChar == 8) return;//wyskocz jak BackSpace
            if (e.KeyChar < '0' || e.KeyChar > '9') e.Handled = true;//ignoruj nienumeryczne
        }

        private void button2_Click(object sender, EventArgs e)
        {
            if (tab == null) return;
            sortKubelkowy(tab, lista, rozmiar);
            textBox3.Clear();
            //wypisz posortowany zbiór
            for (int i=0;i<rozmiar;i++)
              for(int j = 0; j < lista[i].t.Count;j++)
                    textBox3.AppendText(lista[i].t[j].ToString() + Environment.NewLine);
        }
    }
}