Я хочу реализовать алгоритм быстрой сортировки в двусвязном списке синхронизации. Я даю функции "разделить" левую и правую границу, затем она начинает искать более низкие значения с левой стороны и помещать большие с правой стороны. Это работает, потому что мой элемент поворота всегда самый правый, а после этих шагов он находится посередине.
Я всегда получаю бесконечный цикл, и я не знаю почему? Может быть неправильное условие прерывания?
Ее мой код:
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;
}
}
