Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.88/8: Рейтинг темы: голосов - 8, средняя оценка - 4.88
Xoniks
0 / 0 / 0
Регистрация: 24.04.2014
Сообщений: 31
1

Быстрая сортировка (сортировка Хоара) для связных списков

19.06.2014, 13:04. Просмотров 1514. Ответов 9
Метки нет (Все метки)

есть у кого готовый алгоритм? или подскажите как реализовать
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.06.2014, 13:04
Ответы с готовыми решениями:

Быстрая сортировка(сортировка Хоара). Отсортировать фрагмент массива
Мне нужно отсортировать фрагмент массива, расположенный между первым и...

C/C++ FAQ :: Быстрая сортировка (сортировка Хоара)
Вопрос, скорее академический, по мотивам реализации. Вот в faq приведена...

Быстрая сортировка (сортировка методом Хоара)
Ввести массив x1,x2,...,x20 в диапазоне . Требуется расположить отрицательные...

Сортировка Хоара / Быстрая сортировка
Доброго времени суток. Написал реализацию алгоритма быстрой сортировки. void...

Быстрая сортировка Хоара
Быстрая сортировка Хоара (QSort) разбивает массив в ходе сортировки до ...

9
Тамика
Котовчанин
928 / 469 / 199
Регистрация: 16.02.2010
Сообщений: 3,304
Записей в блоге: 29
19.06.2014, 13:06 2
Алгоритмы сортировок
0
Kuzia domovenok
2443 / 2151 / 525
Регистрация: 25.03.2012
Сообщений: 7,749
Записей в блоге: 1
19.06.2014, 13:17 3
так же как и для массивов.
только там для разбиения данных на две части лучше не обменивать элементы в цикле, а формировать как бы два новых списка из элементов старых, потому что операции удаления/добавления (особенно в конец) для списков идут быстрее, чем операции обмена
0
Xoniks
0 / 0 / 0
Регистрация: 24.04.2014
Сообщений: 31
19.06.2014, 16:58  [ТС] 4
То есть, я беру например первый элемент списка, делаю его опорным, затем делю список на 2, и в одну сторону меньше опорного, в другую больше?
0
Kuzia domovenok
2443 / 2151 / 525
Регистрация: 25.03.2012
Сообщений: 7,749
Записей в блоге: 1
20.06.2014, 02:27 5
Это и есть оперделение "быстрой сортировки"! Я же говорю о том, что, применяя её к спискам, для разбиения на две половины нужно не переставлять элементы местами, а создавать "как-бэ два новых списка" путём добавления в них элементов из оригинала и далее уже сортировать их.
Как-то так.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <cstdlib>
#include <ctime>
 
struct ListItem
{
    int key;
    ListItem *next;
};
ListItem* Key_Push_Front(ListItem* Start, int newKey)
{
    ListItem* tNew = new ListItem;
    tNew->key = newKey;
    tNew->next = Start;
    return tNew;
}
inline ListItem* Node_Push_Front(ListItem* Start, ListItem* newNode)
{
    newNode->next = Start;
    return newNode;
}
void Print_List(ListItem* MyList)
{
    for (ListItem* it = MyList; it != NULL; it = it->next)
        std::cout << (it->key) << " ";
    std::cout << std::endl;
}
ListItem* Q_sort(ListItem* data, ListItem** endptr)
{
    *endptr = data;
    if (!data)      return NULL;
    if (!data->next) return data;
    ListItem* Right=NULL;
    ListItem* Left=NULL;
    ListItem* it = data;
    ListItem* tmp;
    int med = data->key;
    while (it)
    {
        tmp = it->next;
        if (it->key < med) 
            Right = Node_Push_Front(Right, it);
        else 
            Left  = Node_Push_Front(Left,  it);
        it = tmp;
    }
    Right=Q_sort(Right, &it);
    if (!Right)
        Right = Q_sort(Left, endptr);
    else        
        it->next = Q_sort(Left, endptr);
    return Right;
}
int main()
{
    ListItem* MyList = NULL;
    ListItem* it;
    srand(time(NULL));
    for (int i = 0; i < 10; ++i)
        MyList = Key_Push_Front(MyList, rand()%100);
    Print_List(MyList);
    MyList = Q_sort(MyList, &it);
    Print_List(MyList);
    return 0;
}
1
Xoniks
0 / 0 / 0
Регистрация: 24.04.2014
Сообщений: 31
20.06.2014, 14:16  [ТС] 6
хм.. считает далеко не все промежутки) но спасибо и на этом
0
Kuzia domovenok
2443 / 2151 / 525
Регистрация: 25.03.2012
Сообщений: 7,749
Записей в блоге: 1
20.06.2014, 15:29 7
Что конкретно не так?
0
Xoniks
0 / 0 / 0
Регистрация: 24.04.2014
Сообщений: 31
20.06.2014, 16:55  [ТС] 8
ну попробуй поставить не 10 чисел, а 50 и сам поймешь
и можно как-нибудь сделать? чтобы в функцию сортировки, передавать только указатель на первый элемент списка
0
Kuzia domovenok
2443 / 2151 / 525
Регистрация: 25.03.2012
Сообщений: 7,749
Записей в блоге: 1
20.06.2014, 17:07 9
Цитата Сообщение от Xoniks Посмотреть сообщение
и можно как-нибудь сделать? чтобы в функцию сортировки, передавать только указатель на первый элемент списка
А у меня что по-твоему передаётся?
0
Xoniks
0 / 0 / 0
Регистрация: 24.04.2014
Сообщений: 31
20.06.2014, 17:09  [ТС] 10
C++
1
ListItem* Q_sort(ListItem* data, ListItem** endptr)
endptr.. еще, а по идее можно без него обойтись, я бы хотел передавать в функцию, только один указатель, и больше ничего
0
20.06.2014, 17:09
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.06.2014, 17:09

Быстрая сортировка Хоара без рекурсивных функций
Здравствуйте мне нужно написать быстрою сортировку Хоара но без рекурсивных...

Не работает быстрая сортировка для двумерного массива
Здравствуйте, возникла проблема, не работает быстрая сортировка по возрастанию...

Сортировка расчёской и быстрая сортировка
В файле in.txt записана последовательность целых чисел. Заданными методами...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru