Programowanie i algorytmy

KONKURS FRAKTAL

fraktal

VII edycja konkursu programistycznego

FRAKTAL

8-9 kwietnia 2017

czytaj więcej

Sortowanie kubełkowe

powrót

Sortowanie kubełkowe jest algorytmem przeznaczonym dla pewnej specyficznej grupy danych. Jest podobnym algorytmem do sortowania przez zliczanie.  Algorytm jest wydajny w sytuacji, gdy dane rozmieszczone równomiernie. Nazwa wzięła się stąd, że dane wrzucamy do kubełków, które są już z definicji posortowane. 

Zalety

  • złożoność obliczeniowa jest rzędu {tex}O(n){/tex}
  • jest bardzo szybkim algorytmem dla pewnej grupy danych

Wady

  • dane powinny być równomiernie rozłożone
  • algorytm musi być dostosowany do danego typu danych
  • w niektórych sytuacjach trudny w implementacji

 

#include<iostream>
using namespace std;
 
void sortowanie_kubelkowe(int tab[], int n)
{
  //szukanie minimum i maksimum
  int Min = tab[0], Max = tab[0];
  for(int i=1;i<n;i++)
  {
    if(Min > tab[i]) Min = tab[i];
    if(Max < tab[i]) Max = tab[i];
  }
  if(Max - Min > 100000000)
  {
    cout<<"Ten algorytm sobie nie poradzi\n";
    return;
  }
  //tworzenie pomocniczej tablicy
  int *pom = new int [Max - Min + 1];
  //zerowanie tablicy pomocniczej
  for(int i=0;i<Max - Min + 1;i++) pom[i] = 0;
  //zliczanie wartosci
  for(int i=0;i<n;i++) ++pom[tab[i]-Min];
  //zapisywanie posortowanego zbioru do pierwotnej tablicy
  int k=0;
  for(int i=0;i<Max-Min+1;i++)while(pom[i]--)tab[k++]=i + Min;
 
  delete [] pom;
}
 
int main()
{
  int n, *tab;
  cin>>n;
  tab = new int [n+1];
  //wczytanie zbioru
  for(int i=0;i<n;i++) cin>>tab[i];
  //-------------------------------
  sortowanie_kubelkowe(tab, n);
  //-------------------------------
  //wypisanie zbioru
  for(int i=0;i<n;i++) cout<<tab[i]<<" ";
  delete [] tab;
  return 0;
}