Как отсортировать двусвязный список SplDoublyLinkedList?

Question

[romajke]

Есть двусвязный список который мне нужно отсортировать за O(n Log n) время. Я бы хотел использовать merge sort, но я никак не могу сообразить, как это реализовать путём расширения класса SplDoublyLinkedList из стандартной библиотеки PHP.

Основная проблема в том, что я не могу разделить SplDoublyLinkedList пополам без выделения дополнительной памяти. Если бы я имел объекты отдельных нод, я бы легко мог установить указатель next ноды из середины списка на null, и сохранить указатель на следующую ноду в отдельную переменную, таким образом получив уже два связных списка. Но SplDoublyLinkedList не позволяет провернуть такую операци.
Я имею ввиду нечто подобное в Java:

node mergeSort(node h) 
    { 
        if (h == null || h.next == null) { 
            return h; 
        } 

        node middle = getMiddle(h); 
        node nextOfMiddle = middle.next; 

        middle.next = null; 

        node left = mergeSort(h); 
        node right = mergeSort(nextofmiddle); 

        node sortedlist = sortedMerge(left, right); 
        return sortedlist; 
    }

Должен ли я действительно использовать SplDoublyLinkedList в этом случае, или мне лучше написать свою собственую реализацию связного списка?

Comments

[Дмитрий]

https://www.php.net/manual/ru/spl.datastructures.php тут читали?

[romajke]

Дмитрий, читал. Но по сортировкам там ничего не нашёл :(

[Дмитрий]

romajke, пример гляньте https://www.php.net/manual/ru/class.splheap.php

Answer 1

[Руслан .]

Если нет возможности обращаться к элементу по индексу не выйдет уложиться в O(n Log n).
Т.к. по списку можно ходит только последовательно (перебирая все элементы до нужного), а не произвольно.
Может проще добавлять в список элементы так, чтобы они были отсортированы?

Comments

[romajke]

Нет не проще. Проще это будет только в том случае если бы нужно было поддерживать список отсоритрованным всегда. Мне же нужно лишь один раз по потребности отсортировать список. И merge Sort это делает как раз за O(n Log n)

Собственно вопрос в том, как бы реализовать это напрямую в SplDoublyLinkedList без выделения дополнительной памяти

[Wataru]

Руслан ., вы не правы. Не нужно случайного доступа, чтобы отсортировать за n log n. Та же сортировка слиянием делается так: проходим по списку один раз, чтобы значть его длину и найти середину. Разбиваем на 2 списка, сортируем каждый рекурсивно и потом сливаем два получившихся списка.

А еще можно quicksort сделать похоже - там не надо никакого случайного достпа - нужно 2 указателя, которые идут по списку с начала и с конца.

[Руслан .]

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

Также тут не только середины искать нужно, но и элемент который в середине (чтобы передать его в функцию рекурсивно), а это еще один проход.

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

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

Тут выходит O(n*n), а не n log n.

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

[Wataru]

Руслан ., Когда вы сортировку слияния делаете, вы же после рекурсивных вызовов делаете еще и слияние за O(n). Все, что добавляется теперь - еще одно O(n), которое, кстати, все-равно нужно, если структура данных не поддерживает актуальное количество элементов, доступное за константу (надо же подсчитать количесво элементов и найти середину).

Не важно сколько и чего вы добавите в функцию, покуда она делает O(n) операций, не считая рекурсивных вызовов, суммарная сложность будет O(n log n) по основной теореме.

> Кроме этого было требование сортировать на месте

Это же списки! Тут не надо выделять дополнительную память. Ну если вам так хочется, то пишите quicksort.

> quicksort заточен на работу с индексами

Квиксорту не нужен случайный досуп! Посмотрте на код из вики, например. Там тупо делается проход по массиву с конца. Индексы i и j всегда сдвигаются только на один соседний элемент и начинаются с начала или конца куска массива. Тут все отлично работает на списках. Если вы в функцию передадите 2 крайних элемента со ссылками вперед/назад, то все будет работать. Другое дело, что этот пхп-шный список похоже и это не поддерживает.

Т.е. лучше, конечно, использовать другую структуру данных. Или нормальный список или массив. Но если надо использовать этот спискок - то это тоже возможно и даже не сложно по коду.

Answer 2

[Wataru]

Немного через одно место получается, но раз уж вам надо на php, до еще и с SplDoublyLinkedList, то...

Вы можете вместо одной операции разбиения списка просто в цикле откусывать элемент с конца, с помощью pop и добавлять в другой список с помощью push.

На n log n сложность это не повлияет. Просто замедлит ровно в 1.5-2 раза, в зависимости от реализации merge.

Comments

[romajke]

Ну да, я думал о таком варианте, но это получается костыльно.
В таком случае проще наверное будет реализовать свой собственный связный список ?

[Wataru]

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