Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

Информатика->Лабораторная работа
Локальная сеть – система для непосредственного соединения многих компьютеров. При этом подразумевается, что информация передается от компьютера к комп...полностью>>
Информатика->Курсовая работа
Компактная микроэлектронная “память” широко применяется в современной электронной аппаратуре самого различного назначения. В ПК память определяют как ...полностью>>
Информатика->Дипломная работа
В настоящее время информационные технологии внедряются во всё новые и новые области нашей жизни. Если раньше их применяли сугубо в расчетно-научных це...полностью>>
Информатика->Контрольная работа
Трудовая деятельность человека связана с восприятием и накоплением информации об окружающей среде, отбором и обработкой информации при решении различн...полностью>>

Главная > Курсовая работа >Информатика

Сохрани ссылку на реферат в одной из сетей:

Даний метод мало чим відрізняється від методу "бульбашки", тому наведемо лише його реалізацію (Файл SORT_5.CPP):

#include

#include

#include

int mas[1000];

void vuv(int s)

{ for(int i=1;i<=s;i++)

cout<

cout<

}

main()

{clrscr();

cout<<"Vvedit kilkist elementiv masuvy - n"<

int n,tmp,k;

cin>>n;

for (int i=1;i<=n;i++)

{

cout<<"vvedit "<

cin>>mas[i];

}

clrscr();

cout<<"Maemo masuv "<

vuv(n);

//Sort_kamin

for (int j=1;j

for (i=1;i<=(n-j);i++)

{

if (mas[i]>mas[i+1]){

tmp=mas[i];mas[i]=mas[i+1];mas[i+1]=tmp;

}

}

cout<<"Masuv vidsortovanuy "<

vuv(n);

getch();

return 0;}

2.4.3 Метод шейкерного сортування

Якщо розглянути необхідну кількість дій, що виконується при сортуванні „бульбашковим" методом чи методом „камінця" то вона має порядок O(n2). Зовнішній цикл виконується (n-1) раз, а на кожному його кроці внутрішній цикл виконується, в середньому, n на 2 раз. Взагалі, „бульбашкове" сортування відноситься до найменш ефективних методів. Дещо покращати його можна, чергуючи порядок проходу масиву та зупиняючись, коли всі елементи відсортовано. Такий модифікований алгоритм дістав назву „шейкерного" сортування.

Нижче наведемо реалізацію цього методу (Файл SORT_6.CPP):

#include

#include

#include

int mas[1000];

void vuv(int s)

{ for(int i=1;i<=s;i++)

cout<

cout<

}

main()

{clrscr();

cout<<"Vvedit kilkist elementiv masuvy - n"<

int n,tmp,k;

cin>>n;

for (int i=1;i<=n;i++)

{

cout<<"vvedit "<

cin>>mas[i];

}

clrscr();

cout<<"Maemo masuv "<

vuv(n);

//Sort_Sheikerne

int l,r;

l=2; r=n; k=r;

while (l

{

for(int j=l;j<=r;j++)

if (mas[j]

r=k-1;

for(j=r;j>=l;j--)

if (mas[j]

l=k+1;

}

cout<<"Masuv vidsortovanuy "<

vuv(n);

getch();

return 0;

}

Аналіз алгоритмів на основі прямого обміну. Розглянемо спочатку чисту "бульбашку". Для "камінця" оцінки будуть такими ж самими. Зрозуміло, що кількість порівнянь ключів Ci на i-ому проході не залежить від початкового розміщення елементів і дорівнює N-i. Таким чином

Кількість же перестановок залежить від стартової впорядкованості масиву. В найкращому випадку початково-впорядкованого масиву Mi=0 ; в найгіршому випадку зворотно-впорядкованого масиву Mi=Ci*3; для довільного масиву рівноймовірно можливе значення Mi=Ci*3/2. Тому для оцінки ефективності алгоритму по перестановках можна скористатися наступними співвідношеннями:

;

;

.

Очевидно, що і цей алгоритм, аналогічно з іншими прямими методами, описує процес стійкого сортування.

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

Як видно, всі покращення не змінюють кількості переміщень елементів (переприсвоєнь), а лише зменшують кількість повторюваних порівнянь. На жаль операція обміну місцями елементів в пам’яті є "дорожчою" ніж порівняння ключів. Тому очікуваного виграшу буде небагато. Таким чином "шейкерне" сортування вигідне у випадках, коли відомо, що елементи майже впорядковані. А це буває досить рідко.

2.5 Порівняння прямих методів сортування масивів

З метою порівняння методів сортування масивів було виконано тестування. Для кожного методу за алгоритмом було написано підпрограму на С++, після чого виконано тестування для масивів цілих чисел розміром 1024, 4096 та 16384. Результати тестування (кількість секунд з точністю до сотих) на комп’ютері Pentium-II/450 наведено у таблиці. Для кожного розміру масиву використовувалось 3 способи його побудови:

  1. вже впорядкований за зростанням масив;

  2. масив, впорядкований за спаданням;

  3. масив з випадкових чисел.

24 4096 16384

Прямим включ. .00 0.05 0.00 .00 0.88 0.44 .00 14.01 6.98

Бінарним включ..00 0.06 0.06 .00 0.61 0.28 .05 9.67 4.83

Прямим вибором.06 0.05 0.00 .50 0.49 0.49 .30 8.46 8.29

Бульбашка/Камінець .00 0.11 0.11 .54 1.70 1.21 .73 27.79 19.45

Шейкерне .00 0.11 0.05 .00 1.71 0.99 .00 27.30 15.82

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

Розділ ІІІ. Огляд функцій сортування із стандартної бібліотеки С++

Мова програмування С++ має в своєму складі функції, які дають змогу виконувати сортування елементів довільного типу без реалізації алгоритмів. Так, функція sort має декілька версій, в базовому її варіанті прототип виглядає наступним чином:

Void sort(Iterarot begin, Iterator end);

В якості параметрів функції використовуються два ітератори довільного доступу, призначені для роботи з окремим контейнером класу. З допомогою функції sort дані контейнера впорядковуються, починаючи з елемента begin і закінчуючи елементом end (не включаючи його).

Оскільки вказівник на елемент масиву в С++ вважається ітератором довільного доступу, можна впорядкувати частину, або весь масив. Наприклад:

int mas[7]= {0, 10, 2, 0, 4, 15, 6}

//Елементи масиву будуть впорядковані. Зверніть увагу на те,

// що ім’я mas використовується в якості вказівника на перший

// елемент, mas+7, вказує на елемент, що знаходиться

// на одну позицію дальше границі масиву

sort(mas, mas+7);

Проте, дана функція підтримується лише новими компіляторами (Файл SORT_7.CPP).

#include

#include

#include

#include <algorithm.h>

int mas[1000];

void vuv(int s)

{ for(int i=1;i<=s;i++)

cout<

cout<

}

main()

{clrscr();

cout<<"Vvedit kilkist elementiv masuvy - n"<

int n,tmp,k;

cin>>n;

for (int i=1;i<=n;i++)

{

cout<<"vvedit "<

cin>>mas[i];

}

clrscr();

cout<<"Maemo masuv "<

vuv(n);

//Sort_Bibliotrchna_fukccia

sort(mas, mas+n);

cout<<"Masuv vidsortovanuy "<

vuv(n);

getch();

return 0;

}

Крім даної функції, в С++ існує ще ряд інших призначених для сортування масивів довільних типів. Наприклад, однією із перших функцій даного напрямку, що ввійшла в стандартну бібліотеку мови С була функція qsort. Проте в ній програмісту самому було потрібно написати функцію порівняння елементів для її повноцінної роботи, наприклад:

іnt compare_integers(const void* p1, const void* p2)

{

returne* ((int *)) p1)-*((int*)p2));

}

А вже маючи готову функцію порівняння, можна використовувати функцію qsort. Наприклад, для сортування масиву цілих чисел виклик функції буде мати вигляд:

int mas[7]= {0, 10, 2, 0, 4, 15, 6};

qsort((void*)mas,7,sizeof(int),compare_integer);

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

Висновки

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

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

У своїй роботі ми розглянули прямі алгоритми сортування, навели графічне відображення покрокового виконання. Також нами було розроблено ряд програм, для наочної демонстрації роботи кожного окремого методу.

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

Виконуючи дану роботу, ми прийшли до ряду висновків:

  • алгоритми прямого сортування, не є складними у розумінні, легко виконувані і прості у реалізації;

  • дані алгоритми, що ми розглянули, можна використовувати для сортування даних довільного типу, тобто ці алгоритми в певній мірі є універсальні;

  • сортування методами вибору і сортування вставками як при найгіршому, так і при середньому варіанті мають квадратичний час виконання.

  • швидкодія прямих методів сортування невелика, але якщо впорядковуваний масив є невеликим або ж сортування проводиться не часто, то ними користуватися є більш вигідно, ніж іншими алгоритмами;

  • сортування вставками дає більш відчутну перевагу, якщо вихідний масив близький до впорядкованого стану;

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

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

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

Література

  1. Айра П. Обьектно-Ориентированное прогрпммирование на С++. М.: Санкт-Петербург, 1999. – 460 с.

  2. Архангельський А.Я. С++Builder 6: Справ. Пособие. Кн.1. Язык С++. – М.: Бином, 2004. – 544 с.

  3. Глушаков С.В. Программирование на Visual C++. – М.: АСТ; Х.: Фоліо, 2003. – 726 с.

  4. Дейтел Х. Как программировать на С++. – М.: Бином, 2001. – 1152 с.

  5. Джонс Ж., Харроу К. Решение задач в системе Турбо Паскаль. М, 1991. – 709 с.

  6. Клюшин Д. А. Полный курс С++. Москва: Санкт-Петербург, 2004. – 668 с.

  7. Кнут Д.Э. Искуство програмирования, том 3. Поиск и сортировка, 3-е изд.: Пер. с англ.: Уч. Пос. – М.:Издательский дом "Вильямс", 2000. – 750 с.

  8. Ковалюк Т.В. Основи програмування. Київ: Видавнича група ВНV, 2005. – 385 с.

  9. Культин Н. Б. С/С++ в задачах и примерах. – М., 2002. – 288 с.

  10. Кучеренко В. Язык программирования С++ для начинающих и не только. – М.: Майор, 2001. – 160 с.

  11. Львов М. С., Співаковський О. В. Основи алгоритмізації та програмування. Херсон, 1997.

  12. Марченко А.И., Марченко Л.А. Программирование в среде Turbo Pascal 7.0. К.: ВЕК, 2000. – 441 с.

  13. Мешков А.В. Visual C++ u MFC. - М, 2003. – 1040 с.

  14. Павловская Т.А. С/С++: Программирование на языке высокого уровня: Учебник для студ. ВУЗ. М, 2002. – 464 с.

  15. Секунов Н.Ю. Самоучитель Visual C++. М., 2002. – 735 с.

  16. Франка П. С++: Учебный курс. М., 2002. – 521 с.

  17. Щедріна О.І. Алгоритмізація та програмування процедур обробки інформації. К., 2001. – 240 с.




Похожие работы:

  1. Порівняльний аналіз ефективності та складності алгоритмів пошуку елементів у масивах

    Курсовая работа >> Информатика
    ... на тему: "Порівняльний аналіз ефективності та складності алгоритмів пошуку елементів ... Прямий пошук підрядка 2.2 Алгоритм Рабіна-Карпа 2.3 Алгоритм ... і елементів у певному масиві, множині або структур ... використаних операцій провести сортування масиву даних, а ...
  2. Порівняльний аналіз ефективності та складності алгоритмів сортування файлів і послідовностей

    Курсовая работа >> Информатика
    ... на тему: Порівняльний аналіз ефективності та складності алгоритмів сортування файлів і послідовностей Зміст Вступ 1. Сортування прямим злиттям 2. Природне ...
  3. Курс лекций по Логістика

    Реферат >> Логика
    ... прямий вплив здійснюють обсяг (маса), ... від тривалості та складності: сталі закуп ... порівняльний аналіз традиційної та логістичної концепції організації виробництва. Таблиця 5.1 Порівняльний анал ... більш ефективними способами; - висока ефективність забезпечення ...
  4. Контролінг на підприємстві

    Конспект >> Менеджмент
    ... прямі. До прямих витрат належать прямі матеріальні витрати, прямі витрати на оплату праці та ... сортування ... порівняльний аналіз. Порівняльний аналіз використовують для визначення розмірів і причин відмінностей у використанні ресурсів і ефективност ... складності ...
  5. Інформаційні системи в економіці

    Учебное пособие >> Экономика
    ... Сортування; ... та анал ... аналітичних систем прогнозування по ступені складност ... масивів або їхні назви і головне призначення; найважливіші алгоритми ... або прямими вимогами ... порівняльної важливості задоволення одних потреб і ігнорування інших, порівняльної ефективност ...

Хочу больше похожих работ...