come da oggetto sto cercando di ordinare una lista semplice mediante algoritmo quicksort vi posto le classi non riesco a capire il problema
ecco come dovrebbe funzionare
-scelgo il pivot (scelgo il primo elemento della lista)
-creo due nodi (quelli <= del pivot e quelli > del pivot)
-alla fine fondo il tutto nodiminori + pivot + nodimaggiori
non ho applicato la ricorsione nel codice che ho postato in basso quindi dovrei avere in output solo il pivot e alla sua sinistra elementi minori o uguali ad esso e alla sua destra elementi maggiori (nota non ordinati) ma nemmeno questo sono riuscito ad ottenere
qualcuno mi dà una mano?
codice:
public class Nodo{
Object elemento;
Nodo next;
public Nodo(Object elemento,Nodo next) {
this.elemento=elemento;
this.next=next;
}
public Nodo (Object elemento) {
this.elemento=elemento;
this.next=null;
}
}
codice:
public class Lista{
private Nodo header;
private int size;
public Lista(){
size=0;
}
//ritorna header
public Nodo getHeader(){
return header;
}
//ritorna size
public int getSize(){
return size;
}
public void setHeader(Nodo h){
header=h;
}
public void setSize(int s){
size=s;
}
//aggiunge un elemento in testa alla lista
public void add(Object o){
if (size==0) {
header = new Nodo(o);
}
else {
Nodo nuovoNodo = new Nodo(o,header);
header = nuovoNodo;
}
size++;
}
//stampa gli elementi della lista
public void print(Nodo a){
if(size==0) System.out.println("Lista Vuota");
else { System.out.print(a.elemento + " ");
if(a.next!=null) print(a.next);
else System.out.println();
}
}
//conta la size della lista
public int contaSize(Nodo a){
if(a==null) return 0;
else return 1 + contaSize(a.next);
}
//ordina con quicksort
public void ordinaQuicksort(Nodo a){
if(a==null) return ;
else this.header = quickSort(a);
}
//QUICKSORT START
public Nodo quickSort (Nodo list1) {
if (list1 == null || list1.next == null)
return list1;
else {
Nodo pivot = choosePivot(list1);
Nodo y = minoriPivot(list1, pivot);
Nodo z = maggioriPivot(list1,pivot);
//devo restituire y + pivot + z
return unisciNodi(y, unisciPivotresto(pivot,z));
}
}
public Nodo choosePivot (Nodo list1) {
Nodo pivot = new Nodo (list1.elemento);
//scelgo per comodità il primo elemento
return pivot;
}
public Nodo minoriPivot (Nodo list1, Nodo p) {
if (list1 == null) return null;
if (list1.next == null) return list1;
if( ((Comparable)list1.elemento).compareTo((Comparable)p.elemento) <= 0 ) {
list1.next = minoriPivot(list1.next, p);
return list1;
}
else return minoriPivot (list1.next, p);
}
public Nodo maggioriPivot (Nodo list1, Nodo p) {
if (list1 == null) return null;
if (list1.next == null) return list1;
if( ((Comparable)list1.elemento).compareTo((Comparable)p.elemento) > 0 ) {
list1.next = maggioriPivot(list1.next, p);
return list1;
}
else return maggioriPivot (list1.next, p);
}
public static Nodo unisciNodi(Nodo a, Nodo b) {
if (a == null) return b;
if (b == null) return a;
a.next = unisciNodi (a.next, b);
return a;
}
public static Nodo unisciPivotresto(Nodo p, Nodo r) {
p.next=r;
return p;
}
//QUICKSORT END