Алгоритм быстрой сортировки
Здесь можно прочитать перевод статьи об алгоритме быстрой сортировки с сайта Khan Academy. Процедура разбиения в той статье описана схематично, но для того чтобы написать правильно работающую программу, нужна математически точная формулировка данной процедуры. Это важно для обработки крайних случаев (когда группа L или G является пустой).
Сам алгоритм быстрой сортировки не нуждается в специальном математическом анализе, так как он достаточно понятен. Рассмотрим процедуру разбиения.
На входе имеем подмассив \(A[p..r]\), \(p<r\). На выходе элементы этого подмассива должны быть переставлены таким образом, что \(A'[q] = A[r], \; p \leq q \leq r, \;\; A'[i] \leq A'[q], \; i < q,\;\; A'[i] > A'[q], \; i > q\). Здесь через \(A'[i]\) обозначены значения элементов массива по окончании процедуры разбиения.
Сформулируем алгоритм в виде псевдокода:
\(q = {\rm partition}(@A, p, r)\)
$q \leftarrow p$;
for $j \leftarrow p$ to $r - 1$
// инвариант цикла:
// $p \leq q \leq j, \;\; A[i] \leq A[r], \; p \leq i \leq q-1, \;\; A[i] > A[r], \; q \leq i \leq j-1$
if ($A[j] \leq A[r]$)
$A[j] \leftrightarrow A[q]$;
$q \leftarrow q + 1$;
endif
// $p \leq q \leq j + 1, \;\; A[i] \leq A[r], \; p \leq i \leq q-1, \;\; A[i] > A[r], \; q \leq i \leq j$
endfor
$A[r] \leftrightarrow A[q]$;
Символ @ означает, что функция может изменять значения элементов массива $A$.
Докажем, что если выполняется инвариант, указанный в начале цикла (начальное условие), то после выполнения тела цикла будет выполняться условие, указанное в конце цикла (конечное условие).
Обозначим через $A[i]$ и $q$ значения соответствующих переменных перед выполнением тела цикла, а через $A'[i]$ и $q'$ - их значения после выполнения тела цикла.
Если $A[j] > A[r]$, то тело условного оператора не выполнится, $q' = q$, $A'[i] = A[i]$, и начальное условие сохранится:
$$p \leq q' \leq j, \;\; A'[i] \leq A'[r], \; p \leq i \leq q'-1, \;\; A'[i] > A'[r], \; q' \leq i \leq j-1.$$
Для завершения доказательства конечного условия заметим, что $A'[i] > A'[r]$ при $i = j$.
Теперь рассмотрим случай, когда $A[j] \leq A[r]$ и тело условного оператора выполняется. Тогда $q' = q + 1$, $A'[j] = A[q]$, $A'[q] = A[j]$, $A'[i] = A[i]$, если $i \neq j$, $i \neq q$.
Из начального условия вытекает, что
$$p \leq q' \leq j+1, \;\; A'[i] \leq A'[r], \; p \leq i \leq q'-2, \;\; A'[i] > A'[r], \; q' \leq i \leq j-1.$$
Кроме того, заметим, что $A'[q'-1] = A'[q] = A[j] \leq A'[r]$ и $A'[j] = A[q] > A[r]$.
Конечное условие доказано.
Таким образом, после завершения выполнения цикла будут выполнены условия:
$$p \leq q \leq r, \;\; A[i] \leq A[r], \; p \leq i \leq q-1, \;\; A[i] > A[r], \; q \leq i \leq r-1,$$
а после выполнения последнего оператора -
$$A[i] \leq A[q], \; p \leq i \leq q - 1, \;\; A[i] > A[q], \; q+1 \leq i \leq r.$$
Корректность процедуры разбиения доказана.
Вы спросите: зачем так подробно расписывать математические выкладки, если можно просто сесть и написать код, а потом его протестировать? Ответ: конечно, можно. Однако при рабоче-крестьянском подходе к программированию вы будете в некоторой степени полагаться на авось. Если ваши алгоритмы будут несложными, то вам не нужен подробный анализ. Но при усложнении программируемых вычислений важность теоретического анализа возрастает, а возможность проверить вашу программу на тестах снижается.
В конце концов, алгоритм - это то же самое, что и математическая формула, только многоуровневая. Если все математические формулы принято строго выводить и доказывать, то почему бы не поступать так же с алгоритмами? Точная математическая формулировка и строгое доказательство алгоритма повышают уверенность в правильности написанной программы.
А как программируете вы? Поделитесь в комментариях.
Сам алгоритм быстрой сортировки не нуждается в специальном математическом анализе, так как он достаточно понятен. Рассмотрим процедуру разбиения.
На входе имеем подмассив \(A[p..r]\), \(p<r\). На выходе элементы этого подмассива должны быть переставлены таким образом, что \(A'[q] = A[r], \; p \leq q \leq r, \;\; A'[i] \leq A'[q], \; i < q,\;\; A'[i] > A'[q], \; i > q\). Здесь через \(A'[i]\) обозначены значения элементов массива по окончании процедуры разбиения.
Сформулируем алгоритм в виде псевдокода:
\(q = {\rm partition}(@A, p, r)\)
$q \leftarrow p$;
for $j \leftarrow p$ to $r - 1$
// инвариант цикла:
// $p \leq q \leq j, \;\; A[i] \leq A[r], \; p \leq i \leq q-1, \;\; A[i] > A[r], \; q \leq i \leq j-1$
if ($A[j] \leq A[r]$)
$A[j] \leftrightarrow A[q]$;
$q \leftarrow q + 1$;
endif
// $p \leq q \leq j + 1, \;\; A[i] \leq A[r], \; p \leq i \leq q-1, \;\; A[i] > A[r], \; q \leq i \leq j$
endfor
$A[r] \leftrightarrow A[q]$;
Символ @ означает, что функция может изменять значения элементов массива $A$.
Докажем, что если выполняется инвариант, указанный в начале цикла (начальное условие), то после выполнения тела цикла будет выполняться условие, указанное в конце цикла (конечное условие).
Обозначим через $A[i]$ и $q$ значения соответствующих переменных перед выполнением тела цикла, а через $A'[i]$ и $q'$ - их значения после выполнения тела цикла.
Если $A[j] > A[r]$, то тело условного оператора не выполнится, $q' = q$, $A'[i] = A[i]$, и начальное условие сохранится:
$$p \leq q' \leq j, \;\; A'[i] \leq A'[r], \; p \leq i \leq q'-1, \;\; A'[i] > A'[r], \; q' \leq i \leq j-1.$$
Для завершения доказательства конечного условия заметим, что $A'[i] > A'[r]$ при $i = j$.
Теперь рассмотрим случай, когда $A[j] \leq A[r]$ и тело условного оператора выполняется. Тогда $q' = q + 1$, $A'[j] = A[q]$, $A'[q] = A[j]$, $A'[i] = A[i]$, если $i \neq j$, $i \neq q$.
Из начального условия вытекает, что
$$p \leq q' \leq j+1, \;\; A'[i] \leq A'[r], \; p \leq i \leq q'-2, \;\; A'[i] > A'[r], \; q' \leq i \leq j-1.$$
Кроме того, заметим, что $A'[q'-1] = A'[q] = A[j] \leq A'[r]$ и $A'[j] = A[q] > A[r]$.
Конечное условие доказано.
Таким образом, после завершения выполнения цикла будут выполнены условия:
$$p \leq q \leq r, \;\; A[i] \leq A[r], \; p \leq i \leq q-1, \;\; A[i] > A[r], \; q \leq i \leq r-1,$$
а после выполнения последнего оператора -
$$A[i] \leq A[q], \; p \leq i \leq q - 1, \;\; A[i] > A[q], \; q+1 \leq i \leq r.$$
Корректность процедуры разбиения доказана.
Вы спросите: зачем так подробно расписывать математические выкладки, если можно просто сесть и написать код, а потом его протестировать? Ответ: конечно, можно. Однако при рабоче-крестьянском подходе к программированию вы будете в некоторой степени полагаться на авось. Если ваши алгоритмы будут несложными, то вам не нужен подробный анализ. Но при усложнении программируемых вычислений важность теоретического анализа возрастает, а возможность проверить вашу программу на тестах снижается.
В конце концов, алгоритм - это то же самое, что и математическая формула, только многоуровневая. Если все математические формулы принято строго выводить и доказывать, то почему бы не поступать так же с алгоритмами? Точная математическая формулировка и строгое доказательство алгоритма повышают уверенность в правильности написанной программы.
А как программируете вы? Поделитесь в комментариях.
Комментарии
Отправить комментарий