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

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

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

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

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

59
CyBOSSeR
Эксперт С++
2305 / 1675 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
22.01.2010, 02:24 #16
Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
На этот раз решил обойтись без указателей.
Главное палку не перегибай в этом вопросе.

OVERPOWER8, в том то и дело, очень много мест, где можно упасть, потому что алгоритм положенный в основу этого кода никуда не годится.
Кстати на словах опиши его.
0
OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 02:29  [ТС] #17
>> CyBOSSeR

А зачем на словах описывать? Я его в коде описал. И, честно говоря, не вижу ни одной причины, почему некоторые компиляторы ругаются (В данном примере).

>> CyBOSSeR

Может быть, вы объясните, почему некоторым компиляторам не нравится конкретно мой код (а не алгоритм)?

А насчет отрицательных чисел - очень просто - создам новый массив из (-1*min)+1 элементов, отсортирую их в порядке убывания, и потом объединю оба массива.

И на мой взгляд этот алгоритм идеальный - и прост в реализации и быстрый, но вот только для определенных случаев.
0
CyBOSSeR
Эксперт С++
2305 / 1675 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
22.01.2010, 02:41 #18
Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
Может быть, вы объясните, почему некоторым компиляторам не нравится конкретно мой код (а не алгоритм)?
Компилятора под рукой нет. Но могу по ошибкам подсказать.
Segmentation Fault говорит о попытки обращения к защищенным участкам памяти. Скорее всего где-то произошел выход за пределы массива.
Возможное решение: трассировать и проверять индексы.

Stack overflow говорит о переполнении стека. Размер стека ограничен (в зависимости от платформы). Это ошибка скорее всего связана с этой строкой:
C++
1
int array[SIZE];
При огромных значениях SIZE массив array просто не "влезает" в стек.
Возможное решение: выделять память в куче.

Вот как то так.
0
OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 02:43  [ТС] #19
>> CyBOSSeR

Странно. С помощью STL -> qsort я сортировал этот же массив, только SIZE был в разы больше - порядка 20 000 000, и все работало нормально. Подозреваю, что проблема в чем-то другом.

С индексами все путем. Проблема в чем-то другом...
0
CyBOSSeR
Эксперт С++
2305 / 1675 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
22.01.2010, 02:46 #20
Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
>> CyBOSSeR

Странно. С помощью STL -> qsort я сортировал этот же массив, только SIZE был в разы больше - порядка 20 000 000, и все работало нормально. Подозреваю, что проблема в чем-то другом.
Не ты писал про переполнение стека, а кто-то другой. Как я уже говорил размер стека может варьироваться в зависимости от платформы, настроек проекта и т.д.
Возможно у тебя размер стека больше.
0
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);
А еще проце - задать размер стека:
Только бы узнать как
0
CyBOSSeR
Эксперт С++
2305 / 1675 / 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)
1
OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 03:04  [ТС] #23
>> CyBOSSeR

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

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

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

Ни хрена себе! Проверьте конкретно мой пример.
0
taras atavin
3570 / 1754 / 91
Регистрация: 24.11.2009
Сообщений: 27,567
22.01.2010, 12:11 #27
У тебя цикл по элементам, а в нем ещё по значениям. Ну и как ты предлагаешь получить 3*N?
0
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. Анализ последовательности, чтобы выбрать правильную сортировку.

И вижу все причины для доработки моего алгоритма.
Пол года поработаю над моей сортировкой, и она будет лучше, чем быстрая и пирамидальная вместе взятые.
0
Evg
Эксперт CАвтор FAQ
18377 / 6424 / 441
Регистрация: 30.03.2009
Сообщений: 17,815
Записей в блоге: 28
22.01.2010, 14:26 #29
Подозреваю, что в коде нечисто то, что Sort выделается динамически, но при этом его элементы остаются неинициализированными. В итоге строки 25 и 26 ведут себя недетерминировано

А вообще, этот метод и твои комментарии к нему мне очень напоминают институтские уроки химии. Там был закон имени какого-то мужика, в котором утверждалось, что для всех элементов периодической системы кроме (дальше перечисляется чуть ли не полтаблицы, причём никакой системы в этом нет) в диапазоне температур ПРИМЕРНО от 20 до 70 градусов цельсия при давлении ПРИМРНО в одну атмосферу и влажности ПРИМЕРНО такой-то что-то там выполнялось. Это они называли словом ЗАКОН. Вот и сортировка у тебя такая же - работает только в каких-то узкоопределённых условиях, которые в реальной жизни практически не нужны. Ну это так, чисто к сведению
1
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;
0
22.01.2010, 14:47
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.01.2010, 14:47
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
30
Закрытая тема Создать тему
Опции темы

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