Сортировка списка

@Luzifer · Регистрация: 28.06.2010

Author24 — интернет-сервис помощи студентам

Народ нужна помощь

Элементы списка представлены следующим образом:

C++

class Node
{
public:
    char *name;
    Node *next;
    Node()
    {
        this->name = new char[255];
        this->next = NULL;
    }
    ~Node(){}
}

Поле name может достигать длинны 255 элементов (что собственно и видно).
Задача: реализовать быструю сортировку элементов списка. (понятно, что неполным перебором символов в полях name).
Признателен за любые мысли.

@Nick Alte · 26.05.2013, 12:33

Быструю сортировку как "сортировка за O(N*log N)" или быструю сортировку как "сортировка Хоара"?
В любом случае сортировка списков должна использовать высокую мобильность элементов списка, чтобы компенсировать последовательный доступ, что сразу наводит на мысль о сортировке слиянием (см. соответствующую статью в википедии). Для сравнения строк можно использовать функцию strcmp, она лишних тактов не украдёт.

@OhMyGodSoLong · 26.05.2013, 12:55

Связные списки сортируются мердж-сортом. Точка.

Квик-сорт и мердж-сорт основаны на одном и том же инварианте, просто заходят к проблеме с разных сторон.

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

Мердж-сорт требует больше лишней памяти на хранение частично отсортированных элементов, но существенная часть этой памяти уже есть в самих элементах связных списков, и это позволяет обойтись последовательным доступом к частично отсортированным кускам. Это отлично работает на связных списках, но ужасно для массивов, которые надо будет постоянно перемещать и перевыделять.

@Nick Alte 1675 / 1047 / 174 Регистрация: 27.09.2009 Сообщений: 1,945
	26.05.2013, 12:33	2
	Быструю сортировку как "сортировка за O(N*log N)" или быструю сортировку как "сортировка Хоара"? В любом случае сортировка списков должна использовать высокую мобильность элементов списка, чтобы компенсировать последовательный доступ, что сразу наводит на мысль о сортировке слиянием (см. соответствующую статью в википедии). Для сравнения строк можно использовать функцию strcmp, она лишних тактов не украдёт. 1

@OhMyGodSoLong ~ Эврика! ~ 1257 / 1006 / 74 Регистрация: 24.07.2012 Сообщений: 2,002
	26.05.2013, 12:55	3
	Связные списки сортируются мердж-сортом. Точка. Квик-сорт и мердж-сорт основаны на одном и том же инварианте, просто заходят к проблеме с разных сторон. Квик-сорт не требует O(N) памяти сверху и может работать in-place, но чтобы это использовать, необходим быстрый произвольный доступ к элементам. Это отлично подходит для сортировки массивов, но ужасно работает на списках, где доступ к произвольному элементу выполняется за O(N). Мердж-сорт требует больше лишней памяти на хранение частично отсортированных элементов, но существенная часть этой памяти уже есть в самих элементах связных списков, и это позволяет обойтись последовательным доступом к частично отсортированным кускам. Это отлично работает на связных списках, но ужасно для массивов, которые надо будет постоянно перемещать и перевыделять. 1