WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Демонстрація сортування методом спливаючих бульбашок - Курсова робота

Демонстрація сортування методом спливаючих бульбашок - Курсова робота


Курсова робота
Демонстрація сортування методом спливаючих бульбашок
Зміст
Вступ 2
I Теоритичні відомості 4
1.1 Необхідність вивчення методів сортування даних. 4
1.2 Підготовча робота. 5
1.3.Найпростіші методи сортування. 6
1.4. Складніші і більш ефективні методи сортування. 11
1.5. Порівняльна характеристика методів сортування. 18
II Алгоритм реалізації проекту 20
2.1.Підготовча робота 20
2.2.Розробка частини про принцип сортування. 20
2.3.Розробка частини для виконання сортування. 22
III Лістинг програмного коду. 25
3.1.Головний модуль 25
3.2.Модуль програми 25
Висновок 32
Список використаних джерел та програмних засобів 33
Вступ
Важко собі уявити, як користуватися списками об'єктів, якщо інформація в них би не була відсортована. Процесом сортування називають дії по впорядкуванню деяких даних (таблицю) по ключу. Ключі можуть бути різними. Наприклад, перетворити:
1. Таблицю чисел за збільшенням;
2. Таблицю прізвищ - за абеткою, причому тільки по першій букві
3. Елементи, що стоять тільки на парних місцях таблиці в убуваючому порядку.
Очевидно, що з "відсортованими даними" працювати легше і швидше, ніж з довільно розташованими. Коли елементи "відсортовані", простіше знайти, наприклад, телефон товариша в телефонній книзі на 500 сторінок, швидше знайти слово в словнику на 700 сторінок.
Всі ЕОМ засновані на здібності до швидкої і точної обробки великих об'ємів інформації, а це можливо тільки коли інформація однорідна і відсортована. Таким чином, таблиці як основний засіб представлення однорідної інформації неминуче використовуються у всіх реальних комп'ютерних програмах. На табличному принципі заснована і архітектура сучасних ЕОМ: пам'ять машини можна розглядати як великий масив байтів, адреси яких розташовуються за збільшенням. Отже, без розуміння інформаційної сутності таблиць і основних алгоритмів їх обробки неможливе формування повноцінних уявлень про можливості ЕОМ і принципи їх роботи.
Для побудови скільки-небудь складних і змістовних програм необхідне упевнене володіння загальними принципами застосування таблиць і базовими прийомами їх обробки.
Тому темою даної роботи є демонстрація сортування методом "бульбашки".
Метою створити програму для ефективного подання принципів роботи алгоритму сортування.
Перед розробкою роботи були поставленні завдання:
1. Створити програму для демонстрації сортування методом "бульбашки".
2. Розглянути існючі методи сортування.
I Теоритичні відомості
1.1 Необхідність вивчення методів сортування даних.
В словниках слово "сортування" визначається як розподіл, відбір по сортах, якості, розмірах, по схожих ознаках, в програмуванні це слово традиційно використовується в більш вузькому значенні. Під сортуванням звичайно розуміють процес розміщення елементів в деякому певному порядку, як правило, в порядку зростання або спадання (коли сортованими елементами є числа) або в алфавітному порядку (при сортуванні текстової інформації).
Очевидно, що відсортованими даними легше користуватися, ніж довільно розташованими даними. Коли елементи відсортовані, їх простіше відшукати, простіше проводити з ними різні операції. У відсортованих даних легше визначити, чи є пропущені елементи. Для двох відсортованих таблиць легше знайти загальні елементи. Сортування також є могутнім засобом прискорення роботи практично будь-якого алгоритму, в якому виникає необхідність частого звернення до певних елементів. Як пише один з класиків теорії програмування Д. Кнут "Навіть якщо б сортування було майже даремне, знайшлася б маса причин зайнятися нею! Винахідливі методи сортування говорять про те, що вона і сама по собі цікава як об'єкт дослідження". Аналіз цих методів дуже корисний і з погляду навчання, оскільки з їх допомогою можна наочно проілюструвати самі різні ситуації. За словами творця мови Паскаль, Н. Вірта, "створюється враження, що можна побудувати цілий курс програмування, вибираючи приклади тільки із задач сортування". Цікавий цей клас алгоритмів ще і тим, що на ньому наочно демонструються багатющі можливості програмування: наскільки різними шляхами можна прийти до однієї мети - отримання впорядкованого масиву! На безлічі алгоритмів сортування стає зрозумілою необхідність порівняльного аналізу алгоритмів і оцінки їх якості, критеріями якого є збільшення швидкодії і економії пам'яті.
1.2 Підготовча робота.
Сортування відносяться до табличних і інших складних структур даних, тому виникає необхідність, перш за все, у вивченні цих складних структур даних, наприклад, лінійних і прямокутних масивів (таблиць). Структуру для представлення однорідної інформації в програмуванні прийнято називати масивом. (Фактично терміни таблиця і масив в даному контексті - повні синоніми).
Важливе питання, на яке треба відповідати при рішенні реальних задач, - коли слідує і коли не слід об'єднувати прості змінні в таблиці. Ключ до відповіді - розуміння таблиці як складової величини, що містить однорідну інформацію. Однорідність означає, що всі елементи таблиці равноправні: мають однаковий зміст, сенс, при обробці виконуються однакові операції.
Очевидно, що таблиця може бути результатом алгоритму(заповнення), аргументом (обробка) і аргументом-результатом (модифікація). При більш уважному розгляді стає ясно, що обробка (таблиця - аргумент) включає дуже великий клас задач, вирішуваних різними методами. Серед них можна виділити дві великі групи: задачі аналізу і задачі пошуку. В задачах аналізу вимагається проглянути всю таблицю і визначити якісь її характеристики (сума, кількість елементів із заданою властивістю і т.д.)
В задачах пошуку вимагається знайти в таблиці елемент, що володіє потрібною властивістю, причому проглядати всю таблицю для цього необов'язково. З другого боку, багато задач модифікації не вимагають освоєння спеціальних прийомів і зводяться до комбінації аналізу і заповнення.
Наприклад, відома задача про коректування звіту (елементи, меньші 100, замінити на 100) і їй подібні. Тому виділяти модифікацію як окремий клас задач не варто.
Реальний інтерес представляють задачі перестановки, в яких необхідно переставити елементи заданої таблиці відповідно до якихось вимог. Ці задачі не зводяться до інших і можуть розглядатися як самостійна група. Головна задача перестановки - це сортування елементів масиву, тобто елементи масиву необхідно переставити так, щоб вони розташовувалися, наприклад, за збільшенням. Задача сортування масивів не виникає ні звідки , а відноситься до однієї з груп задач на табличні величини. Остаточно одержуємо такі групи задач:
1. Заповнення
2. Аналіз
3. Пошук
4. Перестановка.
Фактично всі основні прийоми побудови алгоритмів формуються на лінійних таблицях. Обробка прямокутних таблиць приводить до кількісного, але не якісному ускладнення. Лінійна таблиця - цеосновне, первинне поняття, а прямокутна таблиця може бути побудований як лінійна таблиця, що складається з лінійних таблиць. Тому достатньо розглянути згадуючи, але не розбираючи детально, прямокутні. тільки лінійні таблиці, мабуть,
1.3.Найпростіші методи сортування.
Для вирішення багатьох задач із пошуку потрібного елемента, складання словників, довідників, складання лотерейних таблиць, списку учнів в журналі, зручно спочатку
Loading...

 
 

Цікаве