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

Продолжая тему рекурсии, познакомимся с реализацией на 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]; tower1[start] = item;

tower1[ind] = temp;

QSort(start+1,finish);

}

else

{

QSort(start,ind1-1);

QSort(ind2+1, finish);

}

}

}// QuickSort

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

/// <summary>

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

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

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

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

/// </summary>

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

/// массива 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}

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

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

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

/// P1: объединение S1, S2, S3 = tower1

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

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

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

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

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

/// Для пустых множеств S1 и S3 условия P2 и P3

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

/// Inv = P1 & P2 & P3 & P4

while (ind1 <=ind2)

{

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

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

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

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

if (ind1 < ind2)

//Из Inv & ~B1 & ~B2 & B3 следует истинность:

//((tower1[ind1] >= item)&&(tower1[ind2]<item))==true.

//Это условие гарантирует, что последующий обмен

//элементов обеспечит выполнение инварианта Inv

{

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

tower1[ind2] = temp;

ind1++; ind2--;

}

//(Inv ==true)

}

//из условия окончания цикла следует: (S2 - пустое множество)

if (ind1 == start)

//В этой точке S1 и S2 - это пустые множества, -> //(S3 = tower1)

// Нетрудно доказать, что отсюда следует истинность:

//(item = min)

// Как следствие, можно минимальный элемент сделать первым,

// а к оставшемуся множеству применить рекурсивный вызов.

{

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

tower1[ind] = temp;

QSort(start+1,finish);

}

else

// Здесь оба множества S1 и S3 не пусты.

// К ним применим рекурсивный вызов.

{

QSort(start,ind1-1);

QSort(ind2+1, finish);

}

//Индукция по размеру массива и истинность инварианта

//доказывает истинность постусловия в общем случае.

}

}// QuickSort

Приведу некоторые пояснения к этому доказательству. Задание предусловия и постусловия процедуры QSort достаточно очевидно - сортируемый массив должен быть не пустым, а после работы метода должен быть отсортированным. Важной частью обоснования является четкое введение трех множеств - S1, S2, S3 - и условий, накладываемых на их элементы. Эти условия и становятся частью инварианта, сохраняющегося при работе различных циклов нашего метода. Вначале множества S1 и S3 пусты, в ходе вычислений пустым становится множество S2. Так происходит формирование подзадач, к которым рекурсивно применяется алгоритм. Особым представляется случай, когда множество S1 тоже пусто. Нетрудно показать, что эта ситуация возможна только в том случае, если случайно выбранный элемент множества, служащий критерием разбиения исходного множества на два подмножества, является минимальным элементом.

Почему обоснование полезно практически? Дело в том, что в данном алгоритме приходится следить за границами множеств (чтобы они не пересекались), за пустотой множеств (служащих условием окончания циклов), за выполнением условий, накладываемых на элементы множеств. Если явно не ввести эти понятия, то вероятность ошибки существенно возрастает. В заключение следует все-таки привести результат сортировки хотя бы одного массива.

Рис. 10.3.  Результаты быстрой сортировки массива