- •Утверждаю
- •Программирование на с#
- •Томск 2012
- •Рецензент доц., канд.Физ.-мат. Наук в.И.Рейзлин
- •Лабораторная работа № 1. Изучение среды разработкиVisualStudio
- •Интегрированная среда разработчика VisualStudio
- •1.2. Настройка формы
- •1.3. Размещение элементов управления на форме
- •1.4. Размещение строки ввода (TextBox)
- •1.5. Размещение надписей (Label)
- •1.6. Написание программы обработки события
- •1.7. Написание программы обработки события нажатия кнопки (Click)
- •1.8. Написание программы обработки события загрузки формы (Load)
- •1.9. Запуск и работа с программой
- •1.10. Динамическое изменение свойств
- •1.11. Выполнение индивидуального задания
- •Индивидуальные задания
- •Лабораторная работа №2. Программирование линейных алгоритмов
- •2.1. Структура приложения
- •2.2. Работа с проектом
- •2.3. Описание данных
- •2.4. Ввод/вывод данных в программу
- •2.5. Арифметические действия и стандартные функции
- •2.6. Пример написания программы
- •2.7. Выполнение индивидуального задания
- •Индивидуальные задания
- •Лабораторная работа №3. Программирование разветвляющихся алгоритмов
- •3.3. Кнопки-переключатели RadioButton
- •3.4. Пример написания программы
- •3.4.1. Создание формы
- •3.4.2. Создание обработчиков событий FormСreate и Botton1Сlick
- •3.5. Выполнение индивидуального задания
- •Лабораторная работа №4 Программирование циклических алгоритмов
- •4.1. Операторы организации циклов
- •4.2. Цикл с предусловием while
- •4.3. Цикл с постусловием do while
- •4.4. Цикл с параметром for
- •4.2. Средства отладки программ
- •4.3. Порядок выполнения задания
- •4.4. Выполнение индивидуального задания
- •Индивидуальные задания
- •Лабораторная работа № 5. Программирование с использованием строк
- •5.1. Тип данных string
- •5.2. Компонент ListBox
- •5.3. Порядок выполнения индивидуального задания
- •5.4. Индивидуальные задания
- •Лабораторная работа № 6. Программирование с использованием одномерных массивов
- •6.1. Работа с массивами
- •6.2. Случайные числа
- •6.3. Порядок выполнения индивидуального задания
- •6.3. Варианты заданий
- •Лабораторная работа 7. Программирование с использованием многомерных массивов
- •7.1. Двухмерные массивы
- •7.2. Элемент управления DataGridView
- •7.3. Порядок выполнения задания
- •7.4. Индивидуальные задания
- •Лабораторная работа 8. Программирование с использованием средств для отображения графической информации
- •8.1. Как строится график с помощью компонента Chart
- •8.2. Пример написания программы
- •8.3. Выполнение индивидуального задания
- •Лабораторная работа 9. Программирование графики
- •9.1. Сообщение wm_paint
- •9.2. Событие Paint
- •9.3. Объект Graphics для рисования
- •9.4. Методы и свойства класса Graphics
- •9.5. Выполнение индивидуального задания
- •Лабораторная работа 10. Простейшая анимация
- •10.1. Работа с таймером
- •10.2. Создание анимации
- •10.3. Выполнение индивидуального задания
- •Лабораторная работа 11. Обработка изображений
- •11.1. Отображение графических файлов
- •11.2. Компоненты OpenFileDialog и SaveFileDialog
- •11.3. Простой графический редактор
- •11.4. Выполнение индивидуального задания
- •Лабораторная работа 12. Методы
- •12.1. Общие понятия
- •12.2. Перегрузка методов
- •12.3. Параметры по умолчанию
- •12.4. Передача параметров по значению и по ссылке
- •12.5. Выполнение индивидуального задания
- •Лабораторная работа 13. Сортировка
- •13.1. Общие понятия
- •13.2. Алгоритмы сортировки. Метод пузырька
- •13.3. Сортировка выбором
- •13.4. Быстрая сортировка
- •13.5. Поиск элемента
- •13.6. Выполнение индивидуального задания
- •ПРиложение 1. Команды основного меню
- •ПРиЛожение 2. Свойства компонентов п2.1. Общие свойства компонентов
- •Свойство Name
- •Свойство Dock
- •Свойство Margin
- •Свойство Color
- •Свойство Cursor
- •Свойство Size
- •Приложение 3. Простые типы данных п3.1.Целые типы
- •П3.2.Логические типы
- •П3.3.Символьный тип
- •П3.4. Перечисляемый тип
- •П3.5. Вещественные типы
- •Пз.6. Тип дата-время
- •Приложение 4. Процедуры и функции для работы со строками
- •Приложение 5. Математические формулы
- •Литература
- •Программирование в среде delphi
13.2. Алгоритмы сортировки. Метод пузырька
Данный алгоритм является достаточно простым и поэтому получил широкое распространение. Вычислительная сложность алгоритма квадратичная – 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;
}
}
13.3. Сортировка выбором
Сортировка выбором имеет квадратичную сложность 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;
}
}
}
13.4. Быстрая сортировка
Алгоритм быстрой сортировки является одним из самых быстрых алгоритмов сортировки: в лучшем случае он имеет логарифмическую сложность, в худшем – квадратичную. Алгоритм выполняется следующим образом:
Выбирается некоторый элемент, который называется опорным.
Реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него.
Рекурсивно упорядочиваем массивы, лежащие слева и справа от опорного элемента.
// Быстрая сортировка
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);
}