Pages: [1]   Go Down
Print
Author Topic: QuickSort  (Read 943 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
andreacannella
Administrator
Forumista Esperto
*****
Offline Offline

Gender: Male
Posts: 1.488


Andea Cannella - www.andreacannella.com


WWW
« on: 06-12-2009, 15:41:41 »

Ho provato a riscrivere il codice  fornito dal prof nelle sue slides per implementare il quicksort, ma testandolo non ordina l'array.

Il codice è identico a quello presente nelle slides, a parte il metodo swap che l'ho implementato evitando l'uso di una variabile temporanea.

Ringrazio quanti sapranno "illuminarmi".

Segue il codice...

Code:
public class QuickSort{
public static void QuickSort(int [] a){
QuickSort(a, 0, a.length-1);
}
public static void QuickSort(int [] a, int first, int last){
if(first>=last)
return;
int m= partition(a, first, last);
QuickSort(a, first, m-1);
QuickSort(a, m+1, last);
}

public static int partition(int [] a, int first, int last){
int lower= first;
int upper= last+1;
int pos=(int)(Math.floor((last-first+1)*Math.random()));
int pivot = a[pos];
swap(a, pos, first);
while(true){
do{
lower++;
}
while(lower<=last && a[lower]<=pivot);
do{
upper--;
}
while(a[upper]>pivot);
if (lower<upper){
swap(a, lower, upper);
}
else break;
}
swap (a, first, upper);
return upper;

}

public static void swap (int [] array, int a, int b){
array[a]=array[a]+array[b];
array[b]=array[a]-array[b];
array[a]=array[a]-array[b];
}


public static void main (String [] args){

int [] a =new int[10];
for (int i=0; i<a.length-1; i++){
a[i]=(int)(Math.random()*100);
System.out.println(a[i]);
}
System.out.println();
QuickSort(a);
for (int j=0; j<a.length-1; j++)
System.out.println(a[j]);




}










}

Saluti

 ciao ciao

Andrea
Logged

Le tre grandi virtù di un programmatore: pigrizia, impazienza e arroganza. (Larry Wall)

Good times for a change
See, the luck I've had
Can make a good man
Turn bad

So please, please, please
Let me, let me, let me
Let me get what I want
This time

The Smiths
andreacannella
Administrator
Forumista Esperto
*****
Offline Offline

Gender: Male
Posts: 1.488


Andea Cannella - www.andreacannella.com


WWW
« Reply #1 on: 16-12-2009, 00:18:15 »

Code:
public class QuickSort{
public static void QuickSort(int [] a){
QuickSort(a, 0, a.length-1);
}
public static void QuickSort(int [] a, int first, int last){
if(first>=last)
return;
int m= partition(a, first, last);
QuickSort(a, first, m-1);
QuickSort(a, m+1, last);
}

public static int partition(int [] a, int first, int last){
int lower= first;
int upper= last+1;
int pos=first+(int)(Math.floor((last-first+1)*Math.random()));
int pivot = a[pos];
swap(a, pos, first);
while(true){
do{
lower++;
}
while(lower<=last && a[lower]<=pivot);
do{
upper--;
}
while(a[upper]>pivot);
if (lower<upper){
swap(a, lower, upper);
}
else break;
}
swap (a, first, upper);
return upper;

}

public static void swap (int [] array, int a, int b){
/*array[a]=array[a]+array[b];
array[b]=array[a]-array[b];
array[a]=array[a]-array[b];
*/
int tmp=array[a];
array[a]=array[b];
array[b]=tmp;
}


public static void main (String [] args){

int [] a =new int[10];
for (int i=0; i<a.length; i++){
a[i]=(int)(Math.random()*100);
System.out.println(a[i]);
}
System.out.println();
QuickSort(a);
for (int j=0; j<a.length; j++)
System.out.println(a[j]);




}










}

Ora è funzionante.

Saluti

 ciao ciao

Andrea
Logged

Le tre grandi virtù di un programmatore: pigrizia, impazienza e arroganza. (Larry Wall)

Good times for a change
See, the luck I've had
Can make a good man
Turn bad

So please, please, please
Let me, let me, let me
Let me get what I want
This time

The Smiths
andreacannella
Administrator
Forumista Esperto
*****
Offline Offline

Gender: Male
Posts: 1.488


Andea Cannella - www.andreacannella.com


WWW
« Reply #2 on: 16-12-2009, 00:29:21 »

L'errore stava nel lavorare sugli indici dell'array anziché sul contenuto.

Scusate per la "baggianata" scritta.
 testate testate

Saluti

 ciao ciao

Andrea
Logged

Le tre grandi virtù di un programmatore: pigrizia, impazienza e arroganza. (Larry Wall)

Good times for a change
See, the luck I've had
Can make a good man
Turn bad

So please, please, please
Let me, let me, let me
Let me get what I want
This time

The Smiths
Giovi89
Apprendista Forumista
**
Offline Offline

Posts: 273


« Reply #3 on: 16-12-2009, 12:46:01 »

Ti volevo chiedere una cosa ma il quicksort che hai scritto ordina l'array in maniera crescente? se io volessi ordinare gli elementi in maniera decrescente cosa devo modificare?
Grazie per una tua risposta.
Logged
andreacannella
Administrator
Forumista Esperto
*****
Offline Offline

Gender: Male
Posts: 1.488


Andea Cannella - www.andreacannella.com


WWW
« Reply #4 on: 16-12-2009, 16:30:12 »

Ti volevo chiedere una cosa ma il quicksort che hai scritto ordina l'array in maniera crescente? se io volessi ordinare gli elementi in maniera decrescente cosa devo modificare?
Grazie per una tua risposta.

Sì ordina in maniera crescente.

Per farlo in maniera decrescente devi scambiare i puntatori e le condizioni all'interno del partition.

Oppure se non guardi alla complessità, basta scambiare tutti i puntatori dell'array appena creato con complessità O(n) in quanto basta solo scorrere una volta l'array.
Logged

Le tre grandi virtù di un programmatore: pigrizia, impazienza e arroganza. (Larry Wall)

Good times for a change
See, the luck I've had
Can make a good man
Turn bad

So please, please, please
Let me, let me, let me
Let me get what I want
This time

The Smiths
Pages: [1]   Go Up
Print
Jump to: