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

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

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

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

Операторы языка C#

Состав операторов языка C#, их синтаксис и семантика унаследованы от языка С++. Как и положено, потомок частично дополнил состав, переопределил синтаксис и семантику отдельных операторов, постарался улучшить характеристики языка во благо программиста. Посмотрим, насколько это удалось языку C#.

Оператор присваивания

Как в языке С++, так и в C# присваивание формально считается операцией. Вместе с тем запись:

X= expr;

следует считать настоящим оператором присваивания, так же, как и одновременное присваивание со списком переменных в левой части:

X1 = X2 = … = Xk = expr;

В отличие от языка C++ появление присваивания в выражениях C# хотя и допустимо, но практически не встречается. Например, запись:

if(x = expr)…

часто используемая в С++, в языке C# в большинстве случаев будет воспринята как ошибка еще на этапе компиляции.

В предыдущих лекциях семантика присваивания разбиралась достаточно подробно, поэтому сейчас я на этом останавливаться не буду. Read more »