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

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

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

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

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Rififi
2338 / 1053 / 44
Регистрация: 03.05.2009
Сообщений: 2,656
22.01.2010, 00:36     САМАЯ БЫСТРАЯ сортировка! #2
OVERPOWER8,

Теоретически и практически доказано, что сортировка OVERPOWER8 - самая быстрая в мире.

думаю, теперь пора подавать заявку в книгу рекордов Гиннеса, а также в Нобелевский комитет.
только про кодепад им не говори.
OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 00:41  [ТС]     САМАЯ БЫСТРАЯ сортировка! #3
>> Rififi

Можешь выяснить, почему некоторые компиляторы выдают Segmentation Fault
А то я не вижу ни одной ошибки, и G++ ничего не говорит.
Gravity
562 / 556 / 39
Регистрация: 29.01.2009
Сообщений: 1,274
22.01.2010, 00:43     САМАЯ БЫСТРАЯ сортировка! #4
Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
int* Sorted = new int[max+1];
Ты выделяешь новый массив размером равным максимальному значению сортируемого массива. Но чего будем делать, если придется сортировать структуры или другие комплексные типы данных?
OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 00:45  [ТС]     САМАЯ БЫСТРАЯ сортировка! #5
>>Gravity

Но чего будем делать, если придется сортировать структуры или другие комплексные типы данных?
Придумаю что-нибудь, если надо будет.
Ты вот лучше подскажи, почему codepad выдает Segmentation Fault
И мой компилятор при использовании более 3000000 элементов - тоже Segmentation Fault
Блин, никак не вижу ошибку.
insideone
Модератор
Автор FAQ
3636 / 914 / 49
Регистрация: 10.01.2010
Сообщений: 2,464
22.01.2010, 00:53     САМАЯ БЫСТРАЯ сортировка! #6
У меня и вовсе это вываливается в "Необработанное исключение в "0x00401c77" в "AB.exe": 0xC00000FD: Stack overflow." в файле "chkstk.asm - C stack checking routine". Ведь массив передается как копия.
При SIZE = 1 вообще виснет
При SIZE > 1 : ~ "Необработанное исключение в "0x7c92aa8c" в "AB.exe": 0xC0000005: Нарушение прав доступа при записи "0x00030fec"."
Все в VS 2008
OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 00:57  [ТС]     САМАЯ БЫСТРАЯ сортировка! #7
insideone

А как насчет:
void sort(int* arr)

Однако это не решает проблему с codepad
insideone
Модератор
Автор FAQ
3636 / 914 / 49
Регистрация: 10.01.2010
Сообщений: 2,464
22.01.2010, 01:00     САМАЯ БЫСТРАЯ сортировка! #8
Вы пишите программы для codepad или для чего?) Разве это важный фактор? -)

Тэкс... что бы я не делал с SIZE код не работает. При "void sort(int* arr)" тоже не работает. Во как!

C++
1
2
3
4
5
        for(i=0; i<SIZE; i++)
                if(arr[i] > max)
                        max = arr[i];
        
        int* Sorted = new int[max+1];
При пошаговом выполнении обнаружил что компилятор посчитал что "int* Sorted = new int[max+1];" расположена внутри тела цикла. По крайне мере это так выглядит. VS 2008 сошла с ума? =)
Однако любые исправления не привели к работоспособности. Гмгм
OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 01:08  [ТС]     САМАЯ БЫСТРАЯ сортировка! #9
>> insideone

Вообще-то это важно. Хотелось бы чтобы мой код работал исправно на всех компиляторах, а не тоьлко на G++.

Есть простое решение - создать 2 глобальных массива. Тогда будет всегда работать исправно.
Только встает одна проблема - как быть с размерами?

При пошаговом выполнении обнаружил что компилятор посчитал что "int* Sorted = new int[max+1];" расположена внутри тела цикла.

Это как же так? В таком случае надо отсоединить тело цикла скобками { }
CyBOSSeR
Эксперт C++
2299 / 1669 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
22.01.2010, 01:42     САМАЯ БЫСТРАЯ сортировка! #10
Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
Требуется памяти: 3*N
Массив из двух элементов: 1, 1999999.
Максимальный элемент: 1999999.

C++
1
int* Sorted = new int[max+1]; // в данном случае max == 1999999
При выполнении этой строки выделится память размером 2000000 * sizeof(int), т.е. в МИЛЛИОН раз больше чем размер массива для сортировки в памяти.

Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
Количество шагов в любом случае: 3*N
Даже не берусь подсчитать порядок количества шагов в твоем алгоритме для приведенного примера.
OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 01:46  [ТС]     САМАЯ БЫСТРАЯ сортировка! #11
>> CyBOSSeR

Да, все правильно. Этот вариант не подходит для сортировки маленьких массивов. А вот больших - очень даже.

МОЖЕТ КТО-ТО ОБЪЯСНИТЬ, ЧТО В КОДЕ НЕ ЧИСТО!?
CyBOSSeR
Эксперт C++
2299 / 1669 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
22.01.2010, 01:52     САМАЯ БЫСТРАЯ сортировка! #12
Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
Этот вариант не подходит для сортировки маленьких массивов. А вот больших - очень даже.
Как и для сортировки массивов, в которых, есть хотя бы один отрицательный элемент.
Упадем здесь либо здесь:
C++
1
int* Sorted = new int[max+1];
либо здесь:
C++
1
Sorted[arr[i]]+=1;
OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 02:07  [ТС]     САМАЯ БЫСТРАЯ сортировка! #13
>> CyBOSSeR

Упадем здесь:
C++
1
int* Sorted = new int[max+1];
либо здесь:
C++
1
Sorted[arr[i]]+=1;
А что тут не правильно?

Если не сложно, то предложите ваш вариант программы.

P.S. На этот раз решил обойтись без указателей.
CyBOSSeR
Эксперт C++
2299 / 1669 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
22.01.2010, 02:16     САМАЯ БЫСТРАЯ сортировка! #14
Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
А что тут не правильно?
Если у нас массив состоит только из отрицательных элементов, то и максимальный элемент будут отрицательным. Поэтому в этой строке
C++
1
int* Sorted = new int[max+1];
max+1 будет меньше или равно нулю - падаем по попытке выделить память отрицательного размера.

Если в массиве есть отрицательные элементы, то в этой строке
C++
1
Sorted[arr[i]]+=1;
рано или поздно arr[i] станет меньше нуля - падаем по выходу за пределы массива.
OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 02:21  [ТС]     САМАЯ БЫСТРАЯ сортировка! #15
>> CyBOSSeR

Да ладно вам с отрицательными элементами!
Я попросил проверить тот код, который я предложил изначально - там что-то не правильно.
CyBOSSeR
Эксперт C++
2299 / 1669 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
22.01.2010, 02:24     САМАЯ БЫСТРАЯ сортировка! #16
Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
На этот раз решил обойтись без указателей.
Главное палку не перегибай в этом вопросе.

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

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

>> CyBOSSeR

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

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

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

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

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

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

С индексами все путем. Проблема в чем-то другом...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.01.2010, 02:46     САМАЯ БЫСТРАЯ сортировка!
Еще ссылки по теме:

Быстрая сортировка - 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...


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

Или воспользуйтесь поиском по форуму:
CyBOSSeR
Эксперт C++
2299 / 1669 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
22.01.2010, 02:46     САМАЯ БЫСТРАЯ сортировка! #20
Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
>> CyBOSSeR

Странно. С помощью STL -> qsort я сортировал этот же массив, только SIZE был в разы больше - порядка 20 000 000, и все работало нормально. Подозреваю, что проблема в чем-то другом.
Не ты писал про переполнение стека, а кто-то другой. Как я уже говорил размер стека может варьироваться в зависимости от платформы, настроек проекта и т.д.
Возможно у тебя размер стека больше.
Yandex
Объявления
22.01.2010, 02:46     САМАЯ БЫСТРАЯ сортировка!
Закрытая тема Создать тему
Опции темы

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