QuickSort na lista duplamente vinculada
Eu quero implementar o QuickSort Algorithm em uma lista dupla de sincronização sincronizada. Eu dou a função "partição" a borda esquerda e direita, então ele começa a procurar valores mais baixos no lado esquerdo e colocar os maiores no lado direito. Isso funciona porque meu elemento pivô é sempre o mais rightern e após este passo está no meio.
Eu sempre recebo um loop infinito e não sei porque? Talvez errado abortar condição?
O meu código:
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;
}
}