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

[coshmos]

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

Comments

[azzazzello]

Там же вроде в задании говорится, что просто меняете последний или медиану местами с первым элементом и все, дальше таже сортировка с pivot на первом месте.

[coshmos]

Всё равно выходит косячно (поэтому и спросил). Видимо у меня условия для рекурсии неправильные и нужно дальше отлаживать.

[azzazzello]

Ну у вас функция то массив хоть правильно сортирует?
while (i < j); - не должно ли быть здесь <=?

[sassa_nf]

Не, ну, тут зависит от того, right включительно или нет, но да, глюк с неучтённым индексом есть. Ну, и более навёрнутая ошибка тоже есть.

[sassa_nf]

да это ж ваще мрак. на кой столько раз элементы массива переписывать сюда-туда?

[coshmos]

Первоначально было так:
public static void qsort(int[] aToSort, int left, int right)
  {      
    numberOfComparisons += (right - left);
    int i = left;
    int j = right;
    int m = aToSort[left];
    do
    {
      while (aToSort[i] < m) ++i;
      while (aToSort[j] > m) --j;
      if (i <= j)
      {
        int temp = aToSort[i];
        aToSort[i] = aToSort[j];
        aToSort[j] = temp;
        i++; j--;
      }
    } while (i <= j);
    if (left < j) qsort(aToSort, left, j);
    if (i

* This source code was highlighted with Source Code Highlighter.

Но не проходило количество сравнений.

[coshmos]

Ответом на вопрос является поставленная задача.
Your recursive call begins with the pivot at the left end of the array segment you are partitioning. You go element-by element rightwards from the next one over. When you come across an element that's greater than the pivot, just go to the next one. When the element is less than the pivot, swap it with one nearer the beginning of the array. Keep doing this and when you get to the end, you have partitioned the array EXCEPT the pivot itself is still at the beginning. But you've been keeping track (with 'i' in Tim's slide) of the array position that separates "stuff less than the pivot" with "stuff greater than the pivot". So just swap the pivot with the rightmost array element that's less than it. Now you have "stuff less than the pivot" all together on the left and "stuff greater than the pivot" all together on the right - the inputs to your next set of recursive calls.

[sassa_nf]

ерунда, а не ответ. эта задача решается за не более чем N копирований (плюс-минус константа).

[sassa_nf]

"А это некоторые кейсы:
...
[2, 1]
First element as pivot : 1 comparisons.
Last element as pivot : 1 comparisons.
Median of 3 as pivot : 1 comparisons."

дык, вы хоть на результат сортировки этого кейса посмотрите.

[coshmos]

да, слона и не приметил

[yelenazadab]

http://www.youtube.com/watch?v=aMzgVshG6CI