VPF::[C++] Quicksort - Форум программистов

Sheismydream

Дата 4.4.2007, 13:58 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 1
Регистрация: 4.4.2007

Репутация: нет
Всего: нет

Условия:
Ограничение времени на тест: 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 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 234
Регистрация: 10.6.2002

Репутация: 7
Всего: 18

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

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »