Быстрая сортировка

[Legioner93]

Написал функцию быстрой сортировки массива структур. Но не работает.

#include "stdio.h" 
struct atl{long int m;long int s;};
void gsort(struct atl a[], long int left, long int right)
{
   long int i,last;
   void swap(struct atl a[], long int i, long int j);

   if(left<right) {
   swap(a, left, (left+right)/2);
   last=left;
   for(i=left+1; i<=right; i++)
      if(a[i].s<a[left].s)
         swap(a, ++last,i);
   swap(a,left,last);
   gsort(a,left,last-1);
   gsort(a,last+1,right);}
}
void swap(struct atl a[], long int i, long int j)
{
   struct atl temp;
   temp=a[i];
   a[i]=a[j];
   a[j]=temp;
}

Где недочёт? Спасибо.

[Circiter]

2Legioner93

Цитата:

Но не работает.

Приведите пример. Вроде-бы все правильно...

[venco]

Что значит "не работает"?

[Circiter]

Возможно, этот код глючит на очень больших выборках; можно попробовать заменить (left+right)/2 на left+(right-left)/2 (чтобы избежать переполнения).

[venco]

Circiter в сообщении #373200 писал(а):

Возможно, этот код глючит на очень больших выборках; можно попробовать заменить (left+right)/2 на left+(right-left)/2 (чтобы избежать переполнения).

Сомнительно, что автору удалось получить переполнение - для этого потребуется 8ГБ данных.

[arseniiv]

(Оформление)

Legioner93 в сообщении #373081 писал(а):

struct atl{long int m;long int s;};
// ...
gsort(a,last+1,right);}

Вам что, место жалко?

Кстати, может, в объявлениях переменных убрать перед atl struct? Вроде только для enum надо писать повторно.

[Legioner93]

После вызова в массиве появляются какие 7-8значные числа. Думаю, что это адреса:) Только где я там с указателями наглупил, не знаю.

[Circiter]

Тогда, очевидно, проблема в вызывающем коде. Для проверки попробуйте воспользоваться стандарной qsort, а если не поможет, то запостите вашу программку сюды.

[venco]

Legioner93 в сообщении #373241 писал(а):

После вызова в массиве появляются какие 7-8значные числа. Думаю, что это адреса:) Только где я там с указателями наглупил, не знаю.

Вы с какими параметрами вызываете gsort()? Не забыли, что right - индекс последнего элемента, а не количество элементов?

-- Ср ноя 10, 2010 13:33:15 --

arseniiv в сообщении #373212 писал(а):

Кстати, может, в объявлениях переменных убрать перед atl struct? Вроде только для enum надо писать повторно.

В C++ можно убрать, а в C без ухищрений - нет.

[Circiter]

2arseniiv

Цитата:

Кстати, может, в объявлениях переменных убрать перед atl struct

Это вы к typedef'ам привыкли. :)

-- Чт ноя 11, 2010 00:56:04 --

2Legioner93
Ну вот простейший тест:

    int i;
    struct atl a[4]=
        {{0, 3},
         {1, 4},
         {2, 7},
         {3, 0}};

    gsort(a, 0, 3);

    for(i=0; i<4; i++)
        printf("%ld ", a[i].s);

Все вроде-бы сортируется. Видимо, вы как-то очень уж хитро память выделяете. :)

Вот тест с динамическим выделением:

    int i;
    const int length=20;
    struct atl *a=malloc(length*sizeof(struct atl));

    for(i=0; i<length; i++)
    {
        a[i].m=i;
        a[i].s=rand()%100;
    }

    for(i=0; i<length; i++)
        printf("%ld ", a[i].s);
    putchar('\n');

    gsort(a, 0, length-1);

    for(i=0; i<length; i++)
        printf("%ld ", a[i].s);

    free(a);

[Legioner93]

#include "stdio.h" 
struct atl{long int m;long int s;};
void gsort(struct atl a[], long int left, long int right)
{
   long int i,last;
   void swap(struct atl a[], long int i, long int j);
   if(left<right) {
   swap(a, left, (left+right)/2);
   last=left;
   for(i=left+1; i<=right; i++)
      if(a[i].s<a[left].s)
         swap(a, ++last,i);
   swap(a,left,last);
   gsort(a,left,last-1);
   gsort(a,last+1,right);}
}
void swap(struct atl a[], long int i, long int j)
{
   struct atl temp;
   temp=a[i];
   a[i]=a[j];
   a[j]=temp;
}
int main()
{
    long int n,i,k,num,uk;
   struct atl temp;
    long long int sum;
   struct atl a[100000];
   scanf("%d",&n);
   for(i=0;i<n;i++) {scanf("%d %d",&a[i].m,&a[i].s);}
   gsort(a,0,n-1);
   num=-1; uk=-1; sum=0;
   while(uk<n)
   {
      uk++;
      if(a[uk].s>=sum)
      {
         sum=sum+a[uk].m; num++;
      }
   }
   num++;
    printf("%d",num); 
   return 0;
}

http://www.acm.mipt.ru/judge/problems.p ... roblem=004
Вот задача. Вышеприведенный код на 9 тесте выдает ошибку (там стоит компилятор GNU C++) "Wrong answer".
Замена же быстрой сортировки на стандартную сортировку пузырьком:

for(i=2;i<n+1;i++)
    for(k=0;k<=n-i;k++)
   if(a[k].s>a[k+1].s)
      {
          temp=a[k]; a[k]=a[k+1]; a[k+1]=temp;
      }

дает ошибку лишь на 17 тесте "Time limit", которая и вынудила меня писать быструю сортировку. Спасибо.

-- Ср ноя 10, 2010 23:45:34 --

Проблема в том, что я не знаю тест, на котором программа не работает. Сам я тоже проверил её на нескольких небольших тестах:вроде всё правильно. И еще раз повторю, что при замене быстрой сортировки на сортировку пузырьком этот тест проходится. Значит проблема именно в сортировке. И я не могу понять, почему она может какой-то массив отсортировать неправильно.

[venco]

В данных может быть много элементов с одинаковым s. Пузырёк сохранит их порядок, а быстрая сортировка может изменить. Я пока не понял, как Вы обошлись сортировкой по одному полю, так что возможно ошибка в алгоритме после сортировки, а разный порядок отсортированных элементов влияет на то, на каком тесте будет ошибка.

[venco]

Я тут подумал, и решил, что Ваш алгоритм просто неправилен. Он может на некоторых входных данных давать правильный результат, причём это будет зависеть от того, как отсортированы элементы. Вот и вся разница с пузырьком. Даже если бы пузырёк успевал, всё равно где-нибудь результат был бы неправильный.
Алгоритм нужен посложнее.

[Legioner93]

Дело в том, что если равны силы атлетов, то равны и их массы. Это следует из условия задачи. Поэтому сила атлета однозначно его идентифицирует. И если массив отсортирован по неубыванию силы, то он будет и неубывающим по массам. А если у нас есть несколько атлетов-клонов, их можно тасовать сколько угодно. Мой алгоритм таков:
Будем строить пирамиду с конца (вершины).
На верхушку пирамиды ставим самого легкого и слабого. В противном случае, если бы наверху стоял не самый легкий и слабый, а самый легкий и слабый атлет был где-то в другой части пирамиды или не участвовал в ней вообще, то верхнего атлета можно было бы заменить на самого легкого и слабого, при этом башня ТОЧНО не разрушится. Под него поставим самого легкого и слабого из тех, кто в состоянии удержать верхушку. Аналогично, если бы мы поставили не самого легкого и слабого из тех, кто в состоянии удержать верхушку, а другого атлета, который сильнее (а значит и не легче), то его можно поменять с самым легким и слабым (из тех, кто может держать верхушку) и башня ТОЧНО не разрушится. Аналогично ставим атлетов всё ниже и ниже, пока не станет так, что ни один из оставшихся (а значит из всех атлетов вообще) не может удержать пирамиду. Извините, что написал много "воды", но старался изложить как можно яснее.
Из указанного построения следует, что оптимальнее всего будет упорядочить массив по неубыванию силы (а значит и массы). Тогда не нужно будет искать каждый раз подходящего атлета с минимальной силой(массой) по всему массиву. Спасибо. По-прежнему не нашел ошибку.

[venco]

Вроде алгоритм верный.

-- Ср ноя 10, 2010 18:12:12 --

Кстати, а зачем Вы используете тип long int? Да ещё вводите его по формату int.

-- Ср ноя 10, 2010 18:13:24 --

И что мешает Вам использовать стандартную сортировку qsort()?