[C] modifica QuickSort per più pivot

[cristianpff]

ciao a tutti amici di html forum, sono alle prese con un progetto di informatica che mi chiede di modificare il QuickSort per farlo funzionare con k partizioni disgiunte; ossia se mi viene dato un array es : 5 2 4 6 1 3 e k=3
devo prendere k-1 pivot random es 4 e 5 ;
poi sistemare il vettore in modo da mettere x < 4 a sinistra, 4 ≤ x < 5 al centro, x ≥ 5 a destra otteniamo 3 2 1 4 6 5
e infine riordinare i sottoarray con chiamate ricorsive.
Mi viene dato il codice di partenza e io devo implementare la funzione Kpartition in modo che lavori con più pivot .
Non è che qualcuno mi da una dritta su come poterlo fare mi basta un consiglio per arrivare al ragionamento ; ad esempio avevo pensato di creare un array di k-1 elementi e di metterci dentro i pivot presi a random però c'è il problema che essendo una funzione ricorsiva il for mi va a ricreare ogni volta il vettore con pivot random diversi.

void KQUICKSORT(int* list,int k,int p, int r){
 int i=0;
    if(p<r)
	 {
		int *L = KPARTITION(list, k, p, r);
		 for(i=0;i<k;i++)
		 {
		   KQUICKSORT(list, k, L[i],L[i+1]-1);
		 }
	 }
   }

[Scara95]

Tieni i primi k-1 elementi, sposti tutti i valori più grandi del massimo alla fine, ci metti il massimo e poi prendi massimo dei rimasti e ripeti.

[cristianpff]

vediamo se ho capito cosa intendi, quando dici ti tenere i primi k-1 elementi quelli intendi che siano i pivot giusto ? poi prendo il massimo dei k-1 pivot e sposto tutti i valori più grandi di lui alla fine finito questo prendo i rimanenti pivot massimi e ripeto la procedura, giusto ?

[Scara95]

Esatto però finito di spostare o valori maggiori devo spostare anche il pivot

[cristianpff]

va bene ho capito, ora provo a implementarlo grazie per l'aiuto , un ultima domanda, dato che i k-1 pivot che devo prendere li devo prendere random va bene se faccio un array globale in cui li salvo? perchè se lo metto dentro la funzione partition ad ogni chiamata ricorsiva me lo ricrea con pivot diversi

[Scara95]

Non hai capito, non ti serve nient'altro a parte l'array da ordinare. Usi le prime celle come pivot. Se vuoi valori random altro non fai che scambiare i valori delle prime celle con valori di celle scelte a caso.

[cristianpff]

Esatto temo di non aver ben capito il ragionamento per strutturare la funzione partition , se guardi nel codice che ho postato a inizio discussione non capisco bene cosa fa la riga int *L =kpartition...
Mi potresti dare una dritta su come farla non chiedo il codice voglio solo capire come poterla fare ;ho riletto la tua risposta e sono d'accordo che non mi serve altro in piu oltre la lista da ordinare perche posso prendere di volta in volta i pivot random e sostituirli come hai detto tu.