Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Алгоритм СОРТ-1 (попарне сортування)
Крок 1. Введення початкових даних: input N (N - кількість сортованих даних) for i = 1 to N do read (x(i)) od. Крок 2. Взвод прапора F (перестановка) для штучного запуску циклу while-do: F = 1. Крок 3. Зовнішній цикл по прапору F - була чи ні перестановка при черговому переборі всіх пар: while F = 1 do F = 0 (скидання прапора перед черговим перебором пар) [внутрішній цикл - формування пар і порівняння їх елементів] for i = 1 to N - 1 do [порівняння елементів чергової пари] if x(i)> x(i + 1) then [перестановка чисел і взвод прапора] а = x(i); x(i)= x(i + 1); x(i + 1)= а: F = 1 fi od od Крок 4. Виведення результатів. for i = 1 to N do write (x(i)) od Крок 5. Кінець.
ОБМІННЕ СОРТУВАННЯ відрізняється від попарної методом формування приватного завдання - пари порівнюваних елементів: ініціалізувався покажчик Р, яким фіксується довільний, наприклад, 1-й елемент. Серед тих, що залишилися (що знаходяться "нижче" за покажчик Р) відшукується найменший, який фіксується покажчиком V. Елементи, помічені покажчиками P і V, і утворюють елементи приватного завдання, яке як і в СОРТ-1 вирішується єдиним і очевидним чином. В результаті (продумайте це!) на місце, помічене покажчиком Р, потрапить найменший елемент послідовності, повторна обробка якого виключається інкрементом покажчика Р після рішення чергової приватної задачі. Послідовне застосування викладеної процедури до частини завдання, що залишилася, гарантує, що на кожному черговому кроці до вже впорядкованих елементів додаватиметься найменший елемент з тих, що залишилися, тобто (i) послідовність упорядковуватиметься належним чином (ii) трудомісткість сортування прогресивно падатиме, оскільки після кожного кроку для перегляду і вибору найменшого залишатиметься все менше і менше елементів.
Для довгих послідовностей доцільно спочатку застосувати метод розділення завдання на рівні частини - розділити початкову послідовність дві або чотири і так далі рівних частин, і тільки потім до кожної з цих частин застосувати метод розділення на нерівні частини, зокрема у вигляді обмінного сортування. При цьому, проте, виникає нова проблема: як об'єднати приватні рішення в одне загальне і не втратити виграш! Це забезпечує алгоритм ЗЛИТТЯ (merge) - сортування по методу розділення завдання на нерівні частини, в якому приватне завдання - формування пари елементів для чергового порівняння, - вирішується з використанням стекової пам'яті.
Стеками при цьому служать приватні відсортовані рішення, і на чергове порівняння завжди поступають елементи з вершин стеків. Менший з вершинних елементів записується у вихідний список, а покажчик вершини відповідного стека зрушується (інкрементується) на одну позицію. Якщо один із стеків вичерпається раніше іншого, то елементи другого стека, що залишилися, просто дописуються у вихідний список.
Наступна схема ілюструє механізм злиття: 1) ініціюються два покажчики L, що визначає початок лівої відсортованої частини, і R, що визначає початок правої відсортованої частини; 2) далі в циклі від 1 до N кожного разу порівнюються вершинні елементи X(L) і X(R) лівого і правого стеків (у яких після введення покажчиків перетворилися відсортовані частини), у вихідний список Z виводиться менший з них, а відповідний покажчик зрушується на одну позицію: Зрозуміло, що в загальному випадку швидкість вичерпання стеків буде різна, і один із стеків спустіє раніше іншого. Тому в механізм злиття необхідно ввести 2 заглушки для перевірки вичерпання лівого і/або правого стеків: ... if L>s (вичерпаний лівий стек) then z(i)= x(R); R = R + 1 [дописати в буфер Z елементи правого стека] fi if R>n (вичерпаний правий стек) then
z(i)= x(L); L = L + 1; [дописати в буфер Z елементи лівого стека] fi ...
РЕКУРСИВНЕ СОРТУВАННЯ.
Алгоритм К. Хоара з використанням методу половинного ділення
Продовжити з к.1 поки довжина чергового лівого або правого підінтервалу не виявиться рівною одному елементу.
ЛАБОРАТОРНА РОБОТА № 7
|
|||||
Последнее изменение этой страницы: 2017-01-25; просмотров: 111; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.237.178.126 (0.019 с.) |