Algorytm sortowania kubełkowego który sam dobiera ilość kubełków

Witam forumowiczów,

Mam takie zadanie do zrobienia - Dążę do zmodyfikowania sortowania kubełkowego tak jak w temacie, jednak to nie jest jedyny cel. Dodatkowo program z wyznaczoną automatycznie ilością kubełków ma działać średnio szybciej niż przy 10 statycznych kubełkach. Do tego celu mam wykorzystać losową próbkę elementów z tablicy.

Chciałem sprawdzić przy jakiej ilości kubełków program działa najwydajniej, więc dopisałem pętlę, która liczy czas algorytmu dla ilości kubełków od 1 do 2/n, gdzie n jest długością tablicy, a następnie wyniki sortuje i zapisuje w pliku.

No i teraz w zasadzie utknąłem. Wyniki są przeróżne, bo np. dla 10 kubełków działa to 15ms, dla 11 18ms, a dla 12 15ms. Nie mogę znaleźć powiązania, nie wiem jak to ugryźć i jak w tym miałaby pomóc wylosowana owa "próbka" elementów. Macie może jakieś pomysły? Poniżej kod:

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <fstream> //pliki
//Pomysl jest taki ze algorytm wstepnie losuje jakas probke z tablicy i na podstawie tej probki
// dobiera ilosc i rozmiary "kubelkow". Sprawdzic doswiadczalnie czy zastosowany algorytm jest
// srednio lepszy od poprzedniego. mozna w tym celu wypelniac tablice losowymi liczbami:
// tab[i]=rand()%zakres;
// tab[i]=rand()%(zakres/3)+rand()%(zakres/3)+rand()%(zakres/3);
// tab[i]=pow(rand()%pow(zakres,2)0.5);
using namespace std;

struct test //struktura stworzona na potrzeby wyznaczenia najkrotszych czasow dzialania algorytmu
{
    int kubek;
    double cz_alg;
};

struct node
{
    int num;
    node * next;
};

void push( int n, node *& h )
{
    node * temp = new node;
    temp->num = n;
    temp->next = h;
    h = temp;
}

int pop( node *& h )
{
    int res = h->num;
    node * temp = h;
    h = h->next;
    delete temp;
    return res;
}

void wstawianie( int * tab, int z )
{
    int tmp;
    int j;
    for( int i = 1; i < z; i++ ) //bo zakladamy ze 1 jest posortowany
    {
        j = i - 1;
        tmp = tab[ i ];
        while( j >= 0 && tab[ j ] > tmp ) //j jest licznikiem mniejszym od i - czyli pierwszym elementem 'posortowanej' czesci tablicy
        {
            tab[ j + 1 ] = tab[ j ];
            j--;
        }
        tab[ j + 1 ] = tmp;
    }
}

void wstawianie( test * tabb, int z ) //przeciazenie sortowania dla tablicy struktur "test"
{
    test tmp;
    int j;
    
    for( int i = 1; i < z; i++ ) //bo zakladamy ze 1 jest posortowany
    {
        j = i - 1;
        tmp = tabb[ i ];
        while( j >= 0 && tabb[ j ].cz_alg > tmp.cz_alg ) //j jest licznikiem mniejszym od i - czyli pierwszym elementem 'posortowanej' czesci tablicy
        {
            tabb[ j + 1 ] = tabb[ j ];
            j--;
        }
        tabb[ j + 1 ] = tmp;
    }
}

void BucketSort( int * tab, int n, int k ) //k to ilosc kubelkow
{
    node * kubelki[ k ];
    for( int i = 0; i < k; i++ )
         kubelki[ i ] = NULL;
    
    //idziemy wzdluz tablicy i wrzucamy liczby do odpowiednich kubelkow
    for( int i = 0; i < n; i++ )
    {
        push( tab[ i ], kubelki[ int( tab[ i ] /( 2000.0 / k ) ) ] );
    }
    
    //idziemy wzdluz tablicy kubelki i wrzucamy liczby ponownie do tablicy tab
    int z = 0; //int k=0;
    for( int i = 0; i < k; i++ )
    {
        while( kubelki[ i ] )
        {
            tab[ z++ ] = pop( kubelki[ i ] );
        }
        wstawianie( tab, n );
    }
}

int main()
{
    clock_t s, f; //zmienne do mierzenia czasu algorytmu
    double czas = 0;
    
    srand( time( 0 ) );
    int n = 4000;
    int * tab = new int[ n ];
    int * tab2 = new int[ n ]; //tablica pomocnicza w liczeniu wydajnosci algorytmu w zaleznosci od liczby kubelkow
    
    
    for( int i = 0; i < n; i++ )
         tab[ i ] =( rand() % 2000 ); //400+rand()%400+rand()%400+rand()%400+rand()%400);    //szansa na wylosowanie liczby blizej 2000 jest mniejsza
    
    for( int i = 0; i < n; i++ ) //pomocnicza tablica ma te same wartosci co glowna
         tab2[ i ] = tab[ i ];
    /////////////////////////zapisywania posortowanego zakresu liczb do pliku ////////////////////
    //wstawianie(tab,n);
    ofstream plik2; //Zapis wylosowanych liczb
    plik2.open( "liczby.txt" );
    for( int i = 0; i < n; i++ )
         plik2 << tab[ i ] << endl;
    
    plik2.close();
    //for(int i=0;i<n;i++)    //tablica glowna ponownie dostaje pierwotnie wylosowane wartosci
    //tab[i]=tab2[i];
    /////////////////////////zapisywania posortowanego zakresu liczb do pliku ////////////////////
    int ile = n / 2;
    test * tab_wyniki = new test[ ile - 1 ]; //tablica struktur
    
    for( int x = 1; x < ile; x++ ) //x<ile x<5
    {
        //  cout<<"X: "<<x<<endl;
        s = clock(); //zmienna zapisujaca czas przed rozpoczeciem algorytmu
        BucketSort( tab, n, x ); //ostatnia wartosc to ilosc kubelkow
        f = clock(); //zmienna zapisujaca czas po dzialaniu algorytmu
        
        
        //for(int i=0;i<n;i++)
        //    cout<<tab[i]<<"\t";
        
        czas =( double )( f - s ) /( double )( CLOCKS_PER_SEC ); //zwrocenie roznicy czasow w sekundach
        //cout<<"FUNKCJA! Kubelek: "<<x<<", Czas: "<<czas<<endl; //TESTESTESTESTESTESTESTESTESTEST
        tab_wyniki[ x - 1 ].kubek = x; //zapisywanie wynikow w tablicy struktur
        tab_wyniki[ x - 1 ].cz_alg = czas;
        
        for( int i = 0; i < n; i++ ) //tablica glowna ponownie dostaje pierwotnie wylosowane wartosci
             tab[ i ] = tab2[ i ];
        
    }
    
    wstawianie( tab_wyniki, ile - 1 ); //sortowanie tablicy wynikow    (tab_wyniki,ile-1) (tab_wyniki,4)
    
    ofstream plik; //Zapis czasow do pliku
    plik.open( "czasy.txt" );
    for( int i = 0; i < ile - 1; i++ )
         plik << "Kubelki: " << tab_wyniki[ i ].kubek << ", Czas: " << tab_wyniki[ i ].cz_alg << endl;
    
    plik.close();
    cout << "Koniec zapisu";
    delete[] tab_wyniki;
    delete[] tab;
    delete[] tab2;
    return 0;
}

Odswieżam