базовый случай для рекурсивной быстрой сортировки в односвязном списке - PullRequest
Новая
       4

базовый случай для рекурсивной быстрой сортировки в односвязном списке

2 голосов
/ 31 марта 2011

Я пытаюсь разобраться с рекурсивной быстрой сортировкой в ​​односвязном списке.Каков базовый случай, и что мне нужно сделать, когда я его достигну, чтобы функция «перемотала» и напечатала отсортированный список?Вот некоторый код, но я думаю, что он отчаянно не прав ... 

public static void qSort(SLLNode first, SLLNode last)
{
    SLLNode pivot = first ;
    SLLNode head = pivot.succ ;
    if (first!=last)
    {   
        while (head!=null)
        {
            if (head.data.compareToIgnoreCase(pivot.data)<0)
            {
                pivot.succ = head.succ ;
                head.succ = first ;
                first = head ;
                qSort(first, pivot) ;
                qSort(head, last) ;
            }
            qSort(first, pivot) ;
            qSort(head, last) ;
            }
        }
}

Перефразируя мой вопрос: Когда я достигну базового варианта first==last, что мне нужно сделать? Как я могу сделать рекурсию перемотать и создать отсортированный список?

Вот мой обновленный код: 

public static void qSort(SLLNode first, SLLNode last)
    {
        if (first==last)
        {
            return ;
        }
        SLLNode pivot = first ;
        SLLNode head = pivot.succ ;

        while (head!=null)
        {
            if (head.data.compareToIgnoreCase(pivot.data)<0)
            {
                pivot.succ = head.succ ;
                head.succ = first ;
                first = head ;
                qSort(first, pivot) ;
                qSort(head, last) ;
            }
            qSort(first, pivot) ;
            qSort(head, last) ;
        }
    }

Ответы [ 5 ]

2 голосов
/ 31 марта 2011

Исследование Quicksort для связанного списка - полезная вещь. При изучении любого алгоритма важно понимать, что абсолютно необходимо.

В данном случае обнаруживается, что итераторы произвольного доступа не требуются. Действительно, итераторов вперед достаточно. Большая работа Степанова с STL состояла в том, чтобы отобрать такую ​​информацию.

Вот простая реализация на C ++. Извините за смену языка. Я просто меняю данные вместо указателей узлов. Выполнение последнего не имеет никакого отношения к быстрой сортировке.

И да, я знаю, что мой выбор элемента поворота может вызвать проблемы. Можно найти расстояние d между первым и последним, а затем выбрать случайное число x в диапазоне [0, d). Теперь переместите указатель, инициализированный на первые x раз, и поменяйте его местами данными, на которые указывает первый. 

struct Node
{
    Node(int d) : data(d), next(0) {}
    ~Node() { delete next; }
    Node* next;
    int data;
};

void Quicksort(Node* first, Node* last)
{
    if (first == last)
    {
        return;
    }

    Node* pivot = first;
    Node* boundary = first;
    for (Node* it = first->next; it != last; it = it->next)
    {
        // Invariant:
        // The iterators in the range [first, boundary->next) 
        // point to nodes with data less than the pivot
        // element's.
        // The iterators in the range [boundary->next, it) 
        // point to nodes with data greater or equal to 
        // the pivot element's.

        if (it->data < pivot->data)
        {
            // Swap the data to maintain the invariant
            boundary = boundary->next;
            std::swap(it->data, boundary->data);
        }
    }

    // Put the pivot data in its right place
    std::swap(pivot->data, boundary->data);

    Quicksort(first, boundary);
    Quicksort(boundary->next, last);
}

Первоначальный вызов будет выглядеть примерно так: 

Quicksort(head, 0);
2 голосов
/ 31 марта 2011

В общем

Для общего обзора быстрой сортировки вам, вероятно, следует рассмотреть алгоритм быстрой сортировки в Википедии .Короче говоря, проще, если вы используете вспомогательную функцию partition, чтобы привести свой список в состояние, когда все, что меньше, чем ваша точка вращения, находится слева от него, а все, что больше, чем точка вращения, находится справа от него.Затем вы вызываете быструю сортировку рекурсивно с обеих сторон оси.

EJP также имеет очень хорошую точку.Я не видел быстрой сортировки в связанном списке.

Давайте сделаем это в любом случае

Если бы я видел быструю сортировку со связанным списком, алгоритм был бы похож на 

def qsort(head, tail)
    if head == tail
        return
    pivot = tail
    current = head
    while current != pivot
        if current.value < pivot.value
            move/prepend current to head of the list
        else
            move/append current to tail of the list
        current = current.next
    qsort(head, pivot-1)
    qsort(pivot, tail)

Это немного сложно, потому что вы должны отслеживать pivot - 1, что не очень естественно делать с односвязным списком.Кроме того, приведенный выше алгоритм на самом деле не учитывает равные элементы.Но общая идея заключается в том, что в конечном итоге все, что меньше pivot, находится перед ним, и все, что больше, чем после, а затем вы снова вызываете qsort для обеих сторон.

Ваш код

Давайте разберем вашу программу с простым кейсом. 

A->B->C->D
F        L

Это наш старт.

SLLNode pivot = first ;
SLLNode head = pivot.succ ;

Дает нам 

A->B->C->D
F  H     L
P

Допустим, if (head.data.compareToIgnoreCase(pivot.data)<0) истинно для каждого элемента, учитывая текущее состояние списка.

Итак, мы вводим if Скажите, и сделайте 

pivot.succ = head.succ ;

A->C->D  B->C
F     L  H
P

head.succ = first ;

B->A->C->D
H  F     L
   P 

first = head ;

B->A->C->D
H  P     L
F

Это дает нам 

A->B->C->D
F  H     L
P

B->A->C->D  
H  P     L
F

Если у меня есть это право, то вызов 

qSort(head, last);

Должно быть вместо этого 

qSort(pivot, last);

То есть вы больше не будете звонить qSort по всему списку.Также может показаться, что вместо этого вы можете продолжать просматривать список до тех пор, пока все, что меньше, чем пивот, не окажется слева от него, перед рекурсивным вызовом qSort.

1 голос
/ 31 марта 2011

Концептуально, обратите внимание, что в базовом случае, когда first==last, у вас есть связанный список из одного элемента, и, таким образом, он уже отсортирован.

Я думаю, что ваш алгоритм может быть немного отключен ?.Вы хотите цикл, который перемещает все меньше, чем пивот, к первой половине, и все, что больше, ко второй половине.Затем (после завершения цикла!) Вы можете рекурсивно отсортировать половинки.Я вижу, что вы делаете это немного по-другому, но я не уверен, что это правильно ....

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

1 голос
/ 31 марта 2011

Вам не нужно «перематывать».Когда вы делаете рекурсивный вызов, он возвращается в стек рекурсии после завершения вызова.

if(first==last) return;

1 голос
/ 31 марта 2011

Базовым регистром является список из 0 или 1 элементов.

...