Раздел для рандомизированной быстрой сортировки (с несколькими уникальными элементами) - PullRequest
Новая
       9

Раздел для рандомизированной быстрой сортировки (с несколькими уникальными элементами)

1 голос
/ 02 марта 2020

Мне было поручено написать функцию разбиения для рандомизированной быстрой сортировки с несколькими элементами (оптимизируя ее, добавив 3 раздела вместо 2). Я попытался реализовать свою версию и обнаружил, что она не проходит тестовые случаи.

Однако, используя версию раздела одноклассников, кажется, работает. Концептуально, я не вижу разницы между его и моей, и я не могу сказать, что это с моей версией, которая заставляет его ломаться. Я написал это с концепцией «он» (я думаю), которая включает использование счетчиков (j и k) для разделения массивов на 3.

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

Для сравнения, будет 3 блока кода, ниже приведен фрагмент моей версии раздела, после которого будет версия моих одноклассников и, наконец, будет фактическим алгоритмом, который запускает наш раздел.

Моя версия (не работает) 

vector<int> partition2(vector<int> &a, int l, int r) {
  int x = a[l];
  int j = l;
  int k = r;

  vector<int> m(2);

  // I've tried changing i = l + 1
  for (int i = l; i <= r; i++) {
    if (a[i] < x) {
      swap(a[i], a[j]);
      j++;
    }

    else if (a[i] > x) {
      swap(a[i], a[k]);
      k--;
    }
  }

  // I've tried removing this
  swap(a[l], a[j]);

  m[0] = j - 1;
  m[1] = k + 1;

  return m;
}

Мои одноклассники '(который работает) 

vector<int> partition2(vector<int> &a, int l, int r) {
    int x = a[l];
    int p_l = l;
    int i = l;
    int p_e = r;
    vector<int> m(2);
    while (i <= p_e) {
        if (a[i] < x) {
            swap(a[p_l], a[i]);
            p_l++;
            i++;
        } else if (a[i] == x) {
            i++;
        } else {
            swap(a[i], a[p_e]);
            p_e -= 1;
        }
        m[0] = p_l - 1;
        m[1] = p_e + 1;
    }
    return m;
}

Фактический алгоритм быстрой сортировки 

void randomized_quick_sort(vector<int> &a, int l, int r) {
  if (l >= r) {
    return;
  }

  int k = l + rand() % (r - l + 1);
  swap(a[l], a[k]);
  vector<int> m = partition2(a, l, r);

  randomized_quick_sort(a, l, m[0]);
  randomized_quick_sort(a, m[1], r);
}

1 Ответ

2 голосов
/ 02 марта 2020

Разница между двумя функциями для трехстороннего разбиения заключается в том, что ваш код продвигается на i при каждом проходе через l oop, но функция вашего одноклассника продвигается i только тогда, когда значение в позиции i равно меньше или равно оси.

Давайте go через массив примеров. Первое значение, 3, это стержень. Буквы обозначают положение переменных после каждого прохода через l oop. 

j               k
3   1   5   2   4
    i

Следующее значение меньше: поменяйте его на левую сторону и продвиньтесь j: 

    j           k
1   3   5   2   4
        i

Следующее значение 5 больше, поэтому оно идет вправо: 

    j       k
1   3   4   2   5
            i

Это плохой ход: ваш i теперь пропустил 4, что должно go к правой части тоже. Код вашего одноклассника не продвигает i здесь и ловит 4 в следующем проходе.

Ваш l oop имеет несколько инвариантов , что должно быть верно после всех проходов:

  • Все элементы с индексом ниже i меньше, чем сводка.
  • Все элементы с индексом больше k больше, чем сводка.
  • Все элементы с индексом от j до i - 1 равны оси.
  • Все элементы от i до k еще не обработаны.

Вы также можете определить условия l oop из этого:

  • Шарнир - самый левый элемент по определению, потому что функция быстрой сортировки меняет его там. Он должен принадлежать к группе элементов, равных оси, поэтому вы можете начать свой l oop с l + 1.
  • Все элементы, начиная с k, уже находятся в правильной части массив. Это означает, что вы можете остановиться, когда i достигнет k. Пройдя дальше, вы без необходимости поменяете местами элементы внутри раздела «больше чем», а также переместитесь на k, что вернет неправильные границы раздела.
...