Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9 | Следующая страница реферата



По суті цей алгоритм працює на основі алгоритму сортування обмінами, але цей алгоритм вважається швидким, оскільки перегляд послідовності відбувається у двох напрямках одночасно. Реалізовано ж цей алгоритм за допомогою оператору “if”, який відповідає за порівняння елементів, та пересилань.

Procedure _Qsort (var a:mas; low, hi: byte);

Var i,j:byte; begin if hi> low then begin i:= low; j:= hi; x:= a[i];

While i< j do if a[i+1] right;

HoareSearch ( L, right);

HoareSearch (left, R); end;

End;

Також у програмі представлена процедура, яка відповідає за введення масиву. Вона не винесена окремо в головну програму і користувач не побачить її на своєму екрані-меню. Він побачить лише ті три сортування, що написані у вигляді процедур.

В своїй роботі ми написали програму, що сортує масив за допомогою лише трьох алгоритмів сортування. Але можна створити процедури, які б містили алгоритми сортування деревом та пірамідального сортування. Це не вплине дуже суттєво на нашу програму. Потрібно буде лише додати ці процедури оператор “Case of” головної програми і користувач зможе обирати їх і використовувати їх так само, як і ті алгоритми, що вже були розглянуті нами в нашій дослідницькій роботі.

Висновки

Отже, ми розглянули як працюють швидкі алгоритми сортування і спробували визначити їх складність.

Застосування того чи іншого алгоритму сортування для вирішення конкретної задачі є досить складною проблемою, вирішення якої потребує не лише досконалого володіння саме цим алгоритмом, але й всебічного розглядання того чи іншого алгоритму, тобто визначення усіх його переваг і недоліків.

Звичайно, необхідність застосування саме швидких алгоритмів сортування очевидна. Адже прості алгоритми сортування не дають бажаної ефективності в роботі програми. Але завжди треба пам’ятати й про те, що кожний швидкий алгоритм сортування поряд із своїми перевагами може містити і деякі недоліки.

Так, алгоритм сортування деревом, хоча й працює однаково на всіх входах
(так, що його складність в гіршому випадку співпадає зі складністю в середньому), але цей алгоритм має і досить суттєвий недолік: для нього потрібна додаткова пам’ять розміром 2n-1.

Розглядаючи такий швидкий алгоритм сортування, як пірамідальне сортування, можна зазначити, що цей алгоритм ефективніший ніж попередній, адже він сортує “на місці” , тобто він не потребує додаткових масивів.
Крім того, цей алгоритм (“ з точністю до мультиплікативної константи” (4,
74)) оптимальний: його складність співпадає з нижньою оцінкою задачі, тобто за критеріями C(n) та M(n) він має складність O(n log2 n), але містить складний елемент в умові. Тобто, в умові A[left] має бути строго менше ніж x , а A[right] - строго більше за x. Якщо ж замість “строго більше” та “строго менше” поставити знаки, що позначають “більше, або дорівнює” та “менше, або дорівнює”, то індекси left і right пробіжать увесь масив і побіжать далі. Вийти з цієї ситуації можна було б шляхом ускладнення умов продовження перегляду, але це б погіршило ефективність програми.

В нашій роботі ми розглянули деякі швидкі алгоритми сортування та їх реалізацію мовою Pascal, дослідили не лише переваги таких алгоритмів, ефективність їх використання, але й визначили деякі недоліки окремих алгоритмів, що заважають вживати їх для вирішення першої ліпшої задачі сортування.

Отже, головною задачею, яку має вирішити людина, яка повинна розв’язати задачу сортування – це визначення як позитивних, так і усіх негативних характеристик різних алгоритмів сортування, передбачення кінцевого результату. До того ж , треба враховувати головне – чи , можливо, цю задачу задовольнить один з класичних простих алгоритмів сортування.

Список використаних джерел

1. Абрамов С. А., Зима Е. В. Начала программирования на языке

Pascal. - М.: Наука, 1987.
2. Абрамов В. Г. Введение в язык Pascal: Учебное пособие для студентов вузов по специальности Прикладная математика. – М.: Наука, 1988.
3. Джонс Ж., Харроу К. Решение задач в системе Турбо-Паскаль/ Перевод с английского Улановой, Широкого. – М.: Финансы и статистика, 1991.
4. Зуев Е. А. Язык программирования Турбо Паскаль 6.0, 7.0. – М.: Радио и связь, 1993.
5. Культин Н. Б. Программирование в TurboPascal 7.0 и Delphi. - Санкт- петербург,1999.
6. Львов М. С., Співаковський О. В. Основи алгоритмізації та програмування.

– Херсон, 1997.
7. Перминов О. Н. Программирование на языке Паскаль. – М.: Радио и связь,

1988.
8. Перминов О. Н. Язык программирования Pascal. – М.: Радио и свіязь,1989.
9. Турбо Паскаль 7.0 Издание 10-е стереотипное. – Санкт-Петербург:

“Печатный Двор”, 1999.
10. Фаронов В. В. TurboPascal 7.0 . Начальный курс. – М.: “Нолидж”, 2000.

----------------------- a1

a2

Рекомендуем скачать другие рефераты по теме: ответы 11 класс, скачать контрольные работы.

Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9 | Следующая страница реферата