QuickSort по двойному связанному списку

Я хочу реализовать алгоритм QuickSort для синхронного двойного списка. Я предоставляю функции "разделять" левую и правую границу, затем начинает искать более низкие значения с левой стороны и класть большие с правой стороны. Это работает, потому что мой элемент-поворот всегда самый ранний, и после этого он находится посередине.

Я всегда получаю бесконечный цикл, и я не знаю почему? Может быть, неправильное условие прерывания?

Ее мой код:

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;
}


}

Ответы

Ответ 1

Просто из-за быстрого обезболивания кажется, что ваш список не только дважды связан, но также подключен к концам (так что он больше напоминает кольцо, чем список). Другими словами, если бы я перебирал ваш список (содержащий элементы A, B, C, D), это не было бы:

A -> B -> C -> D -> stop

Вместо этого было бы

A -> B -> C -> D -> A -> B -> C -> D -> A -> B ..... etc.

Я подозреваю, что это может быть причиной того, что у вас бесконечный цикл.

Я бы создал ссылку на последний элемент вашего списка в вашем классе DoublyLinkedList (пример: in.last), используйте его для получения последнего элемента и привяжите первый и последний элементы к null или какой-то NullListElement extends ListElement

Если вы должны сохранить его как кольцо, я все равно добавлю ссылку на последний элемент вашего списка, чтобы вы могли сказать что-то вроде:

if(walker == in.last) break; // stop

Ответ 2

Node partition(Node start, Node end){
    Node l = start;
    Node h = end.previous;
    Node pivot = end;

    if(end!=null && end.next!=start){ //Whenever deal with end.next, check null check
        while(h!=null && h.next!=l){//Whenever deal with end.next, check null check
            System.out.println("gumi");
            if(l.data<pivot.data)
                l=l.next;
            else if(h.data>pivot.data)
                h=h.previous;
            else{
                int temp = l.data;
                l.data = h.data;
                h.data = temp;
            }   
        }   
        int temp = pivot.data;
        pivot.data = l.data;
        l.data = temp;
    }
    return l;

}
void quicksort(Node start, Node end){
     System.out.println("jose");
   if(end!=null && end.next!=start ){ //Whenever deal with end.next, check null check , end should not be less than start: so the condition end.next!=start 
       System.out.println("Quixk");
       Node pivot = partition(start,end);
       quicksort(start, pivot.previous);
       quicksort(pivot.next, end);
   }

}

Ответ 3

Вот реализация для QuickSort с помощью класса DoublyLinkedList, который содержит ссылку на первый (in.first) ListElement, элемент списка содержит key и prev и next ссылки:

public DoublyLinkedList quicksort(DoublyLinkedList in, int numOfElements) {
    in.first = partition(in.first, in.first.prev);
    return in;
}

private ListElement partition(ListElement first, ListElement pivotElement) {
    ListElement left = first;
    ListElement right = pivotElement;

    while (left != pivotElement) {
        if (left.getKey() > pivotElement.getKey()) {
            ListElement next = left.next;
            if (left == first)
                first = next;
            //Remove currentLeft
            left.prev.next = left.next;
            left.next.prev = left.prev;

            //Connect with element after currentRight
            left.next = right.next;
            right.next.prev = left;

            //Connect with pivotElement
            left.prev = right;
            right.next = left;

            right = left; //Switch right with left, since we just swapped their positions
            left = next;  //Assign left to the next object (from the left part)
        } else {
            left = left.next;
        }
    }
    if (first != pivotElement.prev && first != pivotElement)
        first = partition(first, pivotElement.prev);
    if (pivotElement != right)
        partition(pivotElement.next, right);
    return first;
}

На момент написания этой статьи, когда я запускаю ее на своем настольном компьютере с очень недавним процессором Haswel, я получаю следующие результаты:

Quicksort:
1.000.000 Предметы: 696ms
8.300.000 Предметы: 8131мс

Обратите внимание, что это намного медленнее, чем моя реализация MergeSort для той же структуры данных, для которой я получаю следующие тайминги на одном и том же компьютер с одним и тем же входом:

Сортировка слиянием:
1.000.000 Предметы: 466ms
8.300.000 Предметы: 5144мс

Обратите внимание, что тайминги относятся к моему оборудованию, и вы можете получить разные результаты.