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
- [0, 100 000 000)
- [100 000 000, 200 000 000)
- [200 000 000, 300 000 000)
- [300 000 000, 400 000 000)
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)
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
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);
}
}
}
