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]; |