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

Поиск самой быстрой сортировки - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 33, средняя оценка - 4.67
Sich_Taras
14 / 14 / 1
Регистрация: 08.10.2009
Сообщений: 114
13.07.2010, 23:42     Поиск самой быстрой сортировки #1
Ищу быструю реализацию быстрого алгоритма сортировки массива для среднего случая на С/С++ под Win32. Остальные параметры не имеют значения.
Пока что самая быстрая реализация которую я нашел - простой quicksort из книги Седжвика.
Вот прога, где реализована быстрая сортировка :

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
#include<algorithm>
#include<stdlib.h>
#include<time.h>
#include<iostream>
#include<stack>
using namespace std;
 
 
template <class Item>
void quicksort(Item a[], int l, int r)
  {
    if (r <= l) return;
    int i = partition(a, l, r);
    quicksort(a, l, i-1);
    quicksort(a, i+1, r);
  }
 
template <class Item>
int partition(Item a[], int l, int r)
{ 
    int i = l-1, j = r; Item v = a[r];
    for (;;)
      { 
        while (a[++i] < v) ;
        while (v < a[--j]) if (j == l) break;
        if (i >= j) break;
        Item t = a[i]; a[i] = a[j]; a[j] = t; 
      }
     Item t = a[i]; a[i] = a[r]; a[r] = t; 
    return i;
}
 
 
int main()
{
    srand(time(0));
    const int count = 1000000;
    int* a = new int [count];
 
    for(int i = 0; i < count; ++i)
    a[i] = rand();
    
    clock_t begin = clock();
    quicksort(a, 0, count - 1);
    clock_t end = clock();
    cout <<  (double)(end - begin)/CLOCKS_PER_SEC << endl;
 
    int first = 500; 
    cout << "First 500 elements: " << endl;
    for(int i = 0; i < 500; ++i)
        cout << a[i] << ' '; 
    return 0;     
}
У меня на машине Athlon XP 1.66 GHz на Visual Studio 9.0, XP3 эта реализация quicksort сортирует элементы int за 0,68... сек.
Если кто-то имеет более быструю реализацию - киньте код или ссылку, пожалуйста.
Кстати под .Net List.Sort() для int коллекции делает эту работу за 0,2 сек !
Хотелось бы достичь такого результата под виндой на вышеописаной конфигурации без использования стандартных функций С/С++ на языке С/С++/С#.

Добавлено через 20 минут
Если заюзать оптимизацию в опциях компилятора для этого кода - время: 0,23 сек !
Можна ли быстрее ?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.07.2010, 23:42     Поиск самой быстрой сортировки
Посмотрите здесь:

Вопросы насчёт быстрой сортировки C++
Реализовать алгоритм быстрой сортировки C++
C++ Тонкости быстрой сортировки
C++ Алгорим быстрой сортировки
визуализатор быстрой сортировки С++ C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
dxdy
 Аватар для dxdy
97 / 97 / 5
Регистрация: 14.06.2010
Сообщений: 283
14.07.2010, 00:01     Поиск самой быстрой сортировки #2
Sich_Taras анализ сортировок довольно интересное занятие. С какими сортировками ты сравнивал "быструю" сортировку и на каких тестах? Быстрая сортировка хорошо себя показывает на больших массивах, допустим от 10 тыс., но на коротких массивах она будет показывать не самый лучший результат. Могу предположить, что "пузырек усовершенствованный" на коротких массивах даже обгонит quicksort. Книга Седжвика хорошая, но еще для полной уверенности посмотри в книге Кнута 2 том и вроде бы статья по анализу сортировок есть в википедии.
M128K145
Эксперт C++
 Аватар для M128K145
8272 / 3491 / 142
Регистрация: 03.07.2009
Сообщений: 10,707
14.07.2010, 00:01     Поиск самой быстрой сортировки #3
Sich_Taras, это неправильный подход к задаче. Потому как все зависит от данных. Можно простым пузырьком загнать по скорости quick sort. Подайте упорядоченное по возрастанию множество в быструю сортировку и в пузырек и отсортируйте его по возрастанию этими способами. Вы будете удивлены.
Не существует ни самой быстрой сортировки, ни самой медленной. Это ошибочный подход. Надо анализировать данные, на основании выводов выбирать тот или другой способ сортировки
Sich_Taras
14 / 14 / 1
Регистрация: 08.10.2009
Сообщений: 114
14.07.2010, 00:31  [ТС]     Поиск самой быстрой сортировки #4
Входние параметры для сортировки: масив типа int размером от 1000000 елементов.
Елементы не посортированы, а распределены случайно в случайном диапазоне.
dxdy
 Аватар для dxdy
97 / 97 / 5
Регистрация: 14.06.2010
Сообщений: 283
14.07.2010, 01:00     Поиск самой быстрой сортировки #5
Попробуй прогнать на таких тестах:
1. Массив со случайными числами
2. Убывающая последовательность
3. Возрастающая последовательность
И попробуй эти тесты проделать на массивах разной длины. Для примера возьми еще несколько сортировок. Все это можно оформить в виде диаграммы, и уже подвести итог. Но это всего лишь поверхностный анализ сортировок.
M128K145
Эксперт C++
 Аватар для M128K145
8272 / 3491 / 142
Регистрация: 03.07.2009
Сообщений: 10,707
14.07.2010, 09:02     Поиск самой быстрой сортировки #6
Sich_Taras, в любом случайном множестве минимум 30% элементов уже отсортировано!

Какая перед вами цель стоит? Просто изучить алгоритмы сортировок или еще и понять все их тонкости? Если первое, то я не буду ничего вам доказывать, если второе - читайте что вам пишут, читайте литературу
Vas-e-na
 Аватар для Vas-e-na
374 / 371 / 35
Регистрация: 21.06.2010
Сообщений: 1,247
14.07.2010, 13:05     Поиск самой быстрой сортировки #7
лично я изучая алгоритмы сортировок (коды пришлось самому писать, поэтому выводы могут быть и не совем правильными), выбрал для себя алгоритм Шелла, как самый эффективный алгоритм сортировки.
Если поможет, вот моя реализация
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void CControl::ShellSort(void) 
{ 
         int j; 
         int i; 
         int step=m_array.getN()/2; 
         while (step>0) 
         { 
          for (i=0;i<(m_array.getN()-step);i++) 
          { 
           for(j=i;(j>=0)&&(m_array.compare(j,j+step));j--) 
           { 
            m_array.swap(j+step,j); 
            coutSort++; 
           } 
           coutSort++; 
          } 
          step/=2; 
         } 
}
m_array.getN() - возвращает количество элементов массива (тип int)
m_array.compare(int index1, int index2) - сравнивает элемент № index1 с элементом № index2, возвращает true если первый больше второго иначе false
m_array.swap(int index1, int index2) - меняет элементы № index1 и № index2 местами
m_array.key(int indexTO, CKey* key) - ставит ключ key на место indexTO в массив
Описание дополнительных переменных
CKey* m_array.m_key[int index] - указатель на ключ № index массива
CControl:: long coutSort - счетчик обращения к массиву
dxdy
 Аватар для dxdy
97 / 97 / 5
Регистрация: 14.06.2010
Сообщений: 283
14.07.2010, 13:14     Поиск самой быстрой сортировки #8
Vas-e-na Самое важное в сортировке Шелла - это выбор шага, который покажет самый наилучший результат с уменьшением числа инверсий. Хорошая статья на Википедии:
http://ru.wikipedia.org/wiki/%D0%A1%...BB%D0%BB%D0%B0
Цитирую интересный факт из данной статьи:
Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:

* отсутствие потребности в памяти под стек
* отсутствие деградации при неудачных наборах данных — qsort легко деградирует до O(n²), что хуже, чем худшее гарантированное время для сортировки Шелла

Часто оказывается, что сортировка Шелла есть самый лучший способ сортировки до, примерно, 1000 элементов.
Поэтому самый лучший вариант - это изучение научной литературы по данной теме.
Vas-e-na
 Аватар для Vas-e-na
374 / 371 / 35
Регистрация: 21.06.2010
Сообщений: 1,247
14.07.2010, 15:45     Поиск самой быстрой сортировки #9
dxdy, возможно да, сам много читал выбирая сортировку себе, просто не представлялась возможность тестировать на довольно больших объемах данных...

Добавлено через 1 минуту
а на том что тестировалось + знание извлеченные из литературы говорят что Шелл лучший... да и довольно быстрый (имеется в виду что меньшее количество передвижений элементов будет произведено...)
Sich_Taras
14 / 14 / 1
Регистрация: 08.10.2009
Сообщений: 114
14.07.2010, 15:55  [ТС]     Поиск самой быстрой сортировки #10
Vas-e-na, я протестил тот алгоритм ту сортировку что ты выставил и чучуть переписал:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void ShellSort(int* a, int N)
{
         int j; 
         int i; 
         int step = N/2; 
         while (step > 0) 
         { 
          for (i = 0; i < N - step;i++) 
          { 
           for(j = i;j >= 0 && a[j] > a[j+step];j--) 
           { 
            int temp = a[j+step];
            a[j+step] = a[j];
            a[j] = temp;
           } 
         } 
          step/=2; 
        } 
}
Это код сортирует 100000 элементов типа int случайной последовательности у меня за 2.043 сек.
Код быстрой сортировки делает это за 0,02 сек.
Тестировалось на машине Athlon XP 1.66 GHz на Visual Studio 9.0, XP3 с включеной опцией оптимизации компилятора.

Добавлено через 1 минуту
(Код этой быстрой сортировки наверху)
Vas-e-na
 Аватар для Vas-e-na
374 / 371 / 35
Регистрация: 21.06.2010
Сообщений: 1,247
14.07.2010, 16:14     Поиск самой быстрой сортировки #11
Sich_Taras, ну чтож досадно что не получилось...
Sich_Taras
14 / 14 / 1
Регистрация: 08.10.2009
Сообщений: 114
14.07.2010, 21:17  [ТС]     Поиск самой быстрой сортировки #12
Алгоритмы сортировок - здесь есть еще более быстрая итеративная реализация быстрой сортировки:
Случайные 10000000 (10^7) элементов типа int в среднем она сортирует за 2,6 сек против 3,1 сек рекурсивной реализации.

Добавлено через 8 минут
Рекурсивная реализация quickSortR выставленная в этой статьи быстрее всех : 2,4 сек в среднем при сортировке из вышеописанными параметрами (cлучайные 10000000 (10^7) элементов типа int, AthlonXP 1.66 Ггц, Visual Studio 9.0, XP SP3)
kzht91
0 / 0 / 0
Регистрация: 02.07.2010
Сообщений: 19
19.07.2010, 16:05     Поиск самой быстрой сортировки #13
Могу предложить DigitalSort. Сортировка чисел, с заданным диапазоном. Могу объяснить
HIMen
 Аватар для HIMen
4103 / 1352 / 39
Регистрация: 12.04.2009
Сообщений: 2,346
19.07.2010, 17:10     Поиск самой быстрой сортировки #14
Sich_Taras, вот самая быстрая что у меня получалась
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include "stdafx.h"
using namespace System;
const int Q = 30;
void QuickAndInsertSort(array<int>^);
void insertSort(int*, int, int);
void recQuickAndInsertSort(int*, int, int);
void QuickAndInsertSort(array<int>^ arr)
{
    if (arr->Length < Q)
    {
        pin_ptr<int> ptr = &arr[0];
        insertSort(ptr, 0, arr->Length - 1);
    }
    else
    {
        pin_ptr<int> ptr = &arr[0];
        recQuickAndInsertSort(ptr, 0, arr->Length - 1);
    }
}
void insertSort(int* arr, int first, int last)
{
    int j;
    int index;
    for (int i = first; i < last + 1; i++)
    {
        index = arr[i];
        j = i;
        while ((j > 0) && (arr[j - 1] > index))
        {
            arr[j] = arr[j - 1];
            j = j - 1;
        }
        arr[j] = index;
    }
}
void recQuickAndInsertSort(int* arr, int first, int last)
{
    int p = arr[((last - first) >> 1) + first];
    int temp;
    int i = first, j = last;
    while (i <= j)
    {
        while (arr[i] < p && i <= last) i++;
        while (arr[j] > p && j >= first) j--;
        if (i <= j)
        {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }
    if (j - first - Q > 0) recQuickAndInsertSort(arr, first, j);
    else if (j - first > 0) insertSort(arr, first, j);
    if (i - last + Q < 0) recQuickAndInsertSort(arr, i, last);
    else if (i - last < 0)insertSort(arr, i, last);
}
int main()
{
    auto r = gcnew Random(DateTime::Now.Millisecond);
    auto msv = gcnew array<int>(10000000);
    for each (auto% i in msv)
    {
        i = r->Next(int::MinValue, int::MaxValue);
    }
    auto t = DateTime::Now;
    QuickAndInsertSort(msv);
    Console::WriteLine(DateTime::Now - t);
    Console::ReadLine();
    return 0;
}
Рекурсивная быстрая + вставками на малых массивах, под .NET, c использованием управляемых массивов в куче и доступом к элементам через указатель
10^7 элементов от int::MinValue до int::MaxValue в среднем 1.4 секунды
kzht91
0 / 0 / 0
Регистрация: 02.07.2010
Сообщений: 19
19.07.2010, 17:24     Поиск самой быстрой сортировки #15
DigitalSort работает за O(N)
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16824 / 5245 / 319
Регистрация: 30.03.2009
Сообщений: 14,121
Записей в блоге: 26
19.07.2010, 17:40     Поиск самой быстрой сортировки #16
Цитата Сообщение от kzht91 Посмотреть сообщение
DigitalSort работает за O(N)
Т.е. линейная сложность. Ты ничего не путаешь?
kzht91
0 / 0 / 0
Регистрация: 02.07.2010
Сообщений: 19
19.07.2010, 17:41     Поиск самой быстрой сортировки #17
Нет не путаю, но я повторяюсь, что это только для чисел, и только с заданным диапазоном
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16824 / 5245 / 319
Регистрация: 30.03.2009
Сообщений: 14,121
Записей в блоге: 26
19.07.2010, 17:54     Поиск самой быстрой сортировки #18
Цитата Сообщение от kzht91 Посмотреть сообщение
Нет не путаю, но я повторяюсь, что это только для чисел, и только с заданным диапазоном
И только для целых?
kzht91
0 / 0 / 0
Регистрация: 02.07.2010
Сообщений: 19
19.07.2010, 17:55     Поиск самой быстрой сортировки #19
aga)))
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.07.2010, 18:07     Поиск самой быстрой сортировки
Еще ссылки по теме:

прогресс выполнения быстрой сортировки C++
C++ Алгоритмом быстрой сортировки строк
Алгоритм быстрой сортировки C++

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

Или воспользуйтесь поиском по форуму:
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16824 / 5245 / 319
Регистрация: 30.03.2009
Сообщений: 14,121
Записей в блоге: 26
19.07.2010, 18:07     Поиск самой быстрой сортировки #20
Ну.... один раз эту сортировку у нас даже на форуме изобрели - http://www.cyberforum.ru/cpp/thread88396.html
Yandex
Объявления
19.07.2010, 18:07     Поиск самой быстрой сортировки
Ответ Создать тему
Опции темы

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