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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 96, средняя оценка - 4.79
OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
#1

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

22.01.2010, 00:29. Просмотров 12404. Ответов 59
Метки нет (Все метки)

Теоретически и практически доказано, что сортировка 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++ все работает замечательно.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.01.2010, 00:29     САМАЯ БЫСТРАЯ сортировка!
Посмотрите здесь:

Самая быстрая сортировка - C++
Какая на данный момент самая быстрая сортировка?

Быстрая сортировка - C++
Воспользовался готовым решением для сортировки: Алгоритмы сортировок в итоге если беру массив: int A = {2,1,4,5,8,7,1,5,2,9} ...

Быстрая сортировка - C++
Помогите, пожалуйста! Не понимаю почему, но при использовании быстрой сортировки программа выдаёт ошибку и не работает. Вообще первый раз...

Быстрая сортировка - C++
Помоги мне ответить на вопросы,большая просьба,заранее спасибо Быстрая сортировка #include &lt;iostream&gt; using namespace std; ...

Быстрая сортировка - C++
Задача: пользователь задает количество элементов массива (макс. - 500 000), вводит их, затем задает количество запросов (макс. - 10000) и...

Быстрая сортировка - C++
Смотрел в тему посвященной быстрой сортировке, и не совсем понял. написал подобный код. Хотелось бы наиболее подробных комментариев, за...

Быстрая сортировка - C++
Есть три файла: Функция: #ifndef QUICK #define QUICK #include &lt;vector&gt; using namespace std; template&lt;class...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zim22
depict1
276 / 141 / 2
Регистрация: 11.07.2009
Сообщений: 606
22.01.2010, 14:58     САМАЯ БЫСТРАЯ сортировка! #31
>Ну и как ты предлагаешь получить 3*N?
Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
умножь время выполнения алгоритма на количество тактов в секунду твоего процессора. И результат подели на количество элементов.
если бы на собеседовании при приёме на работу кандидат мне бы дал такой ответ - я бы ему сказал "до-свиданья".
OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 15:00  [ТС]     САМАЯ БЫСТРАЯ сортировка! #32
>> zim22

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

C++
1
2
3
4
5
6
7
8
9
10
11
time_t start, end;
        
        time(&start);
                sort(array);
        time(&end);
        
        int seconds = difftime(end, start);
        cout << seconds << endl;
        
        uint64_t steps = seconds * CLOCKS_PER_SEC;
        cout << steps/SIZE << endl;
Как я уже сказал, эта сортировка идеальна для конкретного случая. Например, в какой-то организации 1 000 000 сотрудников, их возраста: 20 ... 70 лет. И допустим надо их отсортировать по возрастам. Для такого случая сортировки лучше просто не существует!

И предусмотреть другую сортировку, а также проверку, когда какой сортировкой пользоваться.
Я забыл упомянуть, что эта сортировка в процессе разработки.
Genius Ignat
1235 / 773 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
22.01.2010, 15:14     САМАЯ БЫСТРАЯ сортировка! #33
OVERPOWER8:
Если человек изобрёл алгоритм, зачем его дарить другим людям.
Вероятно этот алгоритм не особо ценен.

Добавлено через 21 секунду
Запатентуй изобретение.

Добавлено через 2 минуты
Я бы если бы, изобрел какой-то "суперский алгоритм" на форум точно бы его не выложил.
OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 15:16  [ТС]     САМАЯ БЫСТРАЯ сортировка! #34
>> Genius Ignat

А мне не жалко, пусть другие тоже пользуются.
Может кто и поможет его доработать.

Только надо добавить функцию-анализ, которая решает, имеет ли смысл пользоваться этим алгоритмом или выбрать другой. В противном случае последовательность сортируется другим способом, например, qsort.
Genius Ignat
1235 / 773 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
22.01.2010, 15:18     САМАЯ БЫСТРАЯ сортировка! #35
OVERPOWER8:
функцию-анализ.
Если анализировать последовательность, значит тратить время.
OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 15:19  [ТС]     САМАЯ БЫСТРАЯ сортировка! #36
>> Genius Ignat

У меня есть также суперский алгоритм Шифра Вернама. Но он не всегда идеален, и тоже в процессе разработки.

Думаю, знаешь, что такое Шифр Вернама.
Genius Ignat
1235 / 773 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
22.01.2010, 15:21     САМАЯ БЫСТРАЯ сортировка! #37
OVERPOWER8:
Надеюсь анализ не будет дольше сортировки.

Добавлено через 1 минуту
OVERPOWER8:
Может тебе дать ссылочку на достижение человечества: лучшие алгоритмы.
OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 15:21  [ТС]     САМАЯ БЫСТРАЯ сортировка! #38
>> Genius Ignat

функцию-анализ.
Если анализировать последовательность, значит тратить время.
Ну и что! Если окажется, что алгоритм OVERPOWER8 подходит, то затраты на время очень даже оправдаются!
Genius Ignat
1235 / 773 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
22.01.2010, 15:24     САМАЯ БЫСТРАЯ сортировка! #39
OVERPOWER8:
А кстати видел один сайт на котором описывалась производительность алгоритмов сортировки,
не просто описывалась, там производились тесты с последовательностями различных размеров.
OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 15:26  [ТС]     САМАЯ БЫСТРАЯ сортировка! #40
>> Genius Ignat

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

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

>> Genius Ignat

Нет, вот уж сам разбирайся.
Genius Ignat
1235 / 773 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
22.01.2010, 15:34     САМАЯ БЫСТРАЯ сортировка! #44
OVERPOWER8:
Ты действительно хочешь мне помочь?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.01.2010, 15:36     САМАЯ БЫСТРАЯ сортировка!
Еще ссылки по теме:

Быстрая сортировка - C++
void qSort(int a, int N) { int i = 0, j = N; int temp, p; p = a; do { while ( a &lt; p ) i++;

Быстрая сортировка - C++
Читал о быстрой сортировки смысл понятен но не могу понять некоторые моменты. Каким образом работают два последних условия? Они работают...

Быстрая сортировка - C++
Не работают обе версии сортировки.Не понимаю почему.И еще почему-то портится значение второго элемента. Быстрая сортировка 1.0 ...

Быстрая сортировка - C++
Каждому элементу массива а соответствует значение массива b то есть a b 1-5 2-3 5-2 3-1 4-4 если сортировать массив b по...

Быстрая сортировка - C++
нормальный код? а то третий день парюсь, вроде сейчас получилось void quicksort (int *a, int start, int end) { int point = partition...


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

Или воспользуйтесь поиском по форуму:
OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 15:36  [ТС]     САМАЯ БЫСТРАЯ сортировка! #45
>> zim22

Ну так что? Теперь по другому смотрите на мою сортировку?
Yandex
Объявления
22.01.2010, 15:36     САМАЯ БЫСТРАЯ сортировка!
Закрытая тема Создать тему
Опции темы

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