Поиск

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

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

Информатика->Доклад
Использование баз данных и информационных систем становиться неотъемлемой составляющей деловой деятельности современного человека и функционирования п...полностью>>
Информатика->Реферат
С прогрессом информационных технологий появляются всё новые и новые проблемы в плане защиты компьютерных систем Одной из таких проблем являются вирусы...полностью>>
Информатика->Закон
Актуальность темы исследования Стремительное развитие компьютерных технологий и широкое использование электронно-вычислительных систем практически во ...полностью>>
Информатика->Курсовая работа
Практически каждый пользователь компьютера встречается с необходимостью подготовки тех или иных документов – писем, статей, служебных записок, отчетов...полностью>>

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

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

Розділ ІІ. Прямі методи сортування масивів

2.1 Сортування прямим включенням

В основі розглядуваного методу лежить пошук для чергового елемента масиву відповідного місця у відсортованій частині із наступним включенням його в знайдену позицію. Таким чином елементи масиву умовно діляться на дві групи - вже "готову" послідовність mas[1], mas[2], … ,mas[i] та вихідну послідовність. На кожному етапі, починаючи з i=2 та збільшуючи i кожен раз на 1, із вихідної послідовності вибирається один елемент і вставляється в потрібне місце у вже впорядковану послідовність. Очевидно, що початкова ліва послідовність буде "готовою", оскільки одноелементний масив завжди впорядкований. Продовжуючи по аналогії, в кінці-кінців отримаємо впорядкований список, що містить всі елементи масиву, а новий список відповідно збільшиться. Для реалізації цього алгоритму можна використовувати інший масив, куди будуть добавлятися скопійовані в потрібне місце елементи другого масиву, а можна використовувати той же масив, адже зрозуміло, що один масив росте із тією ж швидкістю що і інший зменшується.

Даний алгоритм можна показати наочно наступним чином:

Розглянемо реалізацію даного алгоритму на нашому масиві. Нехай маємо 7 елементів масиву mas із індексами від 0 до 7. Елемент mas[0] відіграє роль бар’єра, що використовуватиметься нами для обміну елементами і спростить реалізацію алгоритму. Використання додаткового елемента в масиві - "бар’єра" mas[0]=x забезпечує гарантоване припинення процесу просіювання. Це дозволяє зменшити кількість логічних умов в заголовку циклу while до однієї, а кількість логічних операцій від 2i-1 до i на кожному етапі. Звичайно, при цьому необхідно попередньо розширити на один елемент масив a та діапазон допустимих значень індексу. На жаль, таке покращення ефективності по кількості порівнянь не зменшує об’єму перестановок елементів.

Елемент масиву mas[1], виділений, щоб підкреслити те, що навіть в вихідному стані цю область можна розглядати як невеликий, окремо-впорядкований масив. Фактично, робота алгоритму починається із другого елемента масиву mas[2], до "впорядкованого масиву", в якому тепер будуть знаходитися два елементи.

Таким чином, перші два елементи (2, 8) утворюють невеликий впорядкований список, и нам необхідно додати до нього решту елементів (5, 3, 10, 7, 1). Після добавлення числа 5 отримаємо наступну картинку.

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

For (i=2;i

Вставити елемент mas[i] в упорядковану частину масиву

Операція вставки елемента mas[i] виконується в три кроки, що ми зараз і продемонструємо для і=4.

1. Зберігаємо копію вставляємого числа. В даному прикладі елемент mas[4] копіюємо в mas[0], який ми спеціально для цього і не використовували для запису масиву.

2. Проводимо здвиг вправо елементи, розміщені до mas[i], поки не буде знайдено потрібне місце під вставку елемента. В нашому випадку спочатку потрібно здвинути вправо число 8, а потім – число 5, як показано на рисунку.

3. Помістити нове значення на потрібне місце. Для даного прикладу число 3 вставляємо в масив із mas[0].

Процес просіювання (пошуку потрібного місця для включення елемента x ) може припинитися при виконанні однієї із двох умов :

1) знайдено елемент a j з ключем, меншим ніж ключ у x ;

2) досягнутий лівий кінець "готової" послідовності.

Таким чином програмна реалізація методу прямого включення матиме вигляд (Файл SORT_1.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_prjamojy vstavkojy

for (int j=2;j<=n;j++)

{

tmp=mas[j]; mas[0]=tmp; i=j;

while (tmp

{

mas[j]=mas[j-1];

j--;

}

mas[j]=tmp;

}

cout<<"Masuv vidsortovanuy "<

vuv(n);

getch();

return 0;

}

Аналіз прямого включення. Кількість порівнянь ключів Ci при i-ому просіюванні найбільше дорівнює i, найменше - 1, а середньоймовірна кількість - i/2. Кількість же перестановок (переприсвоєнь ключів), включаючи бар’єр, Mi=Ci+2. Тому для оцінки ефективності алгоритму у випадках початково впорядкованого, зворотньо впорядкованого та довільного масиву можна скористатися наступними співвідношеннями:

;

;

;

;

;

.

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

2.2 Сортування бінарним включенням

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

{l=1;r=j;tmp=mas[j];

while (l

{

m=(r+l)/2;

if (mas[m]<=tmp) l=m+1; else r=m;

}

Нехай маємо впорядкований масив (8, 9, 10, 16, 18, 20, 35), покажемо жирним рух по бінарному дереву, для знаходження місця елементу = 19.

Програмна реалізація такого модифікованого методу включення матиме вигляд наступної програми (Файл SORT_2.СРР):

#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_binarn vstavkojy

int l,r,m;

for (int j=2;j<=n;j++)

{l=1;r=j;tmp=mas[j];

while (l

{

m=(r+l)/2;

if (mas[m]<=tmp) l=m+1; else r=m;

}

for (i=j;i>=(r+1);i--) mas[i]=mas[i-1];

mas[r]=tmp;

}

cout<<"Masuv vidsortovanuy "<

vuv(n);

getch();

return 0;

}

Аналіз бінарного включення. Зрозуміло, що кількість порівнянь у такому алгоритмі фактично не залежить від початкового порядку елементів. Місце включення знайдено, якщо L=R. Отже вкінці пошуку інтервал повинен бути одиничної довжини. Таким чином ділення його пополам на i-ому етапі здійснюється log(i) раз. Тому кількість операцій порівняння буде:

, де , .




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

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

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

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

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

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

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

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