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

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

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

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

22.01.2010, 00:29. Просмотров 12685. Ответов 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
Rififi
2359 / 1052 / 44
Регистрация: 03.05.2009
Сообщений: 2,656
22.01.2010, 00:36 #2
OVERPOWER8,

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

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

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

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

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

Однако это не решает проблему с codepad
0
insideone
Модератор
Автор FAQ
3642 / 921 / 49
Регистрация: 10.01.2010
Сообщений: 2,472
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 сошла с ума? =)
Однако любые исправления не привели к работоспособности. Гмгм
0
OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 01:08  [ТС] #9
>> insideone

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

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

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

Это как же так? В таком случае надо отсоединить тело цикла скобками { }
0
CyBOSSeR
Эксперт С++
2303 / 1673 / 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
Даже не берусь подсчитать порядок количества шагов в твоем алгоритме для приведенного примера.
0
OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 01:46  [ТС] #11
>> CyBOSSeR

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

МОЖЕТ КТО-ТО ОБЪЯСНИТЬ, ЧТО В КОДЕ НЕ ЧИСТО!?
0
CyBOSSeR
Эксперт С++
2303 / 1673 / 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;
0
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. На этот раз решил обойтись без указателей.
1
CyBOSSeR
Эксперт С++
2303 / 1673 / 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] станет меньше нуля - падаем по выходу за пределы массива.
0
OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 02:21  [ТС] #15
>> CyBOSSeR

Да ладно вам с отрицательными элементами!
Я попросил проверить тот код, который я предложил изначально - там что-то не правильно.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.01.2010, 02:21
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
15
Yandex
Объявления
22.01.2010, 02:21
Закрытая тема Создать тему
Опции темы

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