- •Оглавление
- •Введение
- •Методические указания
- •Темы курсовых проектов
- •Пример выполнения курсового проекта
- •1 Постановка задачи
- •2 Краткая теория
- •2.1 Сортировка методом прямого включения
- •2.2 Сортировка методом прямого выбора
- •2.3 Сортировка с помощью прямого обмена (пузырьковая)
- •3 Метод исследования
- •4 Результаты исследования
- •5 Контрольный пример
- •6 Заключение
- •7 Приложение Описание процедур, используемых в программе
- •Текст программы( на языке программирования Pascal)
- •I:integer;
- •I:integer;
- •I,j:integer;
- •X:integer;
- •I,j:integer;
- •X:integer;
- •I,j:integer;
- •X:integer;
- •I,j:integer;
- •Item:byte;
- •{Fill - процедура, заполняющая заданную область экрана заданными символами заданного цвета}
- •1:Example;
- •2:Begin
- •{Вызов процедуры make, осуществляющей исследование методов сортировки}
- •{Вызов процедуры make, осуществляющей исследование методов сортировки}
- •{Вызов процедуры make, осуществляющей исследование методов сортировки}
- •3:Begin
- •4:Begin
- •5:Begin
- •6:Begin
- •Gotoxy(12,7);write('Данная программа является курсовым проектом по дисциплине');
- •Список литературы
2.3 Сортировка с помощью прямого обмена (пузырьковая)
Идея: n - 1 раз проходят массив снизу вверх. При этом ключи попарно сравниваются. Если нижний ключ в паре меньше верхнего, то их меняют местами.
Программа на Паскале:
for i := 2 to n do for j := n downto i do if a[j - 1] > a[j] then begin x := a[j - 1]; a[j - 1] := a[j]; a[j] := x; end;
|
В нашем случае получился один проход “вхолостую”. Чтобы лишний раз не переставлять элементы, можно ввести флажок.
Улучшением пузырькового метода является шейкерная сортировка, где после каждого прохода меняют направление внутри цикла.
Эффективность алгоритма:
число сравнений М =,
число перемещений Cmax = 3 .
3 Метод исследования
Данная курсовая работа заключается в исследовании базовых методов сортировки:- метода прямого выбора;- метода прямого включения;- метода прямого обмена.
Исследование заключается в следующем:
берут три массива с одинаковым количеством элементов, но один из них упорядоченный по возрастанию, второй - по убыванию, а третий - случайный. Осуществляется сортировка данных массивов и сравнивается количество перемещений элементов при сортировке первого, второго и третьего массивов, а также сравнивается количество сравнений при сортировке.
Вышеописанный способ применяется для массивов, состоящих из 10, 100, 1000 и 10000 упорядоченных и неупорядоченных элементов для всех методов сортировки.
4 Результаты исследования
Сортировка 10 элементов: |
|||
- упорядоченных по возрастанию |
|||
метод |
прямого выбора |
прямой вставки |
прямого обмена |
сравнений |
45 |
45 |
45 |
перемещений |
11 |
33 |
33 |
- неупорядоченных (случайных) |
|||
метод |
прямого выбора |
прямой вставки |
прямого обмена |
сравнений |
45 |
45 |
45 |
перемещений |
27 |
27 |
27 |
- упорядоченных по убыванию |
|||
метод |
прямого выбора |
прямой вставки |
прямого обмена |
сравнений |
45 |
45 |
45 |
перемещений |
0 |
0 |
0 |
Сортировка 100 элементов: |
|||
- упорядоченных по возрастанию |
|||
метод |
прямого выбора |
прямой вставки |
прямого обмена |
сравнений |
4950 |
4950 |
4950 |
перемещений |
2643 |
4862 |
4862 |
- неупорядоченных (случайных) |
|||
метод |
прямого выбора |
прямой вставки |
прямого обмена |
сравнений |
4950 |
4950 |
4950 |
перемещений |
2558 |
2558 |
2558 |
- упорядоченных по убыванию |
|||
метод |
прямого выбора |
прямой вставки |
прямого обмена |
сравнений |
4950 |
4950 |
4950 |
перемещений |
0 |
0 |
0 |
Сортировка 1000 элементов: |
|||
- упорядоченных по возрастанию |
|||
метод |
прямого выбора |
прямой вставки |
прямого обмена |
сравнений |
499500 |
499500 |
499500 |
перемещений |
241901 |
498442 |
498442 |
- неупорядоченных (случайных) |
|||
метод |
прямого выбора |
прямой вставки |
прямого обмена |
сравнений |
499500 |
499500 |
499500 |
перемещений |
244009 |
250366 |
250366 |
- упорядоченных по убыванию |
|||
метод |
прямого выбора |
прямой вставки |
прямого обмена |
сравнений |
499500 |
499500 |
499500 |
перемещений |
0 |
0 |
0 |
Сортировка 10000 элементов: |
|||
- упорядоченных по возрастанию |
|||
метод |
прямого выбора |
прямой вставки |
прямого обмена |
сравнений |
49995000 |
49995000 |
49995000 |
перемещений |
25003189 |
49984768 |
49984768 |
- неупорядоченных (случайных) |
|||
метод |
прямого выбора |
прямой вставки |
прямого обмена |
сравнений |
49995000 |
49995000 |
49995000 |
перемещений |
18392665 |
24986578 |
24986578 |
- упорядоченных по убыванию |
|||
метод |
прямого выбора |
прямой вставки |
прямого обмена |
сравнений |
49995000 |
49995000 |
49995000 |
перемещений |
0 |
0 |
0 |