потрібно, елементи міняються місцями, щоб виконувалася властивість купи і властивість послідовності), поки не досягне розміру початкового масиву. І з цього моменту крайній правий елемент в послідовності куп буде найбільшим для будь купи, а, отже, буде перебувати на вірною, кінцевій позиції. Потім послідовність куп зменшується до купи з одним елементом за допомогою видалення крайнього правого вузла і зміни позицій елементів для відновлення стану купи. Як тільки залишиться купа з одним елементом, масив буде відсортований.
Необхідно дві операції: збільшення послідовності куп шляхом додавання елемента праворуч і зменшення шляхом видалення крайнього правого елемента (кореня останньої купи), зі збереженням стану купи і послідовності куп.
Збільшення послідовності куп шляхом додавання елемента праворуч досягається за таких умов:
· Якщо дві останні купи мають розміри L (x + 1) і L (x) (двох послідовних чисел Леонардо), новий елемент стає коренем купи більшого розміру, рівного L (x + 2). Для неї властивість купи необов'язково.
· Якщо розміри двох останніх куп не рівні двом послідовним числам Леонардо, новий елемент утворює нову купу розміром 1. Цей розмір вважається рівним L (1), крім випадку, коли крайня права купа вже має розмір L ( 1), тоді розмір нової одноелементної купи думають рівним L (0).
Після цього має бути відновлене виконання властивостей купи і послідовності куп, що, як правило, досягається за допомогою різновиди сортування вставками:
· Крайня права купа (сформована останньої) вважається «поточної» купою.
· Поки зліва від неї є купа і значення її кореня більше значення поточного кореня і обох коренів куп-нащадків:
· Виконується «просівання», щоб виконувалася властивість купи:
Операція просіювання значно спрощена завдяки використанню чисел Леонардо, так як кожна купа або буде одноелементної, або буде мати двох нащадків. Немає потреби турбуватися про відсутність однієї зі куп-нащадків.
Зменшення послідовності куп шляхом видалення елемента праворуч досягається за таких умов:
Якщо розмір крайній правій купи дорівнює 1 (тобто L (1) або L (0)), ця купа просто видаляється. В іншому випадку корінь цієї купи віддаляється, купи-нащадки вважаються елементами послідовності куп, після чого перевіряється виконання властивості купи, спочатку для лівої купи, потім - для правої.
1.4 Постановка завдання
Назва програми: Програма сортування методами вибору
Призначення розробки: Виходячи з введених користувачем даних впорядкувати трьома методами сортування: вибіркою, пірамідально, плавною.
Вхідні дані вводяться користувачем в спеціальні поля. Після обробки та виконання сортування програма виводить результат у відповідне поле виводу.
Для коректної роботи програми потрібно заповнити всі необхідні поля. Для реалізації даної програми ми використовуємо мову програмування C #, на платформі Visual Studio.
Системні вимоги до ПК:
) Операційна система Windows 7 або вище.
) Вільне місце на жорсткому диску: 10Мб і більше.
) Наявність Net.Framework 4.0 або вище.
) Оперативна пам'ять 512Мб і вище.
) Клавіатура і миша.
2. ТЕХНОЛОГІЯ РОЗРОБКИ ДОДАТКИ
2.1 Алгоритм рішення
На самому початку виконання програми з'являється форма, де користувачеві пропонується заповнити відповідні поля необхідними для розрахунку даними.
Потім, в ході виконання програми проводиться перевірка повноти та коректності введених початкових даних. Якщо вихідні дані не пройшли перевірку - виводиться відповідне повідомлення.
Після успішно пройденої перевірки, програма починає сортувати отримані дані. Програма зчитує дані, заповнені в спеціальних полях і робить сортування за встановленими алгоритмами.
Після цього результати виводяться у спеціально відведене поле, а виконання програми припиняється.
2.2 Макет програми
Макет додатки «Методи сортувань вибором» (Form1)
Малюнок 7. Макет додатки.
richTextBox1 - отримує введений користувачем масив, або автоматично генерований за допомогою кнопки «Згенерувати»
button1 - приймає текстове значення «Згенерувати», а також генерує в поле richTextBox1 рандомний масив від 0 до 100.
...
