Доказательство правильности сортировки «разделяй и властвуй»

Предположим, у нас есть метод сортировки:

void DD_sort(int a[], int x, int y, int size_a)
{
   if(x == y){
      return;
   }
   else if(y == x+1){
      if(a[x] > a[y]){
         /* swap the content */
         return;
      }
   }
   else{
      int s = floor((y+1-x)/3);
      DD_sort(a, x, y-s, s);
      DD_sort(a, x+s, y, s);
      DD_sort(a, x, y-s, s);
   }  
}

Какими методами можно показать, что алгоритм сортировки правильно или неправильно сортирует массив a? Существуют ли системные подходы к этой проблеме? Я понимаю, что это работает в случае size_a == 1 и size_a == 2, но если size_a равно, скажем, 30, то мы рекурсивно вызываем метод сортировки на ~2/3 размера отброшенного массива. Похоже, что это работает, но я не уверен, как это официально показать.


c++ algorithm proof-of-correctness correctness
person Bob John    schedule 22.09.2014    source источник
comment
каковы начальные значения, данные x и y?   -  person Emanuele Paolini    schedule 22.09.2014
comment
@EmanuelePaolini Это x = 0 и y = size_a-1.   -  person Bob John    schedule 22.09.2014
comment
Что такое size_a? Какова цель этого параметра, когда он нигде в функции не используется?   -  person AnT    schedule 22.09.2014
comment
@AndreyT используется в другой части функции, которую я удалил. Прости за это.   -  person Bob John    schedule 22.09.2014
comment
floor здесь кажется шумом: целочисленное деление не даст никаких десятичных цифр.   -  person dyp    schedule 22.09.2014

Ответы (1)


arrow_upward
1
arrow_downward

Вы должны доказать, что эти строки

  DD_sort(a, x, y-s, s);
  DD_sort(a, x+s, y, s);
  DD_sort(a, x, y-s, s);

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

Это верно, потому что: первый вызов гарантирует, что более крупные элементы s выйдут за пределы индекса y-s-s >= x+s. Таким образом, второй вызов отправит их в конец массива.

Все эти рассуждения верны, если длина массива ровно 3*s. Это остается верным, если s меньше трети длины, фактически, если s меньше, отсортированные подмножества больше.

person Emanuele Paolini    schedule 22.09.2014