[Algoritmi] QuickSort Randominzzato

[creative88]

Buonasera,

avrei bisogno di un piccolo aiuto con il seguente esercizio:

LVQuickSort

Fissati alcuni valori abbastanza grandi per $|S| = n $(tipo $n = 10^4$ e $n = 10^6$)

1. conta il numero Nj di confronti effettuati in ogni singolo run j per ordinare la sequenza S e
produci un istogramma con i valori ottenuti per $R = 10^4$
run

2. giustifica la scelta del numero di bin dell’istogramma osservando come cambia la visualizzazione se il numero e troppo piccolo o troppo grande

3. stima il valore della costante C sapendo che $1/R$ \(\displaystyle \sum\limits_{j=1}^R Nj \) \(\displaystyle \approx \) $C n ln n$

Ho implementato l'algoritmo nel seguente modo:

#include<iostream>
#include<cstdlib>
#include<ctime>
#include <fstream>

using namespace std;
int PARTITION(int [],int ,int );
void R_QUICKSORT(int [],int ,int );
int R_PARTITION(int [],int,int );
int IntCasuale(int,int); // 2 parametri per scegliere minimo e massimo, 1 valore intero da restituire
int confronti=0;

int main()
{
srand (time(NULL));	
    int n=10000; 
    int nRun=10000;

    int a[n];
    for(int i=0;i<n;i++)
    {
        a[i]=IntCasuale(1,100000);  //inizializzazione dell'array da ordinare con valori a caso nel range [1-10^5]
    }
  
    std::ofstream outfile;
    
    int run[nRun];
    int min=0;
    int max=0;
    int b[n];
    
    for (int s=0; s<nRun; s++) 
	{
		int p=0,r=n;
		confronti=0;
		
			for (int k=0; k<n; k++)
			{
				b[k]=a[k];   /*Ricopio L'arrey in un nuovo array di modo da poter ripartire al prossimo run con lo stesso array di partenza altrimenti ricomincerei con un array già ordinato*/
			}

		R_QUICKSORT(b,p,r);
		run[s]=confronti;
		
	 	if(s==0)
	 	{
	 		min=confronti;   /*inizializzo alla prima iterazione massimo e minimo con il risultato dei confronti fatti al primo run*/
	 		max=confronti;
		
		}
		if (confronti<min)
		{
			min=confronti;  //determino il ninimo dei confronti
		
		}
		if(confronti>max)
		{
			max=confronti; //determino il massimo dei confronti
		
		}
		
	        outfile.open("valori.txt", std::ios_base::app); // append instead of overwrite
  		outfile <<s<<";"<<run[s]<<"\n";  /*produco un file di testo con tutte le coppie Run,Numero di confronti*/
		outfile.close();
	}

   cout<<"Il numero massimo di confronti Nj è:"<<max<<endl;
   cout<<"Il numero minimo di confronti Nj è:"<<min<<endl;

	system("PAUSE");
	return 0;
     
}

void R_QUICKSORT(int a[],int p,int r)
    {
        int q;
        if(p<r)
        {
         q=R_PARTITION(a,p,r);
         R_QUICKSORT(a,p,q-1);
         R_QUICKSORT(a,q+1,r);
        }
    }

 int R_PARTITION(int a[],int p,int r)
 {
        int i=p+rand()%(r-p+1);
        int temp;
        temp=a[r];
        a[r]=a[i];
        a[i]=temp;
        return PARTITION(a,p,r);
  }

 int PARTITION(int a[],int p,int r)
 {
        int temp,temp1;
        int x=a[r];
        int i=p-1;
        for(int j=p;j<=r-1;j++)
        {
            if(a[j]<=x)
            {
		confronti++;
                i=i+1;
                temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
        temp1=a[i+1];
        a[i+1]=a[r];
        a[r]=temp1;
        return i+1;
  }
  
  int IntCasuale(int minimo,int massimo)
{ // restituisco il valore non appena esso viene generato

return rand()%(massimo-minimo+1)+minimo;
}

Le mie perplessità sono essenzialmente due:

1)Volendo creare un istogramma con le coppie ottenute in output sul file di testo valori.txt basta inserire sull'ascissa il numero del run e sull'ordinata del grafico il numero di confronti ottenuti? in tal caso come posso variare il bin?
2)Nella stima della Costante C bisogna risolvere il problema utilizando il valore medio dei confronti rilevati attraverso l'algoritmo oppure procedere alla risoluzione matematica del problema in maniera piu generale?

Sperando di essere stato chiaro confido nel vostro aiuto.

[apatriarca]

1. Per creare un istogramma devi suddividere l'intervallo di input in intervalli di una certa ampiezza e quindi inserire ogni valore nell'intervallo corrispondente. In pratica avrai un array in cui ogni valore corrisponde ad un tuo bin/bucket/sotto-intervallo inizializzato a zero. Ogni volta che leggi un valore in un determinato intervallo incrementerai il valore corrispondente. Alla fine visualizzerai un grafico a barre con questi valori.

2. Suppongo che l'idea sia solo di calcolare
\[ C \approx \frac{\sum_{j=1}^{R} N_j}{R\,n\,\log\,n} \]