быстрая сортировка в односвязном списке - PullRequest
Новая
       3

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

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

Моя быстрая сортировка не работает. Я особенно не уверен в том, что передать алгоритму разбиения и как управлять сводной точкой, поскольку в одном случае он становится узлом заголовка, а в другом - последним узлом. Я основал свой подход на решении для массивов. Вот моя попытка. Есть идеи? Обратите внимание, что алгоритм разделения был выбран в соответствии с однонаправленной природой односвязного списка (SLL). 

public static SLL quickSort(SLL list, SLLNode first, SLLNode last)
{
    if (first != null && last != null)
    {
        SLLNode p = partition(list, first, last) ;
        quickSort(list,first,p) ;
        quickSort(list,p.succ, last) ;
    }
    return list ;
}

public static SLLNode partition(SLL list, SLLNode first, SLLNode last)
{
    //last.succ = null ;
    SLLNode p = first ;
    SLLNode ptr = p.succ ;

    while (ptr!=null)
    {
        if (ptr.data.compareToIgnoreCase(p.data)<0)
        {
            String pivot = p.data ;
            p.data =  ptr.data ;
            ptr.data = p.succ.data ;
            p.succ.data = pivot ;
            p = p.succ ;
        }
        ptr = ptr.succ ;
    }
    return p ;
}

[EDIT]

  • Я хочу сделать это «на месте»

  • Я ищу помощи, конкретно о том, как управлять головой и последним в этом процессе.

  • Пожалуйста, не предлагайте альтернативы, если мой подход невозможен

Ответы [ 4 ]

1 голос
/ 16 мая 2014 
//logic - from left to right, remove smaller node and append at the beginning,
public void partition(int x)// x is your pivot element.
        {
            Node prev = null;
            Node cur = root;
            while (cur!=null)
            {
                if ( cur.data > x || cur == root)
                {
                    cur = cur.next;
                    prev = cur;
                }
                else
                {
                    Node next = cur.next;
                    if (prev != null) prev.next = next;
                    cur.next = root;
                    root = cur;
                    cur = next;
                }
            }
        }
1 голос
/ 29 марта 2011

Обычный подход для быстрой сортировки в связанных списках состоит в том, чтобы создать два (или лучше три, средний из которых является всеми элементами, равными элементу pivot) новых списков на этапе разделения, отсортировать первый и последний рекурсивно, а затем объединить их вместе.

Ваш код заменяет данные внутри узлов ... интересно. Я попробовал это со следующим (под) списком: 

        first                            last
        [ 5 ]-->[ 3 ]-->[ 7 ]-->[ 9 ]-->[ 2 ]

Посмотрите, что делает ваш алгоритм: 

        [ 5 ]-->[ 3 ]-->[ 7 ]-->[ 9 ]-->[ 2 ]
          p
                 ptr

3<5? (yes) {
pivot=5
        [ 3 ]-->[ 3 ]-->[ 7 ]-->[ 9 ]-->[ 2 ]
          p      ptr
        [ 3 ]-->[ 7 ]-->[ 7 ]-->[ 9 ]-->[ 2 ]
          p      ptr
        [ 3 ]-->[ 7 ]-->[ 5 ]-->[ 9 ]-->[ 2 ]
          p      ptr
        [ 3 ]-->[ 7 ]-->[ 5 ]-->[ 9 ]-->[ 2 ]
                  p
                 ptr
}
        [ 3 ]-->[ 7 ]-->[ 5 ]-->[ 9 ]-->[ 2 ]
                  p
                         ptr

Это состояние после первой итерации. Начиная с ptr != null, мы теперь переходим к следующей итерации, но я думаю, что вы уже здесь можете увидеть проблему. После следующей итерации это выглядит так: 

        [ 3 ]-->[ 5 ]-->[ 9 ]-->[ 7 ]-->[ 2 ]
                          p
                                 ptr

В следующей итерации перестановок не происходит: 

        [ 3 ]-->[ 5 ]-->[ 9 ]-->[ 7 ]-->[ 2 ]
                          p
                                         ptr

И теперь мы получим исключение NullPointerException, начиная с ptr.next == null (или если это подсписок из большего списка, мы бы поменялись местами за пределами).

Итак, некоторые идеи:

  • На шаге обмена вы должны убедиться, что впоследствии p указывает на узел, который теперь содержит элемент pivot.
  • вам следует остановиться при достижении элемента last и убедиться, что вы не поменялись местами после него (но все же сам элемент поменялся местами при необходимости).
0 голосов
/ 29 марта 2011

Для неразрушающей версии переведите следующий псевдокод на Java: 

quickSort list
    | list.isEmpty = empty list
    | otherwise = concat (quickSort lower) (new List(pivot, quickSort upper))
    where
         pivot = list.head
         lower = list of elements from list.tail that are < pivot
         upper = list of elements from list.tail that are >= pivot
0 голосов
/ 29 марта 2011

Возможно, вы захотите проверить строку "last.succ = null".Я думаю, что вы, возможно, захотите найти какой-то другой способ проверить, достигли ли вы конца сегмента списка, который вы разделяете.На самом деле, я думаю, вы должны получить исключение нулевого указателя, но я могу ошибаться.

...