Методи сортування

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Вступ

Мову програмування Паскаль для навчання студентів основам програмування створив у 1968-1971 рр. швейцарський учений Ніклаус Вірт з кафедри інформатики Стенфордського університету. Таку назву вона отримала на честь відомого французького математика, фізика та філософа Блеза Паскаля.

Переваги мови програмування Паскаль:

· Простий синтаксис мови - програми на Паскалі легко читати та редагувати, оскільки вони містять невелику кількість базових понять;

· Досить низькі апаратні та системні вимоги, як для роботи самого середовища програмування, так і для програм, записаних мовою Паскаль;

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

· Підтримка структурного та об'єктно-орієнтованого програмування.

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

Проте, спочатку мова мала ряд обмежень: неможливість передачі функцій масивів змінної довжини, відсутність нормальних засобів роботи з динамічною пам'яттю, обмежена бібліотека вводу-виводу, відсутність засобів для підключення функцій написаних на інших мовах, відсутність засобів роздільної компіляції і т. п. Докладний розбір недоліків мови Паскаль того часу, був виконаний Брайаном Керніганом у статті «Чому Паскаль не є моєю улюбленою мовою програмування?» (ця стаття вийшла на початку 1980-х, коли вже існувала мова Модула-2, нащадок Паскаля). Деякі недоліки Паскаля були виправлені в ISO-стандарті 1982 року, зокрема, в мові з'явилися відкриті масиви, що дали можливість використовувати одні і ті ж процедури для обробки одновимірних масивів різних розмірів.

Необхідно зауважити, що багато недоліків мови не виявляються або навіть стають достоїнствами при навчанні програмуванню. Крім того, порівняно з основною мовою програмування в академічному середовищі 1970-х (яким був Фортран, що володів набагато більш істотними недоліками), Паскаль представляв собою значний крок вперед.

Паскаль, в його первісному вигляді, представляє собою чисто процедурну мову і включає в себе безліч алголоподібних структур і конструкцій з зарезервованими словами на зразок if, then, else, while, for, і т.д. Проте, Паскаль також містить велику кількість можливостей для структурування інформації та абстракцій, які відсутні в початковому Алгол-60, такі як визначення типів, записи, покажчики, перерахування. Ці конструкції були частково успадковані або інспіровані від мов Симула -67, Алгол-68, створених Никлаусом Віртом AlgolW та запропоновано Хоаром.

У сучасних діалектах (Free Pascal) доступні такі операції як перевантаження операторів і функцій.

Об'єктно-орієнтоване програмування (ООП) - це технологія створення складного програмного забезпечення, яке засноване на представленні програми у вигляді сукупності об'єктів, кожний з яких є екземпляром певного класу, а класи утворюють ієрархію зі спадкуванням властивостей.

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

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

Найбільш відомою реалізацією Паскаля, що забезпечила широке поширення і розвиток мови, є Turbo Pascal фірми Borland, що виросла потім у об'єктний Паскаль для DOS (починаючи з версії 5.5) і Windows, і далі в Delphi, в якій були впроваджені значні розширення мови.

Діалекти Паскаля, застосовані в Turbo Pascal для DOS і Delphi для Windows, стали популярні через відсутність інших успішних комерційних реалізацій.

В 1992 році фірма Borland International представила користувачам чергову версію мови програмування Паскаль - Турбо Паскаль 7.0. Поряд з усіма перевагами, які Турбо Паскаль 7.0 успадкував від попередньої версії Турбо Паскаль (багатовіконний режим роботи, можливість використання миші, можливість використання при написанні програм мови програмування низького рівня Асемблер, можливість створювати об'єктно-орієнтовані програми), у ньому були зроблені зміни й поліпшення.

По-перше: з'явилася можливість виділяти певними кольорами різні елементи вихідного тексту (зарезервовані слова, ідентифікатори, числа й т.і.), що дозволяє навіть недосвідченим користувачам усувати помилки на етапі введення вихідного тексту. По-друге: мова програмування Турбо Паскаль 7.0 була розширена (з'явилася можливість використовувати типізований адресний оператор, відкриті масиви й рядки й т. п.), що надало користувачеві додаткових можливостей при розв'язанні повсякденних завдань. По-третє: був поліпшений компілятор, внаслідок чого «коди програм» стали більш ефективними. По-четверте: був поліпшений інтерфейс користувача. Крім того, у Турбо Паскалі 7.0 розширені можливості об'єктно-орієнтованого програмування (зокрема, розширені й поліпшені можливості Turbo Vision).

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

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

1. Актуальність теми

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

2. Еволюція сортування

сортування програма паскаль

Сортування-це впорядкування набору однотипних даних за зростанням або спаданням.

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

Вперше проблема сортування даних в великих масивах виникла в США в середині ХІХ століття. В 1840 році там був створений центральний офіс перепису населення, куди надходили всі вхідні дані із всіх штатів. В ході перепису було опитано 17 069 453 чоловік, причому кожна анкета містила в собі по 13 питань. Об'єм отриманих даних був настільки великим, що їх обробка традиційним ручним способом потребувала б великих затрат праці і часу. Ситуація погіршилась в зв'язку з необхідністю проведення постійних перевірок і перерахунків, через допущені помилки при ручному сортуванні даних. З кожним новим переписом, який проводився раз в десять років, об'єм оброблюваної інформації, а разом з ним вартість і тривалість обробки даних зростали. Таким чином, ручна обробка даних перепису населення 1880 року (50 189 209 чоловік) потребувала залучення сотень працівників і тривала сім з половиною років.

Перед переписом 1890 року для рішення проблеми сортування даних в дуже великих масивах інформації, за ініціативою бюро перепису, був проведений конкурс на краще електромеханічне обладнання для сортування, яке б зробило обробку даних більш ефективною-більш точною, швидкою і дешевшою. Переможцем конкурсу став американський інженер і винахідник Герман Холлеріт, який розробив обладнання для роботи з перфокартами-електричну табуляційну систему, яка згодом стала відомою як Hollerith Electric Tabulating System. Використання цього обладнання при переписах населення США в 1890 і 1900 роках було визнане дуже успішним.

Ось так були описані переваги машини Холлеріта в російському журналі «Вестник Опытной Физики и Элементарной Математики» в 1895 році: «Переваги машини Холлеріта полягають:

а). в значному прискоренні і знеціненні роботи. При ручному способі можна розкласти і підрахувати не більше 400 карток за годину. Якщо прийняти до уваги те, що в Російській імперії 120 мільйонів жителів, то для виготовлення однієї тільки звідної таблиці буде потрібно не менше 300 000 годин. Машина скорочує кількість роботи майже в 5 разів;

б). в більшій точності результатів;

в). в більш легкому способі отримання складних звідних таблиць. Після небагатьох пропусків через машину всіх карток, в результаті отримуємо більш повні і різні таблиці, складання яких було практично неможливим при колишніх методах;»

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

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

Наступний етап розвитку методів і алгоритмів сортування розпочався на початку 1940-х років з появленням перших електронних обчислювальних машин (далі ЕОМ). Фантастична, на той час, швидкодія ЕОМ викликала зацікавленість до нових алгоритмів сортування, які вже пристосовані до машинної обробки. В 1946 році вийшла перша стаття про алгоритми сортування даних, автором якої був Джон Уільям Мочлі - американський фізик і інженер, один із творців першого в світі електронного цифрового комп'ютера загального призначення ENIAK. В цій статті розглядався цілий ряд нових алгоритмів сортування, в тому числі метод бінарних вставок. До середини 1950-х років найбільш розповсюдженими були модифікації сортування злиттям і вставкою. Ще одним наслідком переходу до сортування даних за допомогою ЕОМ став поділ сортування на два типи - зовнішнє і внутрішнє, тобто на те, що використовує і не використовує дані на периферійних пристроях.

В середині 1950-х років з розробкою ЕОМ другого покоління почався активний розвиток алгоритмів сортування. Основними причинами цього стали:

· значне спрощення і прискорення написання програми для комп'ютерів, в результаті розробки перших мов програмування високого рівня (Фортран, Алгол, Кобол);

· підвищення доступності комп'ютерів, в зв'язку з різким зменшенням їх габаритів і вартості, і як наслідок широке їх розповсюдження;

· збільшення продуктивності комп'ютерів до 30 тичся операцій в секунду.

В 1959 році Дональд Левіс Шелл запропонував метод сортування зі спадним кроком, в 1960 році Чарльз Ентоні Річард Хоар розробив метод швидкого сортування, в 1964 році Дж.Уільямс - метод пірамідального сортування. Багато з розроблених в той період алгоритмів (наприклад, швидке сортування Хоара) широко використовуються і в наш час. Підсумки етапу активного розвитку алгоритмів сортування підвів в 1973 році Дональд Ервін Кнут в третьому томі своєї монографії «Мистецтво програмування».

На початку 1970-х років використовувалися наступні види алгоритмів сортування: сортування підрахунком, вставкою, обміном, вибором, злиттям та розподілом.

Найбільша кількість розроблених до того часу методів відносилась до сортування методом вставки (метод простих вставок, бінарні і двошляхові вставки, метод Шелла, вставка в список, сортування з вирахуванням адреси і тому подібне), обміном (метод бульбашки і його модифікації, паралельне сортування Бетчера, швидке сортування, порозрядне сортування обміном, асимптотичні методи) і сортування методом вибору (пірамідальне сортування, метод виключення найбільшого із включеного, метод зв'язаного представлення пріоритетних черг).

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

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

В період з середини 1970-х до 1990-х років були досягнуті значні успіхи в збільшенні швидкості сортування за рахунок підвищення ефективності вже відомих на той час алгоритмів, шляхом їхнього доопрацювання чи комбінування. Наприклад, нідерландський вчений Едсгер Дейкстра в 1981 році запропонував алгоритм плавного сортування, який є покращенням пірамідального сортування. Другим напрямом вдосконалення алгоритмів сортування став пошук оптимальних вхідних послідовностей для різних методів сортування, що дозволяло значно скоротити його час. Третім напрямком (який найбільше розвивався) було рішення задачі сортування в класі паралельних алгоритмів, для чого не тільки узагальнювалися раніше відомі парадигми, але й розроблювалися принципово нові алгоритми. Розвиток даного напрямку характеризувався все більш широким використанням сортуючих мереж, а також багатовимірних обчислювальних решіток.

Для нинішнього етапу розвитку способів і методів сортування характерне дослідження:

- задач сортування на частково впорядкованих множинах;

- задач розпізнавання частково впорядкованої множини М;

- задач сортування частково впорядкованої множини з використанням результатів попарних порівнянь елементів;

- задач визначення порядку на множині М без апріорної інформації.

Актуальність даних задач обумовлена виникненням і розповсюдженням комп'ютерів з надскладними мікропроцесорами та високоефективних мережевих комп'ютерних систем.

Таким чином, досліджуючи еволюцію способів і алгоритмів машинного сортування даних в масивах, можна виділити наступні 5 етапів:

1. Перший етап почався в 1870 році і тривав до початку 1940-х років. Його ознаменував перехід від ручного сортування до сортування за допомогою статистичних табуляторів. При цьому використовувався алгоритм порозрядного сортування.

2. Другий етап - з початку 1940-х років до середини 1950-х. На заміну лічильно-перфораційним машинам прийшли ЕОМ першого покоління, для яких був розроблений ряд нових алгоритмів сортування. Відбулося їх розділення на внутрішні та зовнішні. Найбільш розповсюдженими на той період були модифікації сортування злиттям і вставкою.

3. Третій етап розпочався в середині 1950-х років і продовжувався до середини 1970-х років. Для нього був характерний активний розвиток алгоритмів сортування - зовнішнього і внутрішнього, стійкого і нестійкого. Багато з них використовуються і сьогодні. Найбільша кількість розроблених до того часу методів відносилась до сортування шляхом вставки, обміну і вибору.

4. Четвертий етап продовжувався з середини 1970-х років до середини 1990-х років. Поява обчислювальних центрів, що об'єднували потужності окремих обчислювальних машин і дозволяли працювати з поділом часу потребувала розробки нових алгоритмів і модифікації вже існуючих. Почалося дослідження задач сортування в класі паралельних алгоритмів, були досягнуті значні успіхи в збільшенні швидкості сортування за рахунок підвищення ефективності уже відомих на той час алгоритмів шляхом їх доопрацювання та комбінування. Одночасно відбувався пошук оптимальних вхідних послідовностей для різних методів сортування, що дозволяло значно скоротити його час.

5. П'ятий етап почався з середини 1990-х років і продовжується до сьогоднішніх днів. Особливу актуальність отримало дослідження задач сортування на частково впорядкованих множинах, задач розпізнавання частково впорядкованої множини, задач сортування частково впорядкованої множини М з використанням результатів попарних порівнянь елементів, а також задач визначення порядку на множині М без апріорної інформації. Актуальність цих задач пояснюється появою і широким розповсюдженням комп'ютерів на надскладних мікропроцесорах з паралельно-векторною структурою, а також високоефективних мережевих комп'ютерних систем.

Размещено на Allbest.ru