Форум программистов, компьютерный форум CyberForum.ru

САМАЯ БЫСТРАЯ сортировка! - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 96, средняя оценка - 4.79
OVERPOWER8
 Аватар для OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 00:29     САМАЯ БЫСТРАЯ сортировка! #1
Теоретически и практически доказано, что сортировка OVERPOWER8 - самая быстрая в мире.

Характеристика:
Требуется памяти: 3*N
Количество шагов в любом случае: 3*N
Стабильная: ДА
Метод: Замена

Если не верите, то можете проверить:

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
#include <iostream>
#include <stdlib.h>
using namespace std;
 
const int SIZE=2000000;
 
void sort(int arr[])
{
    int max=arr[0];
    
    int i;
    
    for(i=0; i<SIZE; i++)
        if(arr[i] > max)
            max = arr[i];
    
    int* Sorted = new int[max+1];
    
    for(i=0; i<SIZE; i++)
        Sorted[arr[i]]+=1;
    
    int counter=0;
    
    for(i=0; i<=max; i++)
        while(Sorted[i])
        {
            arr[counter++]=i;
            Sorted[i]--;
        }
        
    delete [] Sorted;
}
 
int main()
{
    srand(time(0));
 
    int Max=2000000;
    
    int i, j;
    
    int array[SIZE];
    
    for(i=0; i<SIZE; i++)
        array[i]=rand()%Max+1;
        
    sort(array);
    
    cout << "Sorted!\n";
    
    /*
    for(i=0; i<SIZE; i++)
        cout << array[i] << " ";
    */
    
    return 0;
}
P. S. при использовании элементов более 2000000, требуется использовать другой тип данных, например, uint64_t.

Не знаю, почему codepad.org выдает Segmentation Fault,
у меня на Linux G++ все работает замечательно.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zim22
depict1
 Аватар для zim22
276 / 141 / 2
Регистрация: 11.07.2009
Сообщений: 606
22.01.2010, 15:26     САМАЯ БЫСТРАЯ сортировка! #41
вики
Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей всегда нуждаются по меньшей мере в O(n log n) сравнениях
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Genius Ignat
1233 / 771 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
22.01.2010, 15:28     САМАЯ БЫСТРАЯ сортировка! #42
OVERPOWER8:
Если ты гений помоги мне разобрать с библиотекой декодирования MPEG-2 видео.
OVERPOWER8
 Аватар для OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 15:31  [ТС]     САМАЯ БЫСТРАЯ сортировка! #43
>> zim22

А где вы увидели у меня "абстрактную операцию сравнения ключей"?
Такое впечатление, будто вы мой код даже не видели!

>> Genius Ignat

Нет, вот уж сам разбирайся.
Genius Ignat
1233 / 771 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
22.01.2010, 15:34     САМАЯ БЫСТРАЯ сортировка! #44
OVERPOWER8:
Ты действительно хочешь мне помочь?
OVERPOWER8
 Аватар для OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 15:36  [ТС]     САМАЯ БЫСТРАЯ сортировка! #45
>> zim22

Ну так что? Теперь по другому смотрите на мою сортировку?
Genius Ignat
1233 / 771 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
22.01.2010, 15:37     САМАЯ БЫСТРАЯ сортировка! #46
OVERPOWER8:
Я вспылил на счет MPEG-2.
Тебе лучше этого не видеть.
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16821 / 5242 / 318
Регистрация: 30.03.2009
Сообщений: 14,118
Записей в блоге: 26
22.01.2010, 16:29     САМАЯ БЫСТРАЯ сортировка! #47
Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
А что не нравится?
По-моему тебе довольно внятно объяснили, что при сортировке маасива из двух элементов { 1, 1000000 } у тебя будет цикл на миллион итераций

Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
Такое впечатление, будто вы мой код даже не видели!
Такое впечатление, что ты совершенно не читаешь, что тебе пишут
zim22
depict1
 Аватар для zim22
276 / 141 / 2
Регистрация: 11.07.2009
Сообщений: 606
22.01.2010, 16:47     САМАЯ БЫСТРАЯ сортировка! #48
Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
А где вы увидели у меня "абстрактную операцию сравнения ключей"?
на то она и астрактная операция, что под ней подразумевается любой способ, применив который, можно выяснить является ли один ключ меньше другого.
вот один раз увидел:
Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
if(arr[i] > max)
max = arr[i];
а вот второй раз:
Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
while(Sorted[i])
{
arr[counter++]=i;
Sorted[i]--;
}
Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
Ну так что? Теперь по другому смотрите на мою сортировку?
я на неё вообще никак не смотрю. это кривой велосипед. всё уже сделано до тебя. есть уйма сортировок для которых определены их характеристики. я уж лучше их буду использовать, чем твою
OVERPOWER8
 Аватар для OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 17:10  [ТС]     САМАЯ БЫСТРАЯ сортировка! #49
>> zim22

Ну как хотите.

А я уже составил алгоритм анализа, когда использовать мою сортировку:
1. Элементов больше, чем 10 000 000 (иначе ненамного быстрее, чем qsort)
2. все элементы >= 0
3. Макс. элемент такой, чтобы хватило памяти для динам. массива такого размера,
и желательно, чтобы он был меньше, чем N*log(N).

Иначе использовать STL -> qsort.

Вот несколько сравнительных запусков (показано время в с.):
STL -> qsort: 110 39 19 3 3
Power_sort: 44 16 7 8 3

Следствие: если элементов меньше, чем 10.000.000, то моя сортировка не особо выигрывает перед qsort. Однако памяти расходуется приблизительно одинакого.
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16821 / 5242 / 318
Регистрация: 30.03.2009
Сообщений: 14,118
Записей в блоге: 26
22.01.2010, 17:13     САМАЯ БЫСТРАЯ сортировка! #50
Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
А я уже составил алгоритм анализа, когда использовать мою сортировку:
1. Элементов больше, чем 10 000 000 (иначе ненамного быстрее, чем qsort)
2. все элементы >= 0
3. Макс. элемент такой, чтобы хватило памяти для динам. массива такого размера,
и желательно, чтобы он был меньше, чем N*log(N).
А теперь придумай случай, где РЕАЛЬНО нужна сортировка с такими ограничениями?
OVERPOWER8
 Аватар для OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 17:40  [ТС]     САМАЯ БЫСТРАЯ сортировка! #51
>> Evg
А теперь придумай случай, где РЕАЛЬНО нужна сортировка с такими ограничениями?
Да полно, даже перечислять не стану!

Вы бы лучше посмотрели на время!
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2293 / 1663 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
22.01.2010, 17:48     САМАЯ БЫСТРАЯ сортировка! #52
Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
Вы бы лучше посмотрели на время!
Что нам дает это время, если область применения этой сортировки очень и очень ограничена?
То что можно будет кому-нибудь пустить пыль в глаза?
Сортировка в таком виде никому не будет нужна.

Где мы будем эту сортировку использовать?
OVERPOWER8
 Аватар для OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 17:53  [ТС]     САМАЯ БЫСТРАЯ сортировка! #53
Имеется 400.000.000 человек с возрастами: 20 ... 70 лет.
Надо их отсортировать по возрастам.

Моя сортировка займет 10 секунд + 1 секунда - анализ.
STL -> qsort: 140 секунд. (т. е. более чем в 10! раз дольше!)
zim22
depict1
 Аватар для zim22
276 / 141 / 2
Регистрация: 11.07.2009
Сообщений: 606
22.01.2010, 17:54     САМАЯ БЫСТРАЯ сортировка! #54
Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
Вы бы лучше посмотрели на время!
твоя сортировка сортирует всё-что угодно или только типы int?
Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
STL -> qsort: 140 секунд.
так stl или qsort?
OVERPOWER8
 Аватар для OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 18:37  [ТС]     САМАЯ БЫСТРАЯ сортировка! #55
>> zim22

твоя сортировка сортирует всё-что угодно или только типы int?
Ну вообще-то может сортировать все что угодно - классы, структуры и т. д. Для этого надо дописать, чтобы создавал динамический массив определенных обэектов, и функцию, которая возвращает значение какого-либо члена объекта.

Можно, конечно, сделать, только пока что нет надобности и желания.

так stl или qsort?
Обобщенный алгоритм qsort из стандартной библиотеки stl (не знаю, как остальные, но я отношу cstdlib к stl)
Genius Ignat
1233 / 771 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
22.01.2010, 18:39     САМАЯ БЫСТРАЯ сортировка! #56
Где мы будем эту сортировку использовать?
Вести перепись населения планеты: упорядочивать данные о людях всей планеты.
OVERPOWER8
 Аватар для OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 18:44  [ТС]     САМАЯ БЫСТРАЯ сортировка! #57
>> Genius Ignat

Пока что не сталкивался с необходимостью такой сортировки.
Но вот если столкнусь (ну не знаю, может быть! при программировании какой-нибудь игры)
Не надо будет ничего изобретать.
odip
Эксперт C++
 Аватар для odip
7224 / 3286 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
22.01.2010, 21:11     САМАЯ БЫСТРАЯ сортировка! #58
Ввиду того что автор не может разобраться с работоспособностью собственного кода продолжение данной темы считаю бессмысленным.

Добавлено через 46 минут
Ввиду новых уточнений тему открываю.

Добавлено через 9 минут
Рекомендую ознакомиться с алгоритмом http://ru.wikipedia.org/wiki/Сортировка_подсчётом
Похоже это и есть алгоритм, который пытается изобрести OVERPOWER8
HIMen
 Аватар для HIMen
4103 / 1352 / 39
Регистрация: 12.04.2009
Сообщений: 2,346
22.01.2010, 21:40     САМАЯ БЫСТРАЯ сортировка! #59
этот алгоритм уже давно придуман и называется он сортировка подсчетом
которая во-первых требует памяти O(MAX),
во-вторых нестабильна (ты хоть гуглил что значит устойчивая сортировка)
в-третьих она основана вовсе не на замене (капитан очевидность недоумевает, где там замена)

Что-то мне подсказывает ты проводил тесты на массивах типа
C#
1
2
Random rnd = new Random(DateTime.Now.Millisecond);
int[] msv = (new int[2000000]).Select(n => rnd.Next(0, 10)).ToArray();
А ты попробуй такой
C#
1
2
3
Random rnd = new Random(DateTime.Now.Millisecond);
int[] msv = (new int[2000000]).Select(n => rnd.Next(0, 10)).ToArray();
msv[4] = int.MaxValue;
или такой
C#
1
int[] msv = { 0, int.MaxValue };
Любой из алгоритмов быстрая/пирамидальная/слиянием или подобный будет гораздо быстрее, а т.к твоя реализация еще и криворукая ты получишь либо StackOverflow либо OutOfMemory

Даже хорошая реализация (которая стабильна) не делает эту сортировку достойной: она сортирует только дискретные величины

Не по теме:

Надеюсь код на c# тебе понятен



Добавлено через 4 минуты
Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
Ну вообще-то может сортировать все что угодно - классы, структуры и т. д.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.01.2010, 22:10     САМАЯ БЫСТРАЯ сортировка!
Еще ссылки по теме:

Быстрая сортировка (сортировка Хоара) для связных списков C++
Быстрая сортировка (сортировка методом Хоара) C++
C++ Сортировка Хоара / Быстрая сортировка

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

Или воспользуйтесь поиском по форуму:
Genius Ignat
1233 / 771 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
22.01.2010, 22:10     САМАЯ БЫСТРАЯ сортировка! #60
Жестко
Так вроде тему закрывали.
Yandex
Объявления
22.01.2010, 22:10     САМАЯ БЫСТРАЯ сортировка!
Закрытая тема Создать тему
Опции темы

Текущее время: 06:42. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru