Вот тут я написал сортировку (quick sort). Нужно подсчитать кол-во перестановок и сранений (для набора чисел "87950433"):

Код

#include <iostream.h> #include <conio.h> int a[8]; int c = 0; /* кол-во сравнений */ int e = 0; /* кол-во перестановок */ /* нахождение опорного элемента */ int findpivot(int i, int j) {   int k;   for (k = i + 1; k <= j; k++)   {     if (a[k] > a[i])     {       c++;       return k;     }     else     {       if (a[k] < a[i])       {         c++;         return i;       }     }   }      return -1; }; /* findpivot */ /* сортировка участка массива от i до j */ int partition(int i, int j, int w) {   int l = i;   int r = j;   do {     // swap elements     int t = a[l]; a[l] = a[r]; a[r] = t;     e++;          while (a[l] < w) l++;     while (a[r] >= w) r--;        } while (l < r);   return l; }; /* partiton */ /* собственно сортировка */ void quick_sort(int i, int j) {   int ind = findpivot(i, j);   if (ind != -1)   {     int piv = a[ind];     int k = partition(i, j, piv);     quick_sort(i, k-1);     quick_sort(k, j);   } }; int main(int argc, char* argv[]) {   for (int i = 0; i <= 7; i++) cin >> a[i];   quick_sort(0, 7);    for (int i = 0; i <= 7; i++) cout << a[i] << " ";   cout << endl << endl;   cout << "Kol-vo sravneniy: " << c << endl;   cout << "Kol-vo perestanovok: " << e << endl;   getch();   return 0; }

Если кто может посоветовать правильно ли я считаю или нет, то буду очень рад.

Этот кусок

Код

for (k = i + 1; k <= j; k++)       {         c++;     if (a[k] > a[i])         {              c++;        return k;         }         else         {           if (a[k] < a[i])           {             c++;             return i;           }         }

я бы заменил так:

Код

for (k = i + 1; k <= j; k++){ c++; return a[k] > a[i]?k:i; }

Зачем запихивать инкремент с в условие? Все равно сравнение будет, хотя это только с точки зрения объема кода...

А это:

Код

// swap elements         int t = a[l]; a[l] = a[r]; a[r] = t;

лучше записать так:

Код

a[l]^=a[r]^=a[l]^=a[r];

Лишняя переменная там не нужна.

Цитата(kometa_triatlon @ 16.5.2005, 22:36)

лучше записать так: a[l]^=a[r]^=a[l]^=a[r];

Мне эта запись очень непонятна. Сам бы я до такого не додумался. Может объяснишь в чём тут суть? Операторы работают слева направо?

Код

for (k = i + 1; k <= j; k++){ c++; return a[k] > a[i]?k:i; }

Так не пойдёт. Должно срабатывать только если число строго меньше или строго больше. Этот код срабатывает (возвращает i) даже если числа равны.

Насчет записи - забей, она мне сама непонятна Нам ее препод дал, чтобы мы делали перестановки так. Довольно красиво, правда?

Цитата

Так не пойдёт. Должно срабатывать только если число строго меньше или строго больше. Этот код срабатывает (возвращает i) даже если числа равны.

С чего ты взял?
Извини меня, чтобы узнать, равны числа или нет, их нужно сравнить. Или у тебя есть сравнения двух сортов?

Цитата(kometa_triatlon @ 17.5.2005, 01:24)

С чего ты взял? Извини меня, чтобы узнать, равны числа или нет, их нужно сравнить. Или у тебя есть сравнения двух сортов?

Конечно, может я и ошибаюсь, но запись:

Код

return a[k] > a[i]?k:i;

возвращает k, если a[k] больше чем a[i], иначе возвращается i. Если чило a[k] == a[i], то это и есть тот случай - иначе (else). Или я не прав!?

Цитата(Yanis @ 17.5.2005, 08:06)

Конечно, может я и ошибаюсь, но запись: Код return a[k] > a[i]?k:i; возвращает k, если a[k] больше чем a[i], иначе возвращается i. Если чило a[k] == a[i], то это и есть тот случай - иначе (else). Или я не прав!?

ты не ошибаешься, все именно так

Значит ни у кого этот код и решение моей задачи не вызывает нареканий? Тогда буду доделывать дальше. Всем спасибо.

Цитата(kometa_triatlon @ 17.5.2005, 00:36)

лучше записать так: лучше записать так: Код a[l]^=a[r]^=a[l]^=a[r]; Насчет записи - забей, она мне сама непонятна smile Нам ее препод дал, чтобы мы делали перестановки так. Довольно красиво, правда?

Три последовательных XOR над целыми числами эквивалентны их обмену. Но это некошерно и фактически является undefined behaviour. Читать обсуждение здесь: http://rsdn.ru/Forum/Message.aspx?mid=439731&only=1
Преподу расскажи обязательно

Насчет красоты, по-моему, запись

Код

std::swap(a[l], a[r]);

рулит И, скорее всего, быстрее будет. И сработает для любых типов, а не только целочисленных.

Это сообщение отредактировал(а) Void - 17.5.2005, 19:31

To Void
Спасибо. Про undefined behaviour ничего не понял, потому что не умею пользоваться ихним форумом ;) Но из названия я вижу, что это типа "не объявленное поведение" или скорее "не предсказуемое поведение".

To Void
Спасибо. Про undefined behaviour ничего не понял, потому что не умею пользоваться ихним форумом ;) Но из названия я вижу, что это типа "не объявленное поведение" или скорее "не предсказуемое поведение".

Это сообщение отредактировал(а) Yanis - 17.5.2005, 21:49

Void
Как вызов функции может сработать быстрее? А насчет undefined, то у меня такого никогда не было. Если с его компилятором работает нормально, так почему бы и нет?

Цитата

возвращает k, если a[k] больше чем a[i], иначе возвращается i. Если чило a[k] == a[i], то это и есть тот случай - иначе (else). Или я не прав!?

Вот елки... Действительно
Просто я подумал, что это как обычно поиск максимального элемента, вот и сработал рефлекс
Ну если продолжать тему, то правильно будет так:

Код

a[k] > a[i]?k:(a[i]>a[k]?i:(-1));

И насчет количества сравнений: допустим два числа равны, проверяется первое условие (происходит сравнение), не срабатывает, потом второе (опять сравнение), опять не срабатывает. В итоге прошло два сравнения, а их счетчик не увеличился...

Цитата(kometa_triatlon @ 18.5.2005, 02:32)

Как вызов функции может сработать быстрее?

Есть такое понятие, как inline-подстановка. И для такой простой функции, как std::swap она выполняется практически всегда. По ссылке все-таки стоит сходить - там приводили asm-листинги, во что скомплировался тот и другой вариант. Как и следовало ожидать, компилятор оказался умнее. Преждевременная оптимизация - корень всех бед (с) Кнут, кажется.

Цитата(kometa_triatlon @ 18.5.2005, 02:32)

А насчет undefined, то у меня такого никогда не было. Если с его компилятором работает нормально, так почему бы и нет?

Ну что мы теперь, на конкретный компилятор будем завязываться? Зачем? Это действительно отработает как надо на большинстве компиляторов для целочисленных типов - но завтра понадобится сортировка для double или сложных объектов - что делать будем?

Void
Ну насчет inline я не знал Тогда конечно да.

А насчет компилятора - это я к тому, что в данном случае ( для этого типа, на этом компиляторе ) можно спокойно использовать. Сомневаюсь, что это именно такой:

Цитата

у что мы теперь, на конкретный компилятор будем завязываться? Зачем? Это действительно отработает как надо на большинстве компиляторов для целочисленных типов - но завтра понадобится сортировка для double или сложных объектов - что делать будем?

случай