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

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

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

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

22.01.2010, 00:29. Просмотров 12395. Ответов 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...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 02:51  [ТС]     САМАЯ БЫСТРАЯ сортировка! #21
>> CyBOSSeR

Понятно. А в случае с vector <int> array( 20 000 000); проблем не будет?
Если нет, то как передать вектор в функцию?

C++
1
2
3
4
5
6
void sort(vector <int*> arr);
...
int SIZE=20000000;
vector <int> array(SIZE);
...
sort(array);
А еще проце - задать размер стека:
Только бы узнать как
CyBOSSeR
Эксперт C++
2300 / 1670 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
22.01.2010, 02:58     САМАЯ БЫСТРАЯ сортировка! #22
Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
>> CyBOSSeR
Понятно. А в случае с vector <int> array( 20 000 000); проблем не будет?
Если нет, то как передать вектор в функцию?
Проблем с выделением памяти под вектор быть не должно.

C++
1
void Sort(std::vector<int>& arr)
или
C++
1
void Sort(std::vector<int>* arr)
OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 03:04  [ТС]     САМАЯ БЫСТРАЯ сортировка! #23
>> CyBOSSeR

Хорошо. Спасибо за ответы. А как вы относитесь к тому, как я этим же методом буду сортировать массив, содержащий и отрицательные элементы (ранее распиал) ?
CyBOSSeR
Эксперт C++
2300 / 1670 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
22.01.2010, 03:11     САМАЯ БЫСТРАЯ сортировка! #24
Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
>> CyBOSSeR

Хорошо. Спасибо за ответы. А как вы относитесь к тому, как я этим же методом буду сортировать массив, содержащий и отрицательные элементы (ранее распиал) ?
Не за что.
Насчет работы с отрицательными элементами - овчинка выделки не стоит. Доработка этого алгоритма для отрицательных чисел повлечет дополнительные накладные расходы, а, соответственно, скорость будет падать.

Да и вообще я бы не советовал дальше пытать этот алгоритм - толку от него не будет (ни в скорости, ни в памяти). Хотя отрицательный опыт не менее ценен (а то и более), чем положительный. Так что пробуй, пытайся, хотя бы для опыта.
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
22.01.2010, 06:47     САМАЯ БЫСТРАЯ сортировка! #25
OVERPOWER8, где здесь 3*N? Я вижу N*m, где m может здорово плавать и значительно превышать N. То есть ты по-моему первый, кому удалось сделать сортировку хуже пузырька.
OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 12:09  [ТС]     САМАЯ БЫСТРАЯ сортировка! #26
>> taras atavin

Ни хрена себе! Проверьте конкретно мой пример.
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
22.01.2010, 12:11     САМАЯ БЫСТРАЯ сортировка! #27
У тебя цикл по элементам, а в нем ещё по значениям. Ну и как ты предлагаешь получить 3*N?
OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 12:13  [ТС]     САМАЯ БЫСТРАЯ сортировка! #28
>> CyBOSSeR

Вот с вами НЕ соглашусь! Как я уже писал, в определенных случаях этот алгоритм будет самым быстрым! И с этим нельзя не согласиться.

Просто в программе сделаю три вещи:
1. Пирамидальная сортировка (O(n)*long(n))
2. Сортировка OVERPOWER8 (O*m), m=3, 4, 5, ... В зависимости от случая.
3. Анализ последовательности, чтобы выбрать правильную сортировку.

И вижу все причины для доработки моего алгоритма.
Пол года поработаю над моей сортировкой, и она будет лучше, чем быстрая и пирамидальная вместе взятые.
Evg
Эксперт CАвтор FAQ
17528 / 5766 / 368
Регистрация: 30.03.2009
Сообщений: 15,854
Записей в блоге: 26
22.01.2010, 14:26     САМАЯ БЫСТРАЯ сортировка! #29
Подозреваю, что в коде нечисто то, что Sort выделается динамически, но при этом его элементы остаются неинициализированными. В итоге строки 25 и 26 ведут себя недетерминировано

А вообще, этот метод и твои комментарии к нему мне очень напоминают институтские уроки химии. Там был закон имени какого-то мужика, в котором утверждалось, что для всех элементов периодической системы кроме (дальше перечисляется чуть ли не полтаблицы, причём никакой системы в этом нет) в диапазоне температур ПРИМЕРНО от 20 до 70 градусов цельсия при давлении ПРИМРНО в одну атмосферу и влажности ПРИМЕРНО такой-то что-то там выполнялось. Это они называли словом ЗАКОН. Вот и сортировка у тебя такая же - работает только в каких-то узкоопределённых условиях, которые в реальной жизни практически не нужны. Ну это так, чисто к сведению
OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 14:47  [ТС]     САМАЯ БЫСТРАЯ сортировка! #30
Цитата Сообщение от taras atavin Посмотреть сообщение
У тебя цикл по элементам, а в нем ещё по значениям. Ну и как ты предлагаешь получить 3*N?
Да очень просто - возьми мой пример, скомпилируй, умножь время выполнения алгоритма на количество тактов в секунду твоего процессора.

И результат подели на количество элементов.

как-то так:
C++
1
2
3
4
5
6
7
time_t start,end;
time (&start);
... sort();
time(&end);
int seconds = difftime (end,start);
uint64_t steps = seconds * CLOCKS_PER_SEC ;
cout << steps / SIZE << endl;
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:
А кстати видел один сайт на котором описывалась производительность алгоритмов сортировки,
не просто описывалась, там производились тесты с последовательностями различных размеров.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.01.2010, 15:26     САМАЯ БЫСТРАЯ сортировка!
Еще ссылки по теме:

Быстрая сортировка - 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:26  [ТС]     САМАЯ БЫСТРАЯ сортировка! #40
>> Genius Ignat

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

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