QuickSort na podwójnie powiązanej liście
Chcę zaimplementować algorytm QuickSort na synchronizowanej podwójnie powiązanej liście. Daję funkcji „partycja” lewą i prawą granicę, a następnie rozpoczyna wyszukiwanie niższych wartości po lewej stronie i umieszczanie większych po prawej stronie. Działa to, ponieważ mój element obrotu jest zawsze najbardziej pionowy i po tych krokach znajduje się w środku.
Zawsze dostaję nieskończoną pętlę i nie wiem dlaczego? Może zły warunek przerwania?
Jej mój kod:
private void quickSortRec(DoublyLinkedList in, ListElement l, ListElement r) {
ListElement pivot = partition(in, l, r);
if(pivot!=null && l!=r){
quickSortRec(in, in.first, pivot.prev);
quickSortRec(in, pivot.next, in.first.prev);
}
}
public ListElement partition(DoublyLinkedList in, ListElement l, ListElement r){
ListElement pivot = r;
ListElement walker = l;
if(l!=r){
while(walker != pivot){
if(walker.getKey() >= pivot.getKey()){
System.out.println(walker.getKey());
if(walker.prev == r){
l = walker.next;
r = walker;
}
else{
ListElement h1 = walker.prev;
ListElement h2 = walker.next;
h1.next = h2;
h2.prev = h1;
walker.prev = pivot;
walker.next = l;
pivot.next = walker;
l.prev = walker;
r = walker;
}
}
walker = walker.next;
}
if(l.prev == r)
in.first = l;
ListElement p = in.first;
do{
System.out.print(p.toString()+" ");
p = p.next;
}while(p != in.first);
System.out.println();
return pivot;
}
return null;
}
}