Pages: [1]   Go Down
Print
Author Topic: codice quicksort  (Read 885 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Dario Catalano
docente
Apprendista Forumista
****
Offline Offline

Posts: 153


« on: 17-04-2015, 11:21:41 »

Code:
/*
Corso di Programmazione II (A-L), Prof. Dario Catalano

Esercizi su ordinamento

Esercizio 6: Implementazione del quicksort

*/

#include<iostream>
using namespace std;

void scambia (int& a, int& b)
{  
int aux=a;
a=b;
   b=aux;
}  

void Stampa (int a[], int n)
{
for (int i=0; i<n;i++)
cout << a[i] << " ";
cout << endl;  
}


void quicksort(int a[], int sinistra, int destra)
//Ordina a[sinistra:destra]
{
if (sinistra>= destra) return;
int i=sinistra; //Indice che parte da sinistra
int j=destra-1; //Indice che parte da destra
//Una posizione in meno per effettuare lo scambio
// con il pivot
int pivot = a[(destra+sinistra)/2];

//Spostiamo il pivot all'ultima posizione
scambia(a[destra],a[(destra+sinistra)/2]);
while (i<j) {
while ((a[i]<=pivot) && (i< destra)) i++;
while ((a[j]>pivot) && (j>=sinistra)) j--;
if (i<j)  
// Scambia solo se indice sinistro minore del destro
scambia(a[i],a[j]);
}
a[destra]=a[i]; //Rimettiamo a posto il pivot
/* Poiché i>j allora certamente a[i]>= pivot */
a[i]=pivot;

quicksort(a,sinistra,j);
quicksort(a,j+1,destra);
 
}

void quicksort(int a[], int n) //Ordina a[0:n-1]
{
quicksort(a, 0, n-1);
}

int main()
{ int n;

int a[20]={12,3,6,5,131,7,43,89,54,34,11,21,13,4,90,15,16,71,19,180};

cout << "Vettore iniziale \n";
Stampa(a,20);
quicksort(a,20);
cout << endl << "Vettore ordinato " << endl;
Stampa(a,20);

}

EDIT del mod.: si era perso del codice per via di alcuni costrutti del linguaggio che sono anche meta-tag del forum; inserito tag CODE
« Last Edit: 17-04-2015, 14:41:04 by ɹǝǝuıƃuǝsɹǝʌǝɹ » Logged
Pages: [1]   Go Up
Print
Jump to: