вний для великих масивів. Метою кожного кроку в даному методі є приміщення черговий розглянутої запису на кінцеву позицію всередині масиву. Якщо діяти таким способом, то всі записи, попередні даної, будуть мати менший ключ, в той час як всі наступні - Більший. При використанні такого методу масив завжди ділиться на два подмассіва. Анологично процес може бути застосований до кожного з цих подмассивов і повторюватися до тих пір, поки всі записи не будуть встановлені на їх кінцеві позиції. Використовуються два індекси i і j з початковими значеннями меж масиву. Порівнюються ключі K [i] і K [j], і якщо перестановка потрібно, то j зменшується на 1, і процес повторюється. У тому випадку, коли K [i]> = K [j], записи R [i] і R [j] змінюються місцями. Потім цей процес повторюється з i, збільшеним на 1, і фіксованим j до тих пір, поки не виникає інша перестановка. У цей момент j знову буде зменшено на 1, а i залишиться фіксованим, і т.д. Процес виконується до тих пір, поки i
Щоразу масив розбивається на два подмассіва, один з яких обробляється, тоді як межі другого запам'ятовуються з тим, щоб він був оброблений пізніше. У цих цілях може бути використаний стек, що представляє собою матрицю з двох стовпців. У першому стовпці зберігаються нижні межі поділюваних подмассивов, у другому - верхні кордону. Всякий раз один з отриманих в результаті поділу подмассивов піддається подальшому поділу, а межі іншого поміщаються у вільну рядок стека (зазвичай в стек поміщаються кордону більшого по довжині масиву, оскільки це зменшує необхідний розмір стека). Як тільки завершується процес поділу поточного подмассіва, тобто її довжина стане менше трьох, для поділу береться підмасив, межі якого були занесені в стек останніми. Рядок стека, в якій зберігалися ці межі, звільняється. Процес упорядкування завершується, коли стек повністю звільняється.
Поділ слід застосовувати для подмассивов, довжина яких більше 9, а короткі подмассіви впорядковувати методом вставки.
Стек займає мало місця. Наприклад, стек з 20 рядків дозволяє впорядкувати масив, що містить до 10 ** 7 результатів. Крім того, в сучасних мовах програмування при роботі рекурсивних програм занесення і витяг з стека виконується автоматично, тому рекомендується використовувати саме цей механізм. Середнє число порівнянь для даного алгоритму становить n * log (n) де n - число записів у сортованому масиві, m - розмір подмассіва, сортованої методом вставки.
Найгіршою ситуацією при використанні розглянутого алгоритму є випадок, коли масив вже відсортований. При цьому число порівнянь порядку n, тобто алгоритм не кращий за сортування вибіркою.
2.2 Опис програми " Sort "
В
Даний проект створювався за допомогою AppWizard - генератором коду, що створює робочу заготовку Windows-програми з тими компонентами, іменами класів і вихідними файлами, що були вказані через діалогові вікна. Зокрема: у закладці Project вибираємо - MFC AppWizard (exe). Потім потрібно пройти серію екранів AppWizard:
Step 1: вибираємо "Single document"
Step 2: залишаємо без зміни
Step 3: без зміни
Step 4: залишаємо тільки прапорці "3D controls", "Docking ToolBar"
Step 5: встановлюємо "As a statically linked library"
Step 6: відображає інформацію про створені класах
Після цього AppWizard згенерує код для підтримки функціональних можливостей програми на базі бібліотеки MFC, тобто створить каркас додатки. Розглянемо деякі елементи програми, створені на даному етапі:
Клас CSortApp . Об'єкт класу CSortApp представляє програму. У програмі визначається єдиний глобальний об'єкт класу CSortApp - theApp. Базовий клас CWinApp визначає основні характеристики об'єкта theApp. p> Клас CSortView . Об'єкт класу CSortView представляє основне вікно програми. Коли конструктор викликає функцію-член Create базового класу CFrameWnd, Windows створює дійсну віконну структуру, а каркас додатка пов'язує її з C + +-об'єктом. Функції ShowWindow і UpdateWindow, які є також функціями-членами базового класу, викликаються для виведення вікна на екран. p> При запуску проекту операційна система викликає в програмі функцію WinMain, а та шукає глобально сконструйований об'єкт класу, похідного від CWinApp. У будь-якому додатку, в тому числі і в "Sort", обов'язково повинна бути присутнім ця функція, на яку покладається ряд специфічних завдань. І найважливіша - створення основного вікна програми, з яким має бути пов'язаний код, здатний обробляти повідомлення, передані операційною системою цього вікна. У нашому випадку при програмуванні на Microsoft Visual C + + 6.0, з бібліотекою класів Microsoft Foundation Class (MFC) Library 6.0, ця функція прихована всередині каркаса додатки і немає необхідності в її написанні, але необхідно розуміти, що саме за допомогою неї здійснює...
