Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [C++] Quicksort

Автор: Sheismydream 4.4.2007, 13:58

Условия:
Ограничение времени на тест: 4 сек
Ограничение памяти на тест: 200 Мб
Входной файл: input.txt
Выходной файл: output.txt
Входной файл содержит число n (кол-во элементов массива) затем собственно элементы.
Выходной файл должен содержать отсортированные по возрастанию эл-ты
ограничения : 1<=n<=1000000
-2147483648<=a[i]<=2147483647

Основная проблема - программа массив сортирует, но не укладывается по скорости в 4 секунды. Как максимально увеличить скорость сортировки простыми средствами для данного алгоритма?

Код


#include <iostream> 
using namespace std;
#include <fstream> 

void sort(long a[],long high, long low)

{
    long i, j, p, temp;
    
    i=low;
    j=high;
    p=a[(low+high)/2];

do
{
    while (a[i]<p) i++;


    while (a[j]>p) j--;

if(i<=j)

{
    temp=a[i];
    a[i]=a[j];
    a[j]=temp;
    i++;
    j--;
}
}

while (i<=j);

if(j>low) sort(a, j, low);

if(high>i) sort(a, high, i);

}

void main()
{
    ifstream in("input.txt");

    long n, i, k;
    in>>n;
    long *a=new long[n];    
    for(k=0; k<n; k++)
    {in>>a[k];}
in.close();

sort(a, n-1, 0);

ofstream out("output.txt");
for(i=0; i<n; i++)
{out<<a[i]<<' ';}
out.close();
delete []a;

}

Автор: MBo 4.4.2007, 15:07

странный какой-то квиксорт... Элемент-разделитель у тебя только номинальный, а рекурсивные вызовы должны производиться для двух "половинок", не включая разделительный элемент (т.е. каждый раз для меньшего числа элементов)