Алгоритмы сортировки. Метод пузырька
Данный алгоритм является достаточно простым и поэтому получил широкое распространение. Вычислительная сложность алгоритма квадратичная – O(n2), поэтому алгоритм эффективен только на небольших массивах данных.
Алгоритм проходит все элементы массива и попарно сравнивает их друг с другом. Если порядок сравниваемых элементов неверный, алгоритм меняет элементы местами:
// Сортировка пузырьком
void BubbleSort(ref int[] Array)
{
// Перебираем все элементы массива (кроме последнего)
for (int i = 0; i < Array.Length - 1; i++)
// Перебираем все элементы справа от i
for (int j = i + 1; j < Array.Length; j++)
// Правильный ли порядок элементов?
if (Array[i] > Array[j])
{
// Нет - меняем порядок
int t = Array[i];
Array[i] = Array[j];
Array[j] = t;
}
}
Сортировка выбором
Сортировка выбором имеет квадратичную сложность O(n2) и, как и предыдущий метод пузырька, эффективен лишь на небольших объемах данных.
Алгоритм находит номер минимального значения в текущем списке, меняет этот элемент со значением первой неотсортированной позиции (если минимальный элемент не находится на данной позиции), а затем сортирует хвост списка, исключив из рассмотрения уже отсортированные элементы:
// Сортировка выбором
void SelectionSort(ref int[] Array)
{
// Перебираем все элементы массива (кроме последнего)
// i - позиция первого неотсортированного элемента
for (int i = 0; i < Array.Length - 1; i++)
{
// Позиция минимального элемента справа от i
int min = i;
// Перебираем все элементы справа от i
for (int j = i + 1; j < Array.Length; j++)
// Меньше ли очередной элемент минимального?
if (Array[j] < Array[min])
min = j; // Да - теперь это новый минимальный элемент
// Минимальный элемент не на первом месте? Меняем местами!
if (min! = i)
{
int t = Array[i];
Array[i] = Array[min];
Array[min] = t;
}
}
}
Быстрая сортировка
Алгоритм быстрой сортировки является одним из самых быстрых алгоритмов сортировки: в лучшем случае он имеет логарифмическую сложность, в худшем – квадратичную. Алгоритм выполняется следующим образом:
1. Выбирается некоторый элемент, который называется опорным.
2. Реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него.
3. Рекурсивно упорядочиваем массивы, лежащие слева и справа от опорного элемента.
// Быстрая сортировка
void QuickSort(ref int[] Array, int Left, int Right)
{
// i и j - индексы границ разделяемого массива
int i = Left;
int j = Right;
// x - индекс опорного элемента
int x = Array[(Left + Right) / 2];
do
{
// Ищем элемент слева, который больше опорного
while (Array[i] < x)
++i;
// Ищем элемент справа, который меньше опорного
while (Array[j] > x)
--j;
// Если индексы не поменялись местами, то обмениваем элементы
if (i < = j)
{
int t = Array[i];
Array[i] = Array[j];
Array[j] = t;
i++;
j--;
}
} while (i < = j);
// Рекурсивно выполняем быструю сортировку для массивов слева и справа
if (Left < j)
QuickSort(ref Array, Left, j);
if (i < Right)
QuickSort(ref Array, i, Right);
}
Поиск элемента
Алгоритмы поиска позволяют найти индекс элемента с требуемым значением.
Если массив не упорядочен, то возможен лишь простой поиск: перебор всех элементов массива до тех пор, пока не встретится элемент с нужным значением или не закончится массив. Если элемент найден, поиск должен быть прекращён, поскольку дальнейший просмотр массива не имеет смысла:
// Простой поиск элемента в массиве
int IndexOf(ref int[] Array, int Value)
{
// Перебираем все элементы массива
for (int i = 0; i < Array.Length; i++)
// Если нашли нужное значение, то возвращаем его индекс
if (Array[i] == Value)
return i;
// Перебор закончился безрезультатно - возвращаем -1
return -1;
}
Если алгоритм поиска не нашёл подходящий элемент, он должен каким-то образом сигнализировать об этом вызывающей программе. Чаще всего в таком случае возвращается значение -1 – число, которое заведомо не может использоваться в качестве индекса массива.
Вычислительная сложность алгоритма простого поиска – линейная O(n).
Если же массив упорядочен по возрастанию, то возможно использование дихотомического рекурсивного алгоритма: массив каждый раз делится пополам и если искомый элемент меньше среднего, то поиск продолжается в левой его половине, иначе – в правой:
// Дихотомический поиск элемента в массиве
static int IndexOf(ref int[] Array, int Value, int Left, int Right)
{
// Находим середину диапазона
int x = (Left + Right) / 2;
// Если нашли значение - возвращаем его индекс
if (Array[x] == Value)
return x;
// Если середина совпадает с левой или правой границами - значение не найдено
if ((x == Left) || (x == Right))
return -1;
// Продолжаем поиск слева или справа от середины
if (Array[x] < Value)
return IndexOf(ref Array, Value, x, Right);
else
return IndexOf(ref Array, Value, Left, x);
}
Вычислительная сложность алгоритма – логарифмическая.
13.6. Выполнение индивидуального задания
Общая часть задания: сформировать массив из 100 случайных чисел. Выполнить простой поиск элемента, подсчитать количество итераций. Отсортировать массив методом, указанным в своём варианте. Выполнить поиск элемента методом дихотомии, подсчитать количество итераций. Сделать выводы.
1) Метод пузырька
2) Сортировка выбором
3) Быстрая сортировка
Приложение 1
ПРиложение 1. Команды основного меню
В меню Файл находятся команды для выполнения операций с проектами, модулями и файлами.
| Команда
| Описание
|
| Создать
| Позволяет выбрать тип элемента (проект, файл и другие) и создать его
|
| Открыть
| Открывает ранее созданный проект, модуль, форму или текстовой файл
|
| Закрыть решение
| Закрывает текущее решение
|
| Закрыть
| Закрывает выбранный элемент (файл, модуль, форма)
|
| Сохранить выделенные элементы
| Сохраняет текущее решение, выбранные проекты, формы или файлы
|
| Сохранить выделенные элементы как
| Сохраняет текущее решение, выбранные проекты, формы или файлы с новым именем
|
| Сохранить все
| Сохраняет все открытые файлы, формы, проекты и используемые им модули, а также решение
|
| Параметры страницы
| В открывшемся диалоговом окне можно настроить параметры печати активного файла, такие как ориентация, масштаб и размер бумаги. Заданные параметры печати сохраняются вместе с файлом диаграммы.
|
| Печать
| Выводит содержимое активного файла на печать
|
| Последние файлы
| Позволяет увидеть список недавно использованных фалов и открыть их
|
| Последние проекты и решения
| Позволяет увидеть список недавно использованных решение и проектов и открыть их
|
| Выход
| Завершает работу Visual Studio
|
В меню Правка расположены команды, осуществляющие операции редактирования, работы с областью обмена данными, отмены действий.
| Команда
| Описание
|
| Отменить
| Отменяет ранее выполненные действия
|
| Вернуть
| Восстанавливает отмененные действия
|
| Отменить последнее глобальное действие
| Отменяет последнее глобальное действие, которое затрагивает несколько файлов. К глобальным действиям относятся переименование класса или пространства имен, выполнение операции поиска с заменой по решению, рефакторинг базы данных и любое другой действие, вызывающее изменение нескольких файлов.
|
| Вернуть последнее глобальное действие
| Восстанавливает последнее глобальное действие, которое затрагивает несколько файлов
|
| Вырезать
| Вырезает выделенный объект и помещает его в буфер обмена данными
|
| Копировать
| Копирует выделенный объект и (или) фрагмент текста программы и помещает его в буфер обмена данными
|
| Вставить
| Копирует содержимое буфера обмена данными в редактор или форму
|
| Удалить
| Удаляет выбранный объект или фрагмент программы
|
| Выделить все
| Выделяет все компоненты формы или весь текст программы
|
| Поиск и замена
| Позволяет выполнять поиск в одном или нескольких открытых файлах, расположенных в различных областях поиска, чтобы можно было производить текстовые замены и просматривать результаты поиска в формате отчета.
|
| Закладки
| Позволяет создавать, удалять и выбирать созданные ранее закладки в написанном коде. Закладки позволяют осуществлять быструю навигацию между отмеченными местами в файлах созданного решения и перемещаться по тексту.
|
В меню Вид содержатся команды для выбора панелей инструментов, выводимых на экран и вызова менеджера проектов, инспектора объектов, броузера объектов и других информационных утилит.
| Команда
| Описание
|
| Код
| Показывает окно текста для выбранного файла
|
| Конструктор
| Показывает окно формы для выбранного файла
|
| Открыть
| Открывает выбранный файл
|
| Обозреватель решений
| Открывает окно, отображающее состав открытого решения.
Обозреватель решений позволяет просматривать элементы решения или проекта и осуществлять операции по управлению ими.
|
| Командный обозреватель
| Открывает окно, отображающее состав открытого командного решения. Командный обозреватель позволяет просматривать элементы решения или проекта, загружать их текущии с сервера контроля версий.
|
| Обозреватель серверов
| Открывает серверную консоль управления Visual Studio. Это окно используется для создания подключений к данным, а также для входа на серверы для просмотра баз данных и системных служб.
|
| Обозреватель архитектуры
| Открывает окно архитектуры открытого решения. В обозревателе архитектуры представлены такие структуры, как узлы, и такие отношения, как связи.
|
| Окно закладок
| Открыает окно закладок
|
| Иерархия вызовов
| Открывает окно иерархии вызовов. Иерархия вызовов позволяет переходить по коду, отображая все входящие и исходящие вызовы выбранного метода, свойства или конструктора. Иерархия вызовов доступна во время разработки в отличие от стека вызова, который отображается отладчиком.
|
| Классы
| Открывает окно, отображающее существующие классы в открытом решении
|
| Окно определения кода
| Открывает окно, представляющее редактор только для чтения, в котором отображается определение знака в файле кода, хранящемся в активном проекте или с которым связан активный проект.
|
| Обозреватель объектов
| Обозреватель объектов позволяет просматривать библиотеки, объекты, список свойств, методов, событий, переменных, констант и прочих элементов в заданной области обзора.
|
| Список ошибок
| Открывает окно, в котором отображаются ошибки, предупреждения и сообщения, созданные во время редактирования и компиляции кода.
|
| Вывод
| Открывает окно выходных данных. Данное окно отображает сообщения, созданные в процессе компилирования кода и состояния различных средств, включенных в интегрированную среду разработки.
|
| Начальная страница
| Открывает окно начальной страницы. Начальная страница обеспечивает быстрый доступ к проектам, их созданию, сведениям о предстоящих выпусках продуктов и конференциях, а также о последних статьях по разработке.
|
| Список задач
| Открывает окно список задач, которое позволяет создавать списки задач программирования и управлять этими списками. В окне список задач можно создавать задачи пользователя, представляющие собой заметки о работах, которые необходимо выполнить, а также отображать список задач-комментариев, связывающие задачи со строками кода, в которых необходимо выполнить работу.
|
| Панель элементов
| Открывает окно панели элементов, на котором отображаются значки элементов управления и других элементов, которые можно добавить в проекты Visual Studio. Панель элементов показывает только элементы, подходящие к типу файла, в котором работает пользователь.
|
| Панель инструментов
| Отображает всплывающее меню, на котором можно добавлять или удалять команды в любом меню или на любой панели инструментов в интегрированной среде разработки, а также изменять порядок и группировку этих команд. Кроме того, можно добавлять меню или панели инструментов, а также изменять расположение, позицию и содержимое существующих панелей инструментов.
|
| Окно свойств
| Открывает окно свойств, которое предназначено для просмотра и внесения изменений в заданные во время разработки свойства и события выделенных объектов, расположенных в редакторах и конструкторах.
|
В меню Проект содержатся команды для добавления и удаления компонетов текущего проекта и настройки параметров текущего проекта.
| Команда
| Описание
|
| Добавить форму Windows
| Добавляет форму к открытому проекту
|
| Добавить пользовательский элемент управления
| Добавляет элемент управлению формой к открытому проекту
|
| Добавить компонент
| Добавляет выбранный компонент, разработанный пользователем или членами его команды или добавить пустой класс компонета для его создания
|
| Добавить новый элемент
| Диалоговое окно для добавления элемента в выбранный проект. При выборе элемента из списка установленных шаблонов, в проект добавляются соответствующие файлы и ссылки. В списке шаблонов отображаются элементы в зависимости от выбранного типа проекта и заданной версии.NET Framework
|
| Добавить существующий элемент
| Это диалоговое окно служит для выбора одного или нескольких элементов проекта для их добавления в папку " Элементы решения". Файлы можно выбирать в локальных каталогах, сетевых каталогах или на веб-узлах.
|
| Исключить из проекта
| Позволяет временно или постоянно исключить из открытого решения проекты или из выбранного проекта фалы, модули или формы. При этом хранящийся элемент не будет удален из папки решения, хранящейся на физическом диске.
|
| Свойства
| Открывает окно страницы свойств выбранного элемента, в котором можно задавать параметры для проектов Visual Studio, чтобы они применялись ко всем конфигурациям построения, или же задать различные свойства для каждой конфигурации построения.
|
| Открыть папку в проводнике Windows
| Данная функция активна только при выборе открытого проекта или всего решения в обозревателе решений. Позволяет открыть папку выбранного элемента в проводнике.
|
В меню Построение содержатся команды для компиляции и сборки проектов, а также для установки опций компиляции.
| Команда
| Описание
|
| Построить решение
| Компилирует программу
|
| Перестроить решение
| Компилирует программу после внесения изменений в несколько проектов существующего решения
|
| Очистить решение
| Позволяет удалить ранее сформированные компилятором загрузочные файлы, модули и библиотеки для выбранного решения в целом.
|
| Построить выбранный проект
| Компилирует проект
|
| Перестроить выбранный проект
| Компилирует программу после внесения изменений в несколько файлов существующего проекта
|
| Очистить выбранный проект
| Позволяет удалить ранее сформированные компилятором загрузочные файлы, модули и библиотеки для выбранного проекта.
|
| Пакетное построение
| Открывает диалоговое окно, которое используется для построения нескольких конфигураций проектов одновременно. Например, может возникнуть необходимость построить все конфигурации проекта с помощью одной команды.
|
| Диспетчер конфигураций
| Открывает диалоговое окно, которое используется для создания и изменения конфигураций построения решений и конфигураций проектов.
|
В меню Отладка расположены команды для отладки программ. Эти команды позволяют управлять различными функциями отладки среды разработки.
| Команда
| Описание
|
| Окна
| Позволяет выбать окна, которые используется во время разработки для отладки и вычисления выражений, выполнения операций, печати значений переменных.
|
| Начать отладку
| Компилирует код и запускает программу
|
| Запуск без отладки
| Запускает последнюю скопилированную версию программы с обходом системы отладки ошибок
|
| Продолжить
| Позволяет продолжить выполнение программы до конца или до следующей точки останова
|
| Прервать все
| Позволяет прервать выполнение программы и вернуться в режим отладки
|
| Остановить отладку
| Останавливает выполнение программы и возвращает пользователя в режим редактирования кода
|
| Шаг с заходом
| Позволяет пошагово выполнять программу с заходом в подпрограммы в режиме отладки
|
| Шаг с обходом
| Позволяет пошагово выполнять программу без захода в подпрограммы в режиме отладки
|
| Шаг с выходом
| Позволяет выполнить программус выходом из режима отладки
|
| Быстрая проверка
| Открывает диалоговое окно " Быстрая проверка", которое позволяет просматривать и вычислять значения переменных и выражений используемых в текущей (на момент отладки) функции программы.
|
| Точка останова
| Устанавливает точку останова в текущем файле на строчку, в которой установлен курсор.
|
| Удалить все точки останова
| Удаляет все точки останова имеющиеся в текущем решении
|
| Выключить все точки останова
| Позволяет отключить все точки останова имеющиеся в текущем решении
|
| Отладка IntelliTrace
| Запускает отладку в режиме IntelliTrace, которая позволяет избежать множественных перезагрузок выполнения программы за счет предоставления доступа к информации о событиях, произошедших в прошлом, ускоряя отладку.
|
| Параметры и настройки
| Открывает диалоговое окно " Параметры", которое позволяет просматривать и изменять параметры и конфигурации отладчика.
|
| Точка останова
| Устанавливает точку останова в текущем файле на строчку, в которой установлен курсор.
|
Меню Рабочая группа содержит средства для работы с коллективными проектами.
| Команда
| Описание
|
| Подключиться к Team Foundation Server
| Показывает окно подключения к серверу коллективной работы нескольких программистов над одним или несколькими проектами.
|
Меню Данные содержит средства для работы с базами данных.
| Команда
| Описание
|
| Показать источники данных
| Открывает диалоговое окно «Источники Данных», в котором отображаются источники данных в текущем проекте.
|
| Добавить источник данных
| Вызывает «Мастер настройки источника данных», который используется для создания и редактирования источников данных в приложении. Эти источники данных можно создать из баз данных, служб или объектов.
|
| Сравнение схем
| Открывает окно сравнение схем, которое используется для отображения результата сравнения двух схем баз данных.
|
| Редактор Transact SQL
| Используется для создания соединения к SQL серверам и создания запросов к их базам данным.
|
Из меню Сервис доступны средства настройки среды, дополнительные утилиты, входящие в состав Visual Studio.
| Команда
| Описание
|
| Диспетчер фрагментов кода
| Открывает диалоговое окно «Диспетчер фрагментов кода», которое используется для добавления папок в список папок, сканируемых утилитой «Code Snippets Manager» на предмет наличия файлов XML с расширением SNIPPET. Наличие таких стандартных блоков кода может упростить разработку проекта, позволив копировать готовые блоки в активный документ.
|
| Диспетчер надстроек
| Позволяет загружать и удалять надстройки из интегрированной среды разработки, а также указывать параметров загрузки надстроек.
|
| Макрос
| Макрос является набором команд и инструкций, сгруппированных в виде одной команды для автоматического выполнения задачи. Макросы позволяют автоматизировать повторяющиеся задачи.
|
| Диспетчер расширений
| Позволяет осуществлять поиск и установку расширений для Visual Studio.
|
| Список ошибок
| Открывает окно Список ошибок, которое позволяет отображать различные ошибик, предупреждений и сообщений, созданных во время редактирования и компиляции кода, загрузки файлов, применении политик из шаблона проекта.
|
| Внешние инструменты
| Позволяет выбрать внешние инструменты, которые облегчают разработку и отладку приложений.
|
| Импорт и экспорт параметров
| Вызывает «Мастер экспорта и импорта параметров», которые позволяет сохранить или загрузить параметры и настройки Visual Studio..
|
| Настройка
| Позволяет изменить внешний вид (настраивать такие элементы как окна, панели инструментов, сочетания клавиш и другие элементы интерфейса) и поведение интегрированной среды разработки Visual Studio, а также сохранять эти настройки.
|
| Параметры
| Открывает диалоговое окно «Параметры», которое используется для настроики среды разработки. Например: задать используемое по умолчанию местоположение для хранения проектов, а также стили отображения и поведения окон.
|
В меню Справка содержатся команды для вызова различных разделов справочной системы и отображения диалоговой панели «О программе».
| Команда
| Описание
|
| Просмотр справки
| Запускает агента библиотеки справки, а также открывает веб-браузер для просмотра локально установленной справки или просмотра интерент-справки (MSDN Library).
|
| Управление параметрами справки
| Открывает приложение " Диспетчер библиотек справки", которое позволяет управлять документацией по продукту в локальном хранилище содержимого средства просмотра справки Майкрософт, а также служит для управления параметрами, позволяющими настроить взаимодействие со справочной системой.
|
| Форумы MSDN
| Открытие веб-браузера для просмотра справочных разделов форума библиотеки MSDN.
|
| Сообщить об ошибке
| Позволяет отправить в корпорацию Майкрософт отзывы и предложения, касающиеся работы с Visual Studio.
|
| Примеры
| Соединяет со страницей библиотеки MSDN, посвященной примерам и готовых шаблонов.
|
| Параметры отзывов пользователей
| Открывает диалоговое окно, позволяющее настроить параметры отправки отчетов об ошибках, а также параметры сбора анонимной информации об использовании Visual Studio на сайт Майкрософт.
|
| Зарегестрировать продукт
| Открывает диалоговое окно регистрации продуктов входящих в состав Visual Studio 2010, позволяющее приобрести ключ с помощью интернет магазина Майкрософт или ввести уже имеющийся лицензионный ключ.
|
| Проверить наличие обновлений
| Соединяет со страницей загрузки обновлений продуктов компании Майкрософт и предоставляет пользователю список имеющихся пакетов обновлений для Visual Studio.
|
| Техническая поддержка
| Предоставляет пользователю возможность выбора одного из вариантов технической поддержки Visual Studio (форумы MSDN, локальная справка, служба техничнической поддержки Майкрософт)
|
| Заявление о конфиденциальности
| Соединяет с интернет страницей фирмы Мафкрософт, посвященной Заявлению о конфиденциальности для Visual Studio 2010
|
| О программе
| Отображает диалоговую панель «О программе», содержащую сведения о продукте, а также предоставляется доступ к сведениям о компьютере, на котором он запущен.
|
Приложение 2
ПРиЛОЖЕНИЕ 2. Свойства компонентов
Популярное:
