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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Поиск в тексте http://www.cyberforum.ru/cpp-beginners/thread153525.html
Помогите пожалуйста В файле имеется текст. Найти отсутствие пробелов после точки в конце предложения, исправить ошибки и сохранить файл. Предложением считать часть текста, что кончается "." или начинается с нового рядка
C++ bool в параметрах функции можно ли использовать тип bool в параметрах функции? void draw(char ch, int width, bool vline, bool hline ); или лучше использовать что-то другое? http://www.cyberforum.ru/cpp-beginners/thread153503.html
Невозможно найти или открыть файл pdb C++
я написал по учебнику прогу //Первая программа на C++ #include "stdafx.h" #include <iostream> int main () { std::cout << "Добро пожаловать в С++!\n"; return 0; }
шаблон функции C++
Здрасти. Как правильно написать шаблон ,например, этой функции? int **newmatrix(int row, int col){ int **matrix=new int*; for (int i=0; i<row; ++i) matrix=new int; return matrix; } я сделал так:
C++ Паттерны http://www.cyberforum.ru/cpp-beginners/thread153443.html
Пролистал всю главную страницу и решил поставить вопрос в С++ , чем сможите помогите. Суть , изучаю объектно ориентированное проектирование , есть открытые вопросы , куда писать?:)
C++ Простой список в виде массива.Как работать с элементами списка-массива через единую функцию Добрый день!Подсобите,как реализовать Простой список,но не через шаблоны или создание указателей,а как бы в виде массива.(Ну,или ваш вариант через указатели или шаблоны). Кто-то наверно подумает,что опять изобретают велосипед=) Сама проблема кроется в том,что нужно организовать просмотр элементов списка и каких либо действий над ним через единую общую функцию( void Visit(void (*pf)(Item &) ... подробнее

Показать сообщение отдельно
Sich_Taras
14 / 14 / 1
Регистрация: 08.10.2009
Сообщений: 114
13.07.2010, 23:42     Поиск самой быстрой сортировки
Ищу быструю реализацию быстрого алгоритма сортировки массива для среднего случая на С/С++ под 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 сек !
Можна ли быстрее ?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 23:01. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru