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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 33, средняя оценка - 4.67
Sich_Taras
14 / 14 / 1
Регистрация: 08.10.2009
Сообщений: 114
#1

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

13.07.2010, 23:42. Просмотров 4045. Ответов 21
Метки нет (Все метки)

Ищу быструю реализацию быстрого алгоритма сортировки массива для среднего случая на С/С++ под 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 сек !
Можна ли быстрее ?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.07.2010, 23:42
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Поиск самой быстрой сортировки (C++):

Пример быстрой сортировки массива строк и сортировки методом выбора - C++
Добрый вечер. Скиньте пожалуйста пример быстрой сортировки массива строк и сортировки массива строк методом выбора. Очень срочно надо,...

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

Тонкости быстрой сортировки - C++
Излазил кучу мест в сети. Нашел массу этих алгоритмов, но на поверку практически каждый не совсем работающий. Представляется, что в этой...

Визуализация быстрой сортировки - C++
Ребят,может кто помочь с визуальной сортировкой массива.. Нужна быстрая сортировка,но буду рад любому примеру даже на пузырьковой... ...

Иллюстрация быстрой сортировки - C++
Ребят,необходимо написать программу похожую на ту,которая тут http://www.cyberforum.ru/csharp-beginners/thread874724.html Помогите...

Метод быстрой сортировки - C++
Доброго времени суток, форумчане. Вчера проходили метод быстрой сортировки. Во входном файле в первой строчке указывается кол-во...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Evg
Эксперт CАвтор FAQ
17812 / 6022 / 388
Регистрация: 30.03.2009
Сообщений: 16,545
Записей в блоге: 26
19.07.2010, 17:40 #16
Цитата Сообщение от kzht91 Посмотреть сообщение
DigitalSort работает за O(N)
Т.е. линейная сложность. Ты ничего не путаешь?
0
kzht91
0 / 0 / 0
Регистрация: 02.07.2010
Сообщений: 19
19.07.2010, 17:41 #17
Нет не путаю, но я повторяюсь, что это только для чисел, и только с заданным диапазоном
0
Evg
Эксперт CАвтор FAQ
17812 / 6022 / 388
Регистрация: 30.03.2009
Сообщений: 16,545
Записей в блоге: 26
19.07.2010, 17:54 #18
Цитата Сообщение от kzht91 Посмотреть сообщение
Нет не путаю, но я повторяюсь, что это только для чисел, и только с заданным диапазоном
И только для целых?
0
kzht91
0 / 0 / 0
Регистрация: 02.07.2010
Сообщений: 19
19.07.2010, 17:55 #19
aga)))
0
Evg
Эксперт CАвтор FAQ
17812 / 6022 / 388
Регистрация: 30.03.2009
Сообщений: 16,545
Записей в блоге: 26
19.07.2010, 18:07 #20
Ну.... один раз эту сортировку у нас даже на форуме изобрели - http://www.cyberforum.ru/cpp/thread88396.html
0
Sich_Taras
14 / 14 / 1
Регистрация: 08.10.2009
Сообщений: 114
20.07.2010, 00:03  [ТС] #21
Цитата Сообщение от HIMen Посмотреть сообщение
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 секунды
Я протестировал в среднем 1,96 против 2.434 сек, новый рекорд !!!
Молодец HIMen !!! Вот это я понимаю, спасибо !

Добавлено через 4 минуты
А если заюзать полную оптимизацию в среднем: 00:00:01.5522320 сек !!!!
0
xacmajib
Сообщений: n/a
28.09.2011, 13:23 #22
www.sorting-algorithms.com
И тему можно закрыть.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.09.2011, 13:23
Привет! Вот еще темы с ответами:

Алгоритм быстрой сортировки - C++
Написать программу, реализующую алгоритм быстрой сортировки(рекурсивный) для массива целых чисел.

Не алгоритм быстрой сортировки - C++
Просто как подключить эту функцию Не работаеееет #include&lt;iostream&gt; #include&lt;iomanip&gt; #include &lt;algorithm&gt; using namespace std; ...

Алгорим быстрой сортировки - C++
В одной из тем выложен алгоритм быстрой сортировки. Возник вопрос: если индексы i и j указывают на один элемент зачем нужен обмен? ...

Вопросы насчёт быстрой сортировки - C++
Здравствуйте. Объясните, пожалуйста. Есть алгоритм быстрой сортировки: Код: int shag=1; void quickSort(int arr, int left, int...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
28.09.2011, 13:23
Ответ Создать тему
Опции темы

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