Сообщения с тегом ‘start’
Список с курсором. Динамические структуры данных
Написано admin в 20 Июнь 2008 – 22:01 -Список с курсором. Динамические структуры данных
Добавим в проект классы, задающие динамические структуры данных. Конечно, можно было бы воспользоваться стандартными… Но для обучения крайне полезно уметь создавать собственные классы, задающие такие структуры данных. Список с курсором – один из важнейших образцов подобных классов%:
using System;
namespace Shapes Read more »
Tags: elem, empty, ensure, Figure, last, newitem, prev, public, require, right, start, void
Находится в Учебник | No Comments »
Пространство имен RegularExpression и классы регулярных выражений
Написано admin в 20 Июнь 2008 – 21:25 -Tags: Capture, Compiled, Console, escape, fabadddbdf, FindMatch, Length, patstr, Regex, RegexCompilationInfo, RegexOptions, RegularExpressions, return, start, strpat, Success, TestSinglePat, Text, Unicode, WriteLine
Находится в Новости | No Comments »
Быстрая сортировка Хоара
Написано admin в 20 Июнь 2008 – 21:12 -Быстрая сортировка Хоара
Продолжая тему рекурсии, познакомимся с реализацией на C# еще одного известного рекурсивного алгоритма, применяемого при сортировке массивов. Описанный ранее рекурсивный алгоритм сортировки слиянием имеет один существенный недостаток – для слияния двух упорядоченных массивов за линейное время необходима дополнительная память. Разработанный Ч. Хоаром метод сортировки, получивший название быстрого метода сортировки – QuickSort, не требует дополнительной памяти. Хотя этот метод и не является самым быстрым во всех случаях, но на практике он обеспечивает хорошие результаты. Нужно отметить, что именно этот метод сортировки встроен в класс System.Array.
Идея алгоритма быстрой сортировки состоит в том, чтобы выбрать в исходном массиве некоторый элемент M, затем в начальной части массива собрать все элементы, меньшие M. Так появляются две подзадачи размерности – k и n-k, к которым рекурсивно применяется алгоритм. Если в качестве элемента M выбирать медиану сортируемой части массива, то обе подзадачи имели бы одинаковый размер и алгоритм быстрой сортировки был бы оптимальным по времени работы. Но расчет медианы требует своих затрат времени и усложняет алгоритм. Поэтому обычно элемент M выбирается случайным образом. В этом случае быстрая сортировка оптимальна лишь в среднем, а для плохих вариантов (когда в качестве M всякий раз выбирается минимальный элемент) имеет порядок n2.
Несмотря на простоту идеи, алгоритм сложен в своей реализации, поскольку весь построен на циклах и операторах выбора. Я проводил построение алгоритма параллельно с обоснованием его корректности, введя инварианты соответствующих циклов. Текст обоснования встроен в текст метода. Приведу его, а затем дам некоторые объяснения. Вначале, как обычно, приведу нерекурсивную процедуру, вызывающую рекурсивный метод: Read more »
Tags: Array, finish, int, item, name, param, QSort, QuickSort, rnd, Size, start, summary, System, temp, tower
Находится в Учебник | No Comments »
