Интернет-журнал "Домашняя лаборатория", 2007 №9 - Журнал «Домашняя лаборатория»

соблюдением правил. Выбор выполняется почти автоматически, поскольку слияние частных решений не нарушает правил. В этом еще одна мощь рекурсии.

Решение исходной задачи свелось к решению двух подзадач и одному ходу. В отличие от задачи сортировки слиянием, обе подзадачи имеют не половинный размер, а размер, лишь на единицу меньший исходного. Это, казалось бы, незначительное изменение приводит к серьезным потерям эффективности вычислений. Если сложность в первом случае имела порядок n*iog(n), то теперь она становится экспоненциальной. Давайте проведем анализ временных затрат для ханойских башен (и всех задач, сводящихся к решению двух подзадач размерности n-1). Подсчитаем требуемое число ходов T(n). с учетом структуры решения:

T(n) = 2Т(n-1) +1

Простое доказательство по индукции дает:

T(n) = 2n-1 + 2n-2 +… + 2 +1 = 2n -1

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

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

Продолжая тему рекурсии, познакомимся с реализацией на C# еще одного известного рекурсивного алгоритма, применяемого при сортировке массивов. Описанный ранее рекурсивный алгоритм сортировки слиянием имеет один существенный недостаток — для слияния двух упорядоченных массивов за линейное время необходима дополнительная память. Разработанный Ч. Хоаром метод сортировки, получивший название быстрого метода сортировки — Quicksort, не требует дополнительной памяти.

Хотя этот метод и не является самым быстрым во всех случаях, но на практике он обеспечивает хорошие результаты. Нужно отметить, что именно этот метод сортировки встроен в класс System.Array.

Идея алгоритма быстрой сортировки состоит в том, чтобы выбрать в исходном массиве некоторый элемент M, затем в начальной части массива собрать все элементы, меньшие M. Так появляются две подзадачи размерности — k и n-k, к которым рекурсивно применяется алгоритм. Если в качестве элемента M выбирать медиану сортируемой части массива, то обе подзадачи имели бы одинаковый размер и алгоритм быстрой сортировки был бы оптимальным по времени работы. Но расчет медианы требует своих затрат времени и усложняет алгоритм. Поэтому обычно элемент M выбирается случайным образом. В этом случае быстрая сортировка оптимальна лишь в среднем, а для плохих вариантов (когда в качестве M всякий раз выбирается минимальный элемент) имеет порядок n2.

Несмотря на простоту идеи, алгоритм сложен в своей реализации, поскольку весь построен на циклах и операторах выбора. Я проводил построение алгоритма параллельно с обоснованием его корректности, введя инварианты соответствующих циклов. Текст обоснования встроен в текст метода. Приведу его, а затем дам некоторые объяснения. Вначале, как обычно, приведу нерекурсивную процедуру, вызывающую рекурсивный метод:

/// <summary>

/// Вызывает рекурсивную процедуру QSort,

/// передавая ей границы сортируемого массива.

/// Сортируемый массив tower1 задается

/// соответствующим полем класса, public void Quicksort ()

{

    QSort(0,size-1);

}

Вот чистый текст рекурсивной процедуры быстрой сортировки Хоара:

void QSort(int start, int finish)

{

    if (start!= finish)

    {

       int ind = rnd.Next(start,finish);

       int item = tower1[ind];

       int ind1 = start, ind2 = finish;

       int temp;

       while (ind1 <=ind2)

       {

           while((ind1 <=ind2)&& (tower1[ind1] < item)) ind1++;

           while ((ind1 <=ind2)&&(tower1[ind2] >= item)) ind2--;

           if (ind1 < ind2)

           {

               temp = tower1[ind1]; tower1[ind1] = tower1[ind2];

                tower1[ind2] = temp; ind1++; ind2--;

            }

         }

         if (ind1 == start)

         {

             temp = tower1[start]; towerl[start] = item;

             tower1[ind] = temp;

             QSort(start+1,finish);

         }

         else

         {

             QSort(start,ind1-1);

             QSort(ind2+1, finish);

         }

     }

}//QuckSort

Проведите эксперимент — закройте книгу и попробуйте написать эту процедуру самостоятельно. Если вам удастся сделать это без ошибок и она пройдет у вас с первого раза, то вы — блестящий программист и вам нужно читать другие книги. Я полагаю, что в таких процедурах ошибки неизбежны и для их исправления требуется серьезная отладка. Полагаю также, что помимо обычного тестирования полезно применять обоснование корректности, основанное на предусловиях и постусловиях, инвариантах цикла. Проектируя эту процедуру, я параллельно встраивал обоснование ее корректности. Это не строгое доказательство, но, дополняя тестирование, оно достаточно, чтобы автор поверил в корректность процедуры и представил ее на суд зрителей, как это сделал я.

/// <summary>

/// Небольшая по размеру процедура содержит три

/// вложенных цикла while, два оператора if и рекурсивные

/// вызовы. Для таких процедур задание инвариантов и

/// обоснование корректности облегчает отладку.

/// </summary>

/// <param name="start">нaчaльный индекс сортируемой части

/// массива tower</param>

/// <param name="finish">конечный индекс сортируемой части

/// массива tower</param>

/// Предусловие: (start <= finish)

/// Постусловие: массив tower отсортирован по возрастанию

void QSort (int start, int finish)

{

    if (start!= finish)

    //если (start = finish), то процедура ничего не делает,

    //но постусловие выполняется, поскольку массив из одного

    //элемента отсортирован по определению. Докажем истинность

    //постусловия для массива с числом элементов >1.

    {

        int ind = rnd.Next(start,finish);

        int item = tower1[ind];

        int ind1 = start, ind2 = finish;

        int temp;

    /// Введем три непересекающихся множества:

    /// S1: {tower1(i), start <= i =< ind1-1}

    /// S2: {tower1(i), ind1 <= i =< ind2}

    /// S3: {tower1(i), ind2+1 <= i =< finish}

    /// Введем следующие логические условия,

    /// играющие роль инвариантов циклов нашей программы:

    /// Р1: объединение S1, S2, S3 = towerl

    /// Р2: (S1 (i) < item) Для всех элементов S1

    /// Р3: (S3 (i) >= item) Для всех элементов S3

    /// Р4: item — случайно выбранный элемент tower1

    /// Нетрудно видеть, что все условия становятся

    /// истинными после завершения инициализатора цикла.

    /// Для пустых множеств S1 и S3 условия Р2 и РЗ

    /// считаются истинными по определению.

    /// Inv = P1 & Р2 & РЗ & Р4

       while (ind1 <=ind2)

       {

           while((ind1 <=ind2)&& (tower1[ind1] < item)) ind1++;

          // (Inv == true) & ~B1 (B1 — условие цикла while)

          while ((ind1 <=ind2)&& (tower1[ind2] >= item))