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

@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

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

Новые блоги и статьи Все статьи Все блоги /
http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит переходные токи и напряжения на элементах схемы. . . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .

@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