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

struct NODE
{
 int num;
 struct NODE * next, * prev;
}

примечание: синтаксис языка Си

void ListSort(struct NODE * first)
{
    struct NODE *temp, *min, *search = first;
    while(search != 0)
    {
        temp = search;
        min = search;
        while(temp != 0)
        {
            if(temp->num < min->num)
                min = temp;
            temp = temp->next;
        }
        temp = search->next;
        if(search == first)
        {
            if(min == search->next)
            {
                first = min;
                if(min->next != 0)
                    min->next->prev = search;
                min->prev = 0;
                search->prev = min;
                search->next = min->next;
                min->next = search;
            }
            else if(search != min)
            {
                first = min;
                if(min->next != 0)
                    min->next->prev = min->prev;
                search->next = min->next;
                min->next = search;
                min->prev = search->prev;
                search->prev = min;
            }
        }
        else if(min == search->next)
        {
            search->prev->next = min;
            min->prev = search->prev;
            if(min->next)
                min->next->prev = search;
            search->prev = min;
            search->next = min->next;
            min->next = search;
        }
        else if(search != min)
        {
            search->prev->next = min;
            if(min->next)
                min->next->prev = min->prev;
            search->next = min->next;
            min->next = search;
            min->prev = search->prev;
            search->prev = min;
        }
        search = temp;
    }
}

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

Здравствуйте, boxter, Вы писали:

B>Помогите, пожалуйста.
B>Поставлена задача отсортировать линейный список, состоящий из структуры

Попробуй выделить примитивные операции над элементами списка: вставка, расщепление, и т.п.
А там, глядишь, и остальное станет понятно

какие способы сортировки можно выделить
мне нужны алгоритмы сортировки массивов
а по ним можно отсортировать и линейный список
сортировка производится путем изменения ссылок у элементов (next и prev)

boxter wrote:

> какие способы сортировки можно выделить

insertion sort, selection sort, buble sort, Shell sort, quick sort, heap sort, merge sort...

См. http://en.wikipedia.org/wiki/Sort_algorithm

> мне нужны алгоритмы сортировки массивов

Для массивов чаще используют quick sort, так как он имеет среднюю сложность O(n * log^2(n)) и не требует дополнительной памяти, но требует произвольного доступа к элементам, поэтому для списков он крайне неэффективен.

> а по ним можно отсортировать и линейный список

Для списков тебе нужен merge sort (вбей в google) — этот алгоритм не требует произвольного доступа к сортируемой последовательности (как, к примеру, quick sort) и поэтому идеально подходит для списков, но требует дополнительной памяти.

http://en.wikipedia.org/wiki/Merge_sort
http://linux.wku.edu/~lamonml/algor/sort/merge.html

> сортировка производится путем изменения ссылок у элементов (next и prev)

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

--
Maxim Yegorushkin

Здравствуйте, boxter, Вы писали:

Вот написал в качастве разминки... Сложность n*log(n) надо памяти log(n) (как QuickSort'у) но данная реализация просто ваделяет памяти под список максимум из 2^32 элементов...(512 байт)

примечание: синтаксис языка С++(думаю на С перевести сможешь сам)
Для двусвязного списка алгоритм будет тотже самый НО придется сделать еще один проход для того чтобы сделать валидными указатели на предыдущие элементы.
Поддерживать список в валидном состоянии во время сортировки я посчитал не нужным. Ибо ничего кроме потери производительности это не даст.

#include "stdafx.h"

template<class T>
struct node
{
    T value;
    node* next;
};
struct node_less
{
    template<class T>
    bool operator()(node<T>* l, node<T>* r)const
    {
        return l->value < r->value;
    }
};

template<class T, class Less>
node<T>* merge_list(node<T>* list1, node<T>* list2, Less less)
{
    node<T>* list;
    node<T>* list_res;
    if(less(list1, list2))
    {
        list_res = list1;
        goto list1_pop;
    }
    else
    {
        list_res = list2;
        goto list2_pop;
    }
    while(true)
    {
        if(less(list1, list2))
        {
            list->next = list1;
list1_pop:
            list = list1;
            list1 = list1->next;
            if(list1 == 0)
            {
                list->next = list2;
                return list_res;
            }
        }
        else
        {
            list->next = list2;
list2_pop:
            list = list2;
            list2 = list2->next;
            if(list2 == 0)
            {
                list->next = list1;
                return list_res;
            }
        }
    }
}
template<class T, class Less>
node<T>* list_sort(node<T>* list, Less less)
{
    const int max_stack = 32;
    struct stack_frame
    {
        int n;
        node<T>* list;
    };
    stack_frame stack[max_stack];
    stack[0].n = 1;
    stack[0].list = list;
    list = list->next;
    stack[0].list->next = 0;
    int top = 0;
    while(list != 0)
    {
        ++top;
        stack[top].n = 1;
        stack[top].list = list;
        list = list->next;
        stack[top].list->next = 0;
        while(top > 0 && stack[top].n == stack[top - 1].n)
        {
            --top;
            stack[top].n *= 2;
            stack[top].list = merge_list(stack[top].list, stack[top + 1].list, less);
        }
    }
    while(top > 0)
    {
        --top;
        stack[top].list = merge_list(stack[top].list, stack[top + 1].list, less);
    }
    return stack[0].list;
}
template<class T>
void print_list(node<T>* list)
{
    while(list != 0)
    {
        std::cout << list->value << " ";
        list = list->next;
    }
    std::cout << "\n\n";
}
int main()
{
    int count = 10;
    std::vector<node<int> > list(count);
    for(int i = 0; i < count - 1; ++i)
    {
        list[i].value = rand() % 333;
        list[i].next = &list[i + 1];
    }
    list[count - 1].value = rand() % 333;
    list[count - 1].next = 0;
    print_list(&list[0]);
    node<int>* top = list_sort(&list[0], node_less());
    print_list(top);
    return 0;
}

ЗЫ Я посчитал что goto лучше чем copy-paste. Болие того оптимизатор VC++7.1 со мной согласился...
ЗЗЫ less не должен бросать исключений... иначе

Здравствуйте, WolfHound, Вы писали:

А сортировочка получилась зверская. Соложность у нее O*N*log2(N). Причем на случайных последовательностях O чуть меньше 1, а на упорядочиных падает почти до 0.5 Что и ожидалось учитывая как я реализовал merge_list

WolfHound wrote:

> А сортировочка получилась зверская. Соложность у нее O*N*log2(N). Причем на случайных последовательностях O чуть меньше 1, а на упорядочиных падает почти до 0.5 Что и ожидалось учитывая как я реализовал merge_list

Что это за метод сортировки?

P.S. классический merge sort не чувствителен к характеру входной последовательности и его сложность всегда постоянна — O(n * log^2(n)).

--
Maxim Yegorushkin

Здравствуйте, boxter, Вы писали:

B>какие способы сортировки можно выделить
B>мне нужны алгоритмы сортировки массивов
B>а по ним можно отсортировать и линейный список
B>сортировка производится путем изменения ссылок у элементов (next и prev)

Я имею в виду, что тебе нужно не рожать одну мега-функцию, а разбить её на детальки.
Например, выделить примитивные операции над списками (вставка/удаление элементов, склеивание/расщепление списков).

Здравствуйте, MaximE, Вы писали:

>> А сортировочка получилась зверская. Соложность у нее O*N*log2(N). Причем на случайных последовательностях O чуть меньше 1, а на упорядочиных падает почти до 0.5 Что и ожидалось учитывая как я реализовал merge_list

ME>Что это за метод сортировки?
Сам придумал.
Все просто merge_list сливает два отсортированных списка (список из одного элемента отсортирован ) причем когда один список закончился второй без лишних телодвжений приклеевается в конец ибо все оставшияся в нем элементы гарантированно не меньше (отсюда производительность и плавает к счастью только в лучшую сторону )
Основной алгоритм построен так чтобы всегда сливать списки одинаковой длинны(за исключением того момента когда у нас закончится исходный список но и тогда сливаются списки близкой длинны)

ME>P.S. классический merge sort не чувствителен к характеру входной последовательности и его сложность всегда постоянна — O(n * log^2(n)).

Здравствуйте, WolfHound, Вы писали:

Слега пооптимизировал... уменьшил колличество дополнительной памяти в 2 раза. Надеялся что еще и колличество обращений к памяти будет меньше но в x86'ой архитектуре маловато регистров... (хотя память действительно стал немного меньше дергать но всеже мог бы еще меньше)
Хотя все это мелочи и реально производительности скорее всего не добавилось.

template<class Node, class Less>
Node* merge_list(Node* list1, Node* list2, Less less)
{
    Node* list;
    Node* list_res;
    if(less(list1, list2))
    {
        list_res = list1;
        goto list1_pop;
    }
    else
    {
        list_res = list2;
        goto list2_pop;
    }
    while(true)
    {
        if(less(list1, list2))
        {
            list->next = list1;
list1_pop:
            list = list1;
            list1 = list1->next;
            if(list1 == 0)
            {
                list->next = list2;
                return list_res;
            }
        }
        else
        {
            list->next = list2;
list2_pop:
            list = list2;
            list2 = list2->next;
            if(list2 == 0)
            {
                list->next = list1;
                return list_res;
            }
        }
    }
}
template<class Node, class Less>
Node* list_sort(Node* list, Less less)
{
    const int max_stack = 32;
    struct stack_frame
    {
        Node* list;
        void take_from(Node*& lst)
        {
            list = lst;
            lst = lst->next;
            list->next = 0;
        }
    };
    stack_frame stack[max_stack];
    stack[0].take_from(list);
    if(list == 0)
        return stack[0].list;
    int top = 0;
    int count = 0;
    while(true)
    {
        ++top;
        ++count;
        stack[top].take_from(list);
        if(list == 0)
            break;
        for(int c = count; c % 2 == 0; c >>= 1)
        {
            --top;
            stack[top].list = merge_list(stack[top].list, stack[top + 1].list, less);
        }
    }
    while(top > 0)
    {
        --top;
        stack[top].list = merge_list(stack[top].list, stack[top + 1].list, less);
    }
    return stack[0].list;
}

Здравствуйте, WolfHound, Вы писали:

WH>Слега пооптимизировал... уменьшил колличество дополнительной памяти в 2 раза.
И внес маленький бажик... правда он не влиял на правильность сортировки и почти не влиял на скорость но всеравно не порядок...
В функции list_sort надо

    int count = 0;

заменить на

    int count = 1;

иначе в начале стека застревает список из одного элемента, а это добавляет O(N — 1) сложности при склеевании списков оставшихся после работы основного алгоритма.

Здравствуйте, WolfHound, Вы писали:

WH>примечание: синтаксис языка С++(думаю на С перевести сможешь сам)

Я затем и писал примечание, чтоб кто-то написал сразу по синтаксису С.
Поймите меня правильно: я еще новичек в это деле, и самому мне проблематично перевести с С++ на С (учитывая то, что я только изучаю С, а С++ будет только после нового года).
Если не очень сложно, попробуйте все таки написать на С (Буду очень благодарен).

Здравствуйте, Аноним, Вы писали:


А>Я затем и писал примечание, чтоб кто-то написал сразу по синтаксису С.
А>Поймите меня правильно: я еще новичек в это деле, и самому мне проблематично перевести с С++ на С (учитывая то, что я только изучаю С, а С++ будет только после нового года).
А>Если не очень сложно, попробуйте все таки написать на С (Буду очень благодарен).

Это вряд ли кому-нибудь из форума сложно, просто никто не хочет делать твое домашнее задание К тому же не сложное И не интересное
Кодт дал тебе дельный совет, в каком направлении двигаться для решения задачи, назвали подходящий алгоритм, что еще нужно?
Почему-бы не попробовать самому, а? А если в процессе собственного решения у тебя возникнут конкретные вопросы — я не сомневаюсь, что на них конкретно же ответят.

Здравствуйте, Аноним, Вы писали:

А>Если не очень сложно, попробуйте все таки написать на С (Буду очень благодарен).

Что значит "попробуйте"? А ты?

У задачи есть 3 составляющие:
1) структура данных
2) алгоритм
3) закодировать это на конкретном языке

Со структурой ты почти разобрался (двусвязный список).
Почти — потому что не определил над ней удобный инструментарий (в том числе — примитивные операции).
Например, часто двусвязный список удобно надстраивать специальным объектом "список в целом"

typedef ??? Data;

struct Node
{
  struct Node *prev;
  struct Node *next;
  Data data;
};

struct List
{
  struct Node *head;
  struct Node *tail;
};

Причём иногда используют узел-заглушку

struct List
{
  struct Node *head, *tail;
  struct Node dummy;
};
void initEmptyList(struct List *list)
{
  list->dummy.prev = list->dummy.tail = list->head = list->tail = &(list->dummy);
}

С алгоритмами — ещё предстоит определиться. Есть быстрые и медленные, с перестановкой узлов и обменом значений.

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

// вынесем примитивную операцию "обмен значений"
void swapValues(Data *a, Data *b)
{
  Data c = *a; *a = *b; *b = c;
}
void swapNodeValues(struct Node *a, struct Node *b)
{
  swapValues(&a->data, &b->data);
}

void YourAlgorithm(struct List *list)
{
  ...
  if(...) { ... swapValues(node1, node2); ... }
  ...
  if(...) { ... swapValues(node3, node4); ... }
  ...
}
// вместо копипастанья
void YourAlgorithm(struct List *list)
{
  Data tmp;
  ...
  if(...) { ... tmp=node1->data; node1->data=node2->data; node2->data=tmp; ... }
  ...
  if(...) { ... tmp=node3->data; node3->data=node4->data; node4->data=tmp; ... }
  ...
}

Операция "обмен элементов", сводящаяся к выдёргиванию-вставлению, ещё более громоздка (нужно установить значения 8 указателей). Поэтому вынесение её в отдельную процедуру — тем более пригодится.

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

Ну а роль языка (Си или С++) на этой задаче сводится к минимуму.
Возможно, тебе пригодятся указатели на указатели (см. структуры данных); а возможно, и нет.

Здравствуйте, MaximE, Вы писали:

ME>Для списков тебе нужен merge sort (вбей в google) — этот алгоритм не требует произвольного доступа к сортируемой последовательности (как, к примеру, quick sort) и поэтому идеально подходит для списков, но требует дополнительной памяти.

Не требует для списка.