Форум программистов, компьютерный форум 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++ все работает замечательно.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Rififi
 Аватар для Rififi
2330 / 1045 / 43
Регистрация: 03.05.2009
Сообщений: 2,656
22.01.2010, 00:36     САМАЯ БЫСТРАЯ сортировка! #2
OVERPOWER8,

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

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

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

Но чего будем делать, если придется сортировать структуры или другие комплексные типы данных?
Придумаю что-нибудь, если надо будет.
Ты вот лучше подскажи, почему codepad выдает Segmentation Fault
И мой компилятор при использовании более 3000000 элементов - тоже Segmentation Fault
Блин, никак не вижу ошибку.
insideone
Модератор
Автор FAQ
 Аватар для insideone
3622 / 900 / 47
Регистрация: 10.01.2010
Сообщений: 2,429
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
 Аватар для OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 00:57  [ТС]     САМАЯ БЫСТРАЯ сортировка! #7
insideone

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

Однако это не решает проблему с codepad
insideone
Модератор
Автор FAQ
 Аватар для insideone
3622 / 900 / 47
Регистрация: 10.01.2010
Сообщений: 2,429
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
 Аватар для 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++
 Аватар для CyBOSSeR
2293 / 1663 / 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
 Аватар для OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 01:46  [ТС]     САМАЯ БЫСТРАЯ сортировка! #11
>> CyBOSSeR

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

МОЖЕТ КТО-ТО ОБЪЯСНИТЬ, ЧТО В КОДЕ НЕ ЧИСТО!?
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2293 / 1663 / 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
 Аватар для 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++
 Аватар для CyBOSSeR
2293 / 1663 / 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
 Аватар для OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 02:21  [ТС]     САМАЯ БЫСТРАЯ сортировка! #15
>> CyBOSSeR

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

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

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

>> CyBOSSeR

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

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

И на мой взгляд этот алгоритм идеальный - и прост в реализации и быстрый, но вот только для определенных случаев.
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2293 / 1663 / 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
 Аватар для 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++
Быстрая сортировка (сортировка методом Хоара) C++
C++ Сортировка Хоара / Быстрая сортировка

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

Или воспользуйтесь поиском по форуму:
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2293 / 1663 / 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     САМАЯ БЫСТРАЯ сортировка!
Закрытая тема Создать тему
Опции темы

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