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

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

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

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

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

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

Быстрая сортировка (сортировка Хоара) для связных списков - C++
есть у кого готовый алгоритм? или подскажите как реализовать

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

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

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

Сортировка Хоара / Быстрая сортировка - C++
Доброго времени суток. Написал реализацию алгоритма быстрой сортировки. void SortHhoar(int *arr,int f,int l)//Хоара { int mid = (f...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
zim22
depict1
276 / 141 / 2
Регистрация: 11.07.2009
Сообщений: 606
22.01.2010, 14:58 #31
>Ну и как ты предлагаешь получить 3*N?
Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
умножь время выполнения алгоритма на количество тактов в секунду твоего процессора. И результат подели на количество элементов.
если бы на собеседовании при приёме на работу кандидат мне бы дал такой ответ - я бы ему сказал "до-свиданья".
0
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 лет. И допустим надо их отсортировать по возрастам. Для такого случая сортировки лучше просто не существует!

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

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

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

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

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

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

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

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

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

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

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

>> Genius Ignat

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

Ну так что? Теперь по другому смотрите на мою сортировку?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.01.2010, 15:36
Привет! Вот еще темы с ответами:

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

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

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

Быстрая сортировка - C++
Помогите пожалуйста, при использовании алгоритма быстрой сортировки, конечный массив получается не отсортированным, хотя все операции...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
22.01.2010, 15:36
Закрытая тема Создать тему
Опции темы

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