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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 96, средняя оценка - 4.79
OVERPOWER8
 Аватар для OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 00:29     САМАЯ БЫСТРАЯ сортировка! #1
Теоретически и практически доказано, что сортировка 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++ все работает замечательно.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
OVERPOWER8
 Аватар для 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++
 Аватар для CyBOSSeR
2293 / 1663 / 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
 Аватар для OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 03:04  [ТС]     САМАЯ БЫСТРАЯ сортировка! #23
>> CyBOSSeR

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

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

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

Ни хрена себе! Проверьте конкретно мой пример.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
22.01.2010, 12:11     САМАЯ БЫСТРАЯ сортировка! #27
У тебя цикл по элементам, а в нем ещё по значениям. Ну и как ты предлагаешь получить 3*N?
OVERPOWER8
 Аватар для 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
Эксперт С++Автор FAQ
 Аватар для Evg
16821 / 5242 / 318
Регистрация: 30.03.2009
Сообщений: 14,118
Записей в блоге: 26
22.01.2010, 14:26     САМАЯ БЫСТРАЯ сортировка! #29
Подозреваю, что в коде нечисто то, что Sort выделается динамически, но при этом его элементы остаются неинициализированными. В итоге строки 25 и 26 ведут себя недетерминировано

А вообще, этот метод и твои комментарии к нему мне очень напоминают институтские уроки химии. Там был закон имени какого-то мужика, в котором утверждалось, что для всех элементов периодической системы кроме (дальше перечисляется чуть ли не полтаблицы, причём никакой системы в этом нет) в диапазоне температур ПРИМЕРНО от 20 до 70 градусов цельсия при давлении ПРИМРНО в одну атмосферу и влажности ПРИМЕРНО такой-то что-то там выполнялось. Это они называли словом ЗАКОН. Вот и сортировка у тебя такая же - работает только в каких-то узкоопределённых условиях, которые в реальной жизни практически не нужны. Ну это так, чисто к сведению
OVERPOWER8
 Аватар для 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
 Аватар для zim22
276 / 141 / 2
Регистрация: 11.07.2009
Сообщений: 606
22.01.2010, 14:58     САМАЯ БЫСТРАЯ сортировка! #31
>Ну и как ты предлагаешь получить 3*N?
Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
умножь время выполнения алгоритма на количество тактов в секунду твоего процессора. И результат подели на количество элементов.
если бы на собеседовании при приёме на работу кандидат мне бы дал такой ответ - я бы ему сказал "до-свиданья".
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
1233 / 771 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
22.01.2010, 15:14     САМАЯ БЫСТРАЯ сортировка! #33
OVERPOWER8:
Если человек изобрёл алгоритм, зачем его дарить другим людям.
Вероятно этот алгоритм не особо ценен.

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

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

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

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

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

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

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

функцию-анализ.
Если анализировать последовательность, значит тратить время.
Ну и что! Если окажется, что алгоритм OVERPOWER8 подходит, то затраты на время очень даже оправдаются!
Genius Ignat
1233 / 771 / 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++
Быстрая сортировка (сортировка методом Хоара) C++
C++ Сортировка Хоара / Быстрая сортировка

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

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

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

Текущее время: 05:01. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru