Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Программная реализацияСтр 1 из 3Следующая ⇒ Сортировка и поиск 1. ПОНЯТИЕ СОРТИРОВКИ. Сортировка - это упорядочение данных по определенному признаку. Рассмотрим одномерный массив целых чисел: Const NMax=...; Алгоритмы сортировки отличаются друг от друга степенью эффективности, под которой понимается количество сравнений и количество обменов, произведенных в процессе сортировки. Эффективность оценивается количеством операций сравнения (порядком этого значения). Элементы массива можно сортировать: • по неубыванию — каждый следующий элемент не меньше предыдущего А[1] <= А [2] <=... <= A[N]; • по убыванию — каждый следующий элемент меньше предыдущего А[1] > А [2] >... > A[N]; Рассмотрим идею данного метода на примере. Пусть исходный массив состоит из 10 элементов: Максимальный элемент помещен на свое место. 2. Рассмотрим часть массива — с первого до девятого элемента. Максимальный элемент этой части — 13, стоящий на втором месте. Поменяем его местами с последним элементом неупорядоченной части — с числом 10. Отсортированная часть массива состоит теперь уже из двух элементов. 3. Уменьшим рассматриваемую часть массива на один элемент. Здесь нужно поменять местами второй элемент (его значение — 10) и последний элемент этой части — число 4. В отсортированной части массива — 3 элемента. Программная реализация. Procedure Sortirovka; ЭФФЕКТИВНОСТЬ АЛГОРИТМА: Оценим количество сравнений. При первом просмотре N — 1, при втором — N — 2, при последнем — 1. Общее количество С = N — 1+N — 2 +...+ 1= N• (N- l)/2, или C=O(N2). ЗАДАНИЯ: I уровень: 1. Модифицировать алгоритм так, чтобы осуществлялась сортировка: СОРТИРОВКА ПРОСТЫМ ОБМЕНОМ (метод "пузырька") Название это происходит от образной интерпретации, при которой в процессе выполнения сортировки более "легкие" элементы (элементы с заданным свойством) всплывают на "поверхность". Рассмотрим идею метода на примере. Отсортируем по возрастанию массив из 5 элементов: 5 2 8 4 9. Длина текущей (неупорядоченной) части массива — (N — k + 1), где k — номер просмотра, i — номер первого элемента проверяемой пары, N — k - номер последней пары. i= 2 4 5 8 2 9 < не меняем Второй просмотр: рассматриваем часть массива с первого до предпоследнего элемента. Третий просмотр: рассматриваемая часть массива содержит три первых элемента. Четвертый просмотр: рассматриваем последнюю пару элементов. Procedure Sort; ЭФФЕКТИВНОСТЬ АЛГОРИТМА: При сортировке методом "пузырька" выполняется N — 1 просмотров, на каждом i -м просмотре производится N — i сравнений. Общее количество С равно N* (N—1)/2,или O(N2). ЗАДАНИЯ: II уровень: 1.Дан массив 12 3 5 7 9 10. За один просмотр он становится отсортированным, остальные просмотры ничего не дают. Исключить лишние просмотры. III уровень:
|