Понедельник, Июль 5th, 2010

Структуры и алгоритмы обработки данных

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

Эффективность алгоритма:
число сравнений М = ,
число перемещений Cmax = 3.

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

Данная курсовая работа заключается в исследовании прямых методов сортировки:
— метода прямого выбора;
— метода прямого включения;
— метода прямого обмена.
Исследование заключается в следующем:
берут три массива с одинаковым количеством элементов, но один из них упорядоченный по возрастанию, второй — по убыванию, а третий — случайный. Осуществляется сортировка данных массивов и сравнивается количество перемещений элементов при сортировке первого, второго и третьего массивов, а также сравнивается количество сравнений при сортировке.
Вышеописанный способ применяется для массивов, состоящих из 10, 100, 1000 и 10000  упорядоченных и неупорядоченных элементов для всех методов сортировки.

3.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

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

Категория: Учебники