Как вы доказываете или иллюстрируете, что быстрая сортировка слиянием является нестабильным алгоритмом? - PullRequest
Новая
       41

Как вы доказываете или иллюстрируете, что быстрая сортировка слиянием является нестабильным алгоритмом?

3 голосов
/ 14 июня 2019

Проблема озадачила меня, когда я прочитал задачу 2.2.10 главы 2 Алгоритмов, 4-е издание.В книге говорится, что результаты алгоритма быстрого слияния нестабильны, и я не могу найти доказательства этого. Помогите мне, спасибо! 

public static void sort(Comparable[] a, int lo, int hi){
    if hi <= lo {
    return;
    }
    int mid = lo + (hi - lo) / 2;
    sort(a, lo, mid);
    sort(a, mid+1, hi);
    merge(a, lo, mid, hi);
}

// Why is the result of this sort not stable
private static void merge(Comparable[] a, int lo, int mid, int hi) { 
   for (int i = lo; i <= mid; i++)
      aux[i] = a[i]; 

   for (int j = mid+1; j <= hi; j++)
      aux[j] = a[hi-j+mid+1];

   int i = lo, j = hi; 
   for (int k = lo; k <= hi; k++) 
      if (less(aux[j], aux[i])) a[k] = aux[j--];
      else                      a[k] = aux[i++];
}

Я не могу найти результаты нестабильными, как я могу получитьк этому?

Ответы [ 3 ]

4 голосов
/ 14 июня 2019

Алгоритм сортировки, который сохраняет «равные» элементы в одном и том же порядке, считается стабильным. Таким образом, unstable означает: у вас есть несколько одинаковых элементов, и когда вы сортируете общий список / массив, выходные данные этой сортировки имеют эти равные элементы (потенциально), которые отображаются в другом порядке. .

Предположим, например, что у вас есть класс Person, и равенство реализовано для того, чтобы просматривать только фамилию и игнорировать имя.

Теперь предположим, что у вас есть два объекта Person, представляющих "John Doe" и "Jane Doe". Они находятся в вашем несортированном списке в таком порядке.

Стабильно означало бы: вы всегда заканчиваете тем, что «Джон Доу» появляется перед «Джейн Доу». С нестабильной сортировкой у вас нет такой гарантии.

Другими словами: вам нужно создать класс, который имеет как минимум два атрибута. Затем вам нужно определить compareTo(), чтобы полагаться только на одно из двух свойств.

Затем вы создаете некоторый пример списка объектов этого класса, и затем вы экспериментируете достаточно долго, пока не найдете пример, где отсортированный список показывает, что равные объекты изменили порядок.

Другими словами: создайте список (p1, p2, p3, p4, ...), отсортируйте его, а затем найдите результат, который, возможно, говорит ... p4, p3 ... хотя p4 и p3 считаются "равными".

Наконец: на самом деле это был бы очень хороший вариант использования некоторой среды тестирования на основе свойств , такой как QuickCheck . Используя такой фреймворк, вам необходимо:

  • создать «генератор», который может создавать «случайные» объекты некоторого класса, по которому вы позже сортируете (где вы наклоняете генератор, чтобы убедиться, что вы получаете кучу «равных» объектов из него)
  • затем заставьте каркас проверить базовое «утверждение» о том, что порядок «равных» объектов до и после сортировки не должен изменяться.

А затем заставьте фреймворк творить чудеса ...

1 голос
/ 15 июня 2019

Для доказательства нестабильности алгоритма достаточно одного контрпримера: рассмотрим шаги, предпринятые для сортировки массива из 4 элементов A B C D, которые сравниваются равными для предиката less.

  • sort(a, 0, 3) рекурсив на 2 подмассивах:
  • sort(a, 0, 1), который рекурсивно повторяется
  • sort(a, 0, 0), который немедленно возвращается
  • sort(a, 1, 1), который немедленно возвращается
  • merge(a, 0, 0, 1) не меняет порядок A B
  • sort(a, 2, 3), который повторяется на
  • sort(a, 2, 2), который немедленно возвращается
  • sort(a, 3, 3), который возвращается немедленно
  • merge(a, 2, 2, 3) не меняет порядок C D
  • merge(a, 0, 1, 3) копирует элементы A B C D в t в порядке A B D C, затем все сравнения в цикле слиянияоценивать как ложное, следовательно, элементы, скопированные обратно в a, находятся в том же порядке, скопированы из t[i++]: A B D C, доказывая нестабильность алгоритма сортировки, то есть: относительный порядок элементов, сравнивающих равные, не сохраняется.
0 голосов
/ 15 июня 2019

Чтобы доказать, что алгоритм сортировки нестабилен, требуется только найти один сбой.Доказательство того, что алгоритм сортировки стабилен, будет более сложным.Один из способов проверить наличие ошибок - использовать массив целых чисел и разделить их на две части: верхние 8 битов - это псевдослучайное значение, а младшие 24 бита равны индексу целого числа (от 0 до count-1).Затем выполните сортировку, используя только 8 старших бит для сравнения, например, в C: 

    if((b[j]&0xff000000) < (b[i]&0xff000000)) ...

После завершения сортировки убедитесь, что массив в порядке, используя все 32 бита.

Используя этот метод, я смог подтвердить, что этот вариант сортировки слиянием нестабилен.

Очевидно, причина, по которой это называется "быстрой" сортировкой слиянием, заключается в том, что нет проверки концазапустить при выполнении слияния.Левый цикл копируется в aux [] в прямом порядке от lo до mid, а правый цикл копируется в aux [] в обратном порядке от hi до mid + 1.Затем объединение начинается с обоих концов (lo и hi) и продолжается к середине (mid и mid + 1), левый ход, используя i вперед от lo до середины, правый ход назад, используя j от высокого до среднего + 1.Поскольку нет проверки для достижения конца цикла, i может быть увеличен выше среднего (потенциальная проблема стабильности), или j может быть уменьшен ниже середины + 1 (не стабильность)выпуск).Стабильность нарушается в случае, когда i увеличивается выше середины, и aux [mid + 1] == aux [mid + 2], два самых высоких элемента из исходного правого прогона.В этом случае элементы копируются в обратном порядке.

Хотя книга назвала это быстрой сортировкой слиянием, было бы быстрее избежать копирования данных в aux и вместо этого изменить направление слияния на основе уровнярекурсии.Сверху вниз, это можно сделать с помощью однотипной копии и замены ссылок на массивы в рекурсивных вызовах, например, в этом примере вики:

https://en.wikipedia.org/wiki/Merge_sort#Top-down_implementation

Первоначальной копии можно избежать, используяпара взаимно рекурсивных функций, одна из которых заканчивается результатом в a [], а другая - результатом b [].

Немного быстрее - сортировка слиянием снизу вверх, так как она пропускает все рекурсивное разбиение и сохранение индексов в стеке.В этом случае направление слияния основывается на проходе слияния.Чтобы сохранить количество проходов четным, можно заранее проверить счетчик нечетных проходов, и пары элементов поменялись местами перед началом первого прохода сортировки слиянием снизу вверх.

...