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

@OVERPOWER8 · Регистрация: 29.11.2009

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

Теоретически и практически доказано, что сортировка 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 · 22.01.2010, 15:26

вики

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

@Ignat · 22.01.2010, 15:28

OVERPOWER8:
Если ты гений помоги мне разобрать с библиотекой декодирования MPEG-2 видео.

@OVERPOWER8 · 22.01.2010, 15:31 **[ТС]**

>> zim22

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

>> Genius Ignat

Нет, вот уж сам разбирайся.

@Ignat · 22.01.2010, 15:34

OVERPOWER8:
Ты действительно хочешь мне помочь?

@OVERPOWER8 · 22.01.2010, 15:36 **[ТС]**

>> zim22

Ну так что? Теперь по другому смотрите на мою сортировку?

@Ignat · 22.01.2010, 15:37

OVERPOWER8:
Я вспылил на счет MPEG-2.
Тебе лучше этого не видеть.

Evg · 22.01.2010, 16:29

Сообщение от OVERPOWER8

А что не нравится?

По-моему тебе довольно внятно объяснили, что при сортировке маасива из двух элементов { 1, 1000000 } у тебя будет цикл на миллион итераций

Сообщение от OVERPOWER8

Такое впечатление, будто вы мой код даже не видели!

Такое впечатление, что ты совершенно не читаешь, что тебе пишут

@zim22 · 22.01.2010, 16:47

Сообщение от OVERPOWER8

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

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

Сообщение от OVERPOWER8

if(arr[i] > max)
max = arr[i];

а вот второй раз:

Сообщение от OVERPOWER8

while(Sorted[i])
{
arr[counter++]=i;
Sorted[i]--;
}

Сообщение от OVERPOWER8

Ну так что? Теперь по другому смотрите на мою сортировку?

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

@OVERPOWER8 · 22.01.2010, 17:10 **[ТС]**

>> 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 · 22.01.2010, 17:13

Сообщение от OVERPOWER8

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

А теперь придумай случай, где РЕАЛЬНО нужна сортировка с такими ограничениями?

@OVERPOWER8 · 22.01.2010, 17:40 **[ТС]**

>> Evg

А теперь придумай случай, где РЕАЛЬНО нужна сортировка с такими ограничениями?

Да полно, даже перечислять не стану!

Вы бы лучше посмотрели на время!

@CyBOSSeR · 22.01.2010, 17:48

Сообщение от OVERPOWER8

Вы бы лучше посмотрели на время!

Что нам дает это время, если область применения этой сортировки очень и очень ограничена?
То что можно будет кому-нибудь пустить пыль в глаза?
Сортировка в таком виде никому не будет нужна.

Где мы будем эту сортировку использовать?

@OVERPOWER8 · 22.01.2010, 17:53 **[ТС]**

Имеется 400.000.000 человек с возрастами: 20 ... 70 лет.
Надо их отсортировать по возрастам.

Моя сортировка займет 10 секунд + 1 секунда - анализ.
STL -> qsort: 140 секунд. (т. е. более чем в 10! раз дольше!)

@zim22 · 22.01.2010, 17:54

Сообщение от OVERPOWER8

Вы бы лучше посмотрели на время!

твоя сортировка сортирует всё-что угодно или только типы int?

Сообщение от OVERPOWER8

STL -> qsort: 140 секунд.

так stl или qsort?

@OVERPOWER8 · 22.01.2010, 18:37 **[ТС]**

>> zim22

твоя сортировка сортирует всё-что угодно или только типы int?

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

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

так stl или qsort?

Обобщенный алгоритм qsort из стандартной библиотеки stl (не знаю, как остальные, но я отношу cstdlib к stl)

@Ignat · 22.01.2010, 18:39

Где мы будем эту сортировку использовать?

Вести перепись населения планеты: упорядочивать данные о людях всей планеты.

@OVERPOWER8 · 22.01.2010, 18:44 **[ТС]**

>> Genius Ignat

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

@odip · 22.01.2010, 21:11

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

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

Добавлено через 9 минут
Рекомендую ознакомиться с алгоритмом http://ru.wikipedia.org/wiki/Сортировка_подсчётом
Похоже это и есть алгоритм, который пытается изобрести OVERPOWER8

@HIMen · 22.01.2010, 21:40

этот алгоритм уже давно придуман и называется он сортировка подсчетом
которая во-первых требует памяти 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

Ну вообще-то может сортировать все что угодно - классы, структуры и т. д.

@Ignat · 22.01.2010, 22:10

Жестко
Так вроде тему закрывали.

Новые блоги и статьи Все статьи Все блоги /
Книги по геймдизайну, левел-дизайну, игровым механикам и проектированию игрового опыта 8Observer8 08.11.2026 Содержание блога \| English Version 1. 2003 - 06 - Designing Virtual Worlds (1st Edition) Автор: Richard A. Bartle \| Объем: 768 стр. Ссылки: Amazon . . .	Родители токсичные абьюзеры по отношению к своим детям ругают их оскорбляют не любят zorxor 08.11.2026 Жить в атмосфере постоянных оскорблений, критики и холодности со стороны родителей — это тяжелое и болезненное испытание, которое оставляет глубокие эмоциональные раны. Токсичное и абьюзивное. . .	Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ. zorxor 08.11.2026 Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .	Паттерн очереди действий/команд (Action / Command Queue). Система очереди действий и кат-сцен с SDL3 Callbacks, cglm и OpenGL 8Observer8 07.11.2026 Содержание блога \| English Version Руководство для начинающих по реализации паттерна очереди действий/ команд (Action / Command Queue) на C++ (C++20) с использованием официального SDL3 Callbacks. . .
Проверка полного ФИО в типовом справочнике Maks 07.11.2026 Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров". Задача: Запрет инициалов. Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .	Про "Windows must die!" kumehtar 04.11.2026 Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .	Красочные поля с номером страницы svg+background-image russiannick 04.11.2026 Красочные поля с номером страницы не менее важны чем в эпоху бумажных книг. Посему спешу представить почтеннейшей публике этот важный инструмент который эти поля и формирует. В процессе разработки. . .	Вступаем в новую фазу генерации favicons, векторную. russiannick 02.11.2026 Теперь нет нужды скрывать что используется простой svg. Исходный код изображения помещаем в поле и жмем кнопку. Исходник преобразуется в вид корректный для помещения в favicon или в url(). Нажатие. . .

@Ignat 1261 / 799 / 108 Регистрация: 16.09.2009 Сообщений: 2,010
	22.01.2010, 15:28
	OVERPOWER8: Если ты гений помоги мне разобрать с библиотекой декодирования MPEG-2 видео. 0

@OVERPOWER8 19 / 19 / 2 Регистрация: 29.11.2009 Сообщений: 224
	22.01.2010, 15:31 [ТС]
	>> zim22 А где вы увидели у меня "абстрактную операцию сравнения ключей"? Такое впечатление, будто вы мой код даже не видели! >> Genius Ignat Нет, вот уж сам разбирайся. 0

@Ignat 1261 / 799 / 108 Регистрация: 16.09.2009 Сообщений: 2,010
	22.01.2010, 15:34
	OVERPOWER8: Ты действительно хочешь мне помочь? 0

@OVERPOWER8 19 / 19 / 2 Регистрация: 29.11.2009 Сообщений: 224
	22.01.2010, 15:36 [ТС]
	>> zim22 Ну так что? Теперь по другому смотрите на мою сортировку? 0

@Ignat 1261 / 799 / 108 Регистрация: 16.09.2009 Сообщений: 2,010
	22.01.2010, 15:37
	OVERPOWER8: Я вспылил на счет MPEG-2. Тебе лучше этого не видеть. 0

@OVERPOWER8 19 / 19 / 2 Регистрация: 29.11.2009 Сообщений: 224
	22.01.2010, 17:10 [ТС]
	>> 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. Однако памяти расходуется приблизительно одинакого. 0

@OVERPOWER8 19 / 19 / 2 Регистрация: 29.11.2009 Сообщений: 224
	22.01.2010, 17:53 [ТС]
	Имеется 400.000.000 человек с возрастами: 20 ... 70 лет. Надо их отсортировать по возрастам. Моя сортировка займет 10 секунд + 1 секунда - анализ. STL -> qsort: 140 секунд. (т. е. более чем в 10! раз дольше!) 0

@OVERPOWER8 19 / 19 / 2 Регистрация: 29.11.2009 Сообщений: 224
	22.01.2010, 18:44 [ТС]
	>> Genius Ignat Пока что не сталкивался с необходимостью такой сортировки. Но вот если столкнусь (ну не знаю, может быть! при программировании какой-нибудь игры) Не надо будет ничего изобретать. 0

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	22.01.2010, 21:11
	Ввиду того что автор не может разобраться с работоспособностью собственного кода продолжение данной темы считаю бессмысленным. Добавлено через 46 минут Ввиду новых уточнений тему открываю. Добавлено через 9 минут Рекомендую ознакомиться с алгоритмом http://ru.wikipedia.org/wiki/Сортировка_подсчётом Похоже это и есть алгоритм, который пытается изобрести OVERPOWER8 0

@Ignat 1261 / 799 / 108 Регистрация: 16.09.2009 Сообщений: 2,010
	22.01.2010, 22:10
	Жестко Так вроде тему закрывали. 0