Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Проектування алгоритмів сортування ⇐ ПредыдущаяСтр 8 из 8
Існує N значень, які потрібно упорядкувати за зростанням (або спаданням), якщо мова йде про числові значення, або за алфавітом, якщо мова йде про ланцюжки символів. Методи сортування дуже важливі в теоретичному відношенні і мають велике поширення як у наукових задачах, так і в задачах управління. Вони породили величезне число досліджень. На такому прикладі як сортування, який легко формулюється, можна порівнювати різноманітні алгоритми, досліджувати їхню складність і поведінку в залежності від числа і форми даних. У більшості машин існують стандартні програми сортування і користувач урятований від необхідності писати свою власну програму. Для сортування всі дані потрібно ввести в машину. Припустимо, що потрібно впорядкувати за зростанням числові дані, які містяться в пам’яті в масиві Т розміром N. Існує багато різноманітних алгоритмів сортування, що дозволяють вирішити цю задачу. "Кулькове" сортування. Назва походить від образної інтерпретації, при якій у процесі виконання алгоритму більш "легкі" елементи потрохи підіймаються на "поверхню". Алгоритм (рис.1) "кулькового" сортування складається з послідовних проходів від початку до кінця масиву введених даних Т і обміну сусідніх елементів з інверсією. Порівнюють пари значень Т(I) і Т(I+1) при I в інтервалі від 1 до N-1; якщо Т(I)>T(I+1), то значення переставляються місцями. Сортування зупиняється, коли немає чого переставляти; у цьому випадку сортування масиву закінчується. Сортування пошуком послідовних мінімумів. При першому проході шукається мінімальне значення масиву Т, що потім змінюється місцями з першим елементом T(1), потім пошук продовжується на N-1 елементах, що залишилися, шукається другий мінімум, що змінюється з елементом Т(2) і т.д. Алгоритм сортування пошуком послідовних мінімумів наведено на рис.2. Сортування методом вставки. Щоб відсортувати масив Т, достатньо вставити T(J) у J-1 вже сортованих перших елементів, при цьому J змінюється від 2 до N. Алгоритм сортування методом вставки наведено на рис.3. Швидке сортування SHELL-SORT є вдосконаленим методом вставки. Ідея, що покладена в основу цього метода така, що дані попередньо сортуються у блоках, а потім кількість блоків зменшується до тих пір, поки усі данні не будуть в одному блоці. Тим самим значно зменшується кількість обмінів. На операції обмінів у програмі для сортування даних витрачається багато машинного часу. Швидке сортування QUICKSORT є одним із найшвидших методів сортування. Серед N значень, які треба відсортувати, обирається значення, яке називають провідним елементом. Цей вибір може проводитися випадковим чином. Потім у початок масиву ставляться усі елементи, менші за провідний, а у кінець –усі інші. На кожній з отриманих послідовностей ця операція повторюється до тих пір, доки не одержані послідовності, які мають один або два елементи. Таким чином масив відсортований. Ефективність цього методу є високою лише у тому випадку, коли вибрані провідні елементи розділяють кожну послідовність на послідовності приблизно однієї довжини.
Розберемо приклад. Дано деяку послідовність чисел:
4 3 7 6 9 1 0 2 5
Виберемо перше (4), останнє (5) та число (9), яке знаходиться посередині. Середнім числом D є 5, і по ньому дана послідовність ділиться на 2 підгрупи. Для цього число D переставляється на праве провідне місце (у цьому прикладі воно вже там стоїть). Тепер, починаючи з провідного лівого, шукається число більше за 5, а з правого – число менше за 5, і ці числа переставляються місцями. У даному випадку це числа 2 та 7.
4 3 2 8 9 1 0 7 5
Пошук продовжується до тих пір, доки не зупиниться на числі, котре не вдасться переставити з жодним іншим числом. Таким чином послідовність має вигляд:
4 3 2 0 1 9 8 7 5 Потім це число (у даному випадку 9) зміняється з числом, що стоїть у правому кінці (у даному випадку числом 5). Це дає:
4 3 2 0 1 5 8 7 9
Тепер число 5 стоїть на тому місці, на якому воно буде стояти після закінчення сортування. Таким самим чином сортуються обидві підгрупи (4 3 2 0 1) і (8 7 9), доки в кожній з них не залишиться по одному числу.
3 Контрольні питання 3.1 Зазначте області застосування сортування. 3.2 Сутність методу "кулькового" сортування. 3.3 Сутність сортування методом послідовних мінімумів. 3.4 Сутність сортування методом вставки. 3.5 Методи швидкого сортування.
|
|||||
Последнее изменение этой страницы: 2020-12-09; просмотров: 62; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.191.223.123 (0.006 с.) |