Лабораторна робота №8 (2 год)
модуль 1
Тема: Реалізація абстрактного типу даних «Сортування масивів».
Мета: формування навичок роботи з абстрактними типами даних
Література:
Архангельский А.Я. Язык Pascal и основы программирования в Delphi
Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.– М.: Мир, 1979.– 536 с.
Культин Н.Б. Turbo Pascal в задачах и примерах
М.С.Львов, О.В. Співаковський. Основи алгоритмізації та програмування.
Марченко А.И., Марченко Л.А. Программирование в среде Turbo Pascal 7.0
Меженный О.А. Turbo Pascal
Немцова Т.И., Голова С.Ю., Абрамова И.В. Программирование на языке высокого уровня. программирование на языке Object Pascal
Окулов С.М. Основы программирования.– М.: ЮНИМЕДИАСТАЙЛ, 2002.– 424 с.
Павловская Т.А. Паскаль. Программирование на языке высокого уровня
Пильщиков В.Н. Сборник упражнений по языку Паскаль. Москва, Наука, 1989 г., 160 с.
Короткі теоретичні відомості
Концептуально важливими теоретичними поняттями, сформованими у рамках структурного програмування, стали поняття структури даних і абстрактного типу даних (АТД).
Структура даних складається з трьох основних компонент:
Набір предметно-орієнтованих операцій для обробки специфічних типів абстрактних об’єктів предметної області, що описується.
Структура пам’яті, у якій зберігаються дані, що описують абстрактні об’єкти.
Інтерпретація (реалізація) кожної з операцій у термінах структури пам’яті.
Перша компонента визначення – набір операцій над абстрактними об’єктами – називається абстрактним типом даних. Друга і третя компоненти разом складають реалізацію структури даних.
АТД визначає, що робить структура даних – які операції вона підтримує, але не розкриває, як вони виконуються.
Постановка задачі сортування послідовності
Під сортуванням послідовності розуміють процес перестановки елементів послідовності у певному порядку. Мета такого впорядкування – полегшення подальшої обробки даних (наприклад, задачі пошуку). Тому задача сортування – одна з найбільш важливих внутрішніх задач програмування.
Цікаво, що сортування є ідеальним прикладом великої кількості різних алгоритмів, розв’язку однієї і тієї ж задачі. Розглядаючи різні методи сортування, ми побачимо, як зміни алгоритма призводять до нових, більш ефективних у порівнянні з простими, розв’язками задачі сортування.
Крім того, послідовності можна представити різними структурами даних. Як і слідує очікувати, ефективність алгоритмів виявляється дуже залежить від реалізації послідовності.
Нехай дано послідовність елементів a1, a2, ... , an. Елементи цієї послідовності – дані довільного типу, на якому визначено відношення порядка “<<” (менше) таке, що будьякі два різних елемента можна порівняти. Сортування означає перестановку елементів послідовності ak1, ak2, ... , akn таку, що ak1 << ak2 << ... << akn.
Приклад: послідовність документів, кожен з яких містить інформацію про людину, включаючи його вік. Необхідно розташувати документи цієї послідовності у порядку збільшення віку.
Сортування масивів
Якщо послідовність a1, a2, ... , an реалізована як масив a[1..n], вся вона розташована в адресній пам’яті. Тому поряд з вимогою ефективності за часом основна вимога – економне використання пам’яті. Це означає, що алгоритм не повинен використовувати додаткових масивів і пересилань з масива a у ці масиви.
Постановка задачі сортування у загальному вигляді пердбачає, що існують тільки два типа дій з даними типа, що сортуємо: порівняння двох елементів (x << y) і пересилання елемента (x := y). Тому зручна міра складності алгоритма сортування масива a[1..n] за часом – кількість порівнянь C(n) і кількість пересилань M(n).
Відомі алгоритми сортування масивів діляться на прості і швидкі (ефективні). Незалежно від належності тому чи іншому класу, алгоритми, що розглядаються, використовують на практиці.
Задачі для самостійного розв’язування
Складіть програму сортування за спаданням лінійного масиву методом обміну, так щоб в результаті одного лінійного перегляду масива максимальний елемент спливав на початок.
Складіть програму сортування за зростанням лінійного масиву методом обміну, так щоб в результаті одного лінійного перегляду масива мінімальний елемент спливав на початок.
Складіть програму сортування за спаданням лінійного масиву методом обміну, так щоб в результаті одного лінійного перегляду масива мінімальний елемент спливав у кінець.
Складіть програму сортування за спаданням лінійного масиву методом вибору з пошуком максимального елемента.
Складіть програму сортування за зростанням лінійного масиву методом вибору з пошуком максимального елемента.
Складіть програму сортування за спаданням лінійного масиву методом вибору з пошуком мінімального елемента.
Складіть програму сортування за спаданням лінійного масиву методом вставок.
Дано дійсна матриця розміру n(m; впорядкувати (переставити) рядки матриці за неспаданням значень перших елементів рядків.
Дано дійсна матриця розміру n(m; впорядкувати (переставити) стовбці матриці за незростанням значень мінімальних елементів цих стовбців.
Дано дійсна матриця розміру n(m; впорядкувати (переставити) рядки матриці за незростанням суми елементів рядків.