Поможем в ✍️ написании учебной работы

Имя

Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Выберите тип работыЧасть дипломаДипломная работаКурсовая работаКонтрольная работаРешение задачРефератНаучно - исследовательская работаОтчет по практикеОтветы на билетыТест/экзамен onlineМонографияЭссеДокладКомпьютерный набор текстаКомпьютерный чертежРецензияПереводРепетиторБизнес-планКонспектыПроверка качестваЭкзамен на сайтеАспирантский рефератМагистерская работаНаучная статьяНаучный трудТехническая редакция текстаЧертеж от рукиДиаграммы, таблицыПрезентация к защитеТезисный планРечь к дипломуДоработка заказа клиентаОтзыв на дипломПубликация статьи в ВАКПубликация статьи в ScopusДипломная работа MBAПовышение оригинальностиКопирайтингДругое

Нажимая кнопку "Продолжить", я принимаю политику конфиденциальности

Идея: 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;

В нашем случае получился один проход “вхолостую”. Чтобы лишний раз не переставлять элементы, можно ввести флажок.

Улучшением пузырькового метода является шейкерная сортировка, где после каждого прохода меняют направление внутри цикла.

Эффективность алгоритма:

число сравнений М = ,             

число перемещений C_max = 3 .

 

Метод исследования

Данная курсовая работа заключается в исследовании прямых методов сортировки:

- метода прямого выбора;

- метода прямого включения;

- метода прямого обмена.

Исследование заключается в следующем:

берут три массива с одинаковым количеством элементов, но один из них упорядоченный по возрастанию, второй - по убыванию, а третий - случайный. Осуществляется сортировка данных массивов и сравнивается количество перемещений элементов при сортировке первого, второго и третьего массивов, а также сравнивается количество сравнений при сортировке.

Вышеописанный способ применяется для массивов, состоящих из 10, 100, 1000 и 10000 упорядоченных и неупорядоченных элементов для всех методов сортировки.

 

Результаты исследования

Сортировка 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

 

3.5 Контрольный пример

Задание:

Дан список, содержащий имена студентов и соответствующие им баллы рейтинга. Необходимо отсортировать данный список по убыванию баллов рейтинга.

Сортировка методом прямого включения:

До сортировки		После сортировки
Аркадий	19	Артур	20
До сортировки		После сортировки
Мурат	17	Аркадий	19
Руслан	9	Александр	18
Артур	20	Владимир	18
Евгений	7	Мурат	17
Михаил	15	Казбек	16
Александр	18	Михаил	15
Виталий	14	Борис	15
Сидор	8	Денис	14
Владимир	18	Виталий	14
Алексей	6	Василий	13
Казбек	16	Петр	10
Марат	5	Руслан	9
Борис	15	Иван	8
Геннадий	2	Сидор	8
Денис	14	Евгений	7
Василий	13	Алексей	6
Сидор	3	Марат	5
Петр	10	Сидор	3
Иван	8	Геннадий	2

Выводы

 

По результатам исследования можно утверждать, что лучшим из прямых методов сортировки является метод прямого выбора, так как он дает наименьшее количество сравнений и перемещений независимо от количества сортируемых элементов и их взаимного расположения в массиве.