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

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

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

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

Время жизни и область видимости переменных

Давайте рассмотрим такие важные характеристики переменных, как время их жизни и область видимости. Зададимся вопросом, как долго живут объявленные переменные и в какой области программы видимы их имена? Ответ зависит от того, где и как, в каком контексте объявлены переменные. В языке C# не так уж много возможностей для объявления переменных, пожалуй, меньше, чем в любом другом языке. Открою «страшную» тайну, — здесь вообще нет настоящих глобальных переменных. Их отсутствие не следует считать некоторым недостатком C#, это достоинство языка. Но обо всем по порядку.

Поля

Первая важнейшая роль переменных, — они задают свойства структур, интерфейсов, классов. В языке C# такие переменные называются полями (fields). Структуры, интерфейсы, классы, поля — рассмотрению этих понятий будет посвящена большая часть этой книги, а сейчас сообщу лишь некоторые минимальные сведения, связанные с рассматриваемой темой. Поля объявляются при описании класса (и его частных случаев — интерфейса, структуры). Когда конструктор класса создает очередной объект — экземпляр класса, то он в динамической памяти создает набор полей, определяемых классом, и записывает в них значения, характеризующие свойства данного конкретного экземпляра. Так что каждый объект в памяти можно рассматривать как набор соответствующих полей класса со своими значениями. Время существования и область видимости полей определяется объектом, которому они принадлежат. Объекты в динамической памяти, с которыми не связана ни одна ссылочная переменная, становятся недоступными. Реально они оканчивают свое существование, когда сборщик мусора (garbage collector) выполнит чистку «кучи». Для значимых типов, к которым принадлежат экземпляры структур, жизнь оканчивается при завершении блока, в котором они объявлены.

Есть одно важное исключение. Некоторые поля могут жить дольше. Если при объявлении класса поле объявлено с модификатором static, то такое поле является частью класса и единственным на все его экземпляры. Поэтому static-поля живут так же долго, как и сам класс. Более подробно эти вопросы будут обсуждаться при рассмотрении классов, структур, интерфейсов. Read more »