Сортування шляхом підрахунку

Кожний елемент порівнюється зі всіма іншими; остаточно положення елементів визначаються після підрахунку кількості менших ключів.

Треба знайти перестановку р(1) р(2)...р(n), таку, що

Кр(1)<=Кр(2)<=...<=Кр(n).

Метод заснований на тому що j-ключ впорядкованої послідовності перевищує рівно j-1 інших ключів. Ідея полягає в тому, щоб зрівняти попарно всі ключі і підрахувати, скільки з них менші від кожного окремого ключа.

Спосіб виконання поставленого завдання такий:

((порівняти Кj із Кі) при l<=j<i) при 1<i<=N.

Void sort_pidr()

{

int i,j; int a[50], a1[50];

int k[50];

for (i=0; i<50; i++)

k[i]=0;

for(i=0;i<50-1; i++)

for (j=i+1;j<50;j++)

if(a[i]<a[j])

k[i]++;

else k[j]++;

for (i=0; i<50; i++)

a1[k[i]]=a[i];

for (i=0; i<50; i++)

a[i]=a1[i];

}

Метод Шелла

Подальшим розвитком методу сортування з включеннями є сортування методом Шелла, яке інакше називається сортуванням включеннями з відстанню, що зменшується.

Метод полягає в тому, що таблиця, яка впорядковується, розділяється на групи елементів, кожна з яких упорядковується методом простих включень. У процесі впорядкування розміри таких груп збільшуються доти, поки всі елементи таблиці не ввійдуть у впорядковану групу. Вибір чергової групи для сортування і її розташування всередині таблиці здійснюється так, щоб можна було використовувати попередню впорядкованість. Групою таблиці називають послідовність елементів, номери яких утворять арифметичну прогресію з різницею h (h називають кроком групи). На початку процесу впорядкування вибирається перший крок групи h₁, що залежить від розміру таблиці. Шелл запропонував брати

h₁=[h/2], a h_i=h((i-1)/2).

У більш пізніх роботах Хіббард показав, що для прискорення процесу доцільно визначити крок h₁ за формулою:

h₁=2**k+1, де 2**k<n<=2**(k+1).

Після вибору h₁ методом простих включень впорядковуються групи, що містять елементи з номерами позицій і, i+h₁, i+2*h₁, …, i+m_i*h₁.

При цьому i=1,2,..., h₁; m[і] – найбільше ціле, що задовольняє нерівність i+m[i]*h_i <= n.

Потім вибирається крок h₂ <h₁ і впорядковуються групи, що містять елементи з номерами позицій і, i+h₂,…, i+m[i]*h₂. Ця процедура з усе зменшуваними кроками продовжується доти, поки черговий крок h[l] стане рівним одиниці (h₁>h₂>...>h_l). Цей останній етап являє собою впорядкування всієї таблиці методом включень. Але оскільки вихідна таблиця впорядковувалася окремими групами з послідовним об'єднанням цих груп, то загальна кількість порівнянь значно менша, ніж n/4, необхідна при методі включень. Кількість операцій порівняння пропорційна n*(log₂(n))**2.

Застосування методу Шелла до масиву, використаного в наших прикладах, показано в таблиці 2.

Таблиця 2 – Приклад сортування методом Шелла.

У загальному випадку алгоритм Шелла природно переформулюється для заданої послідовності з t відстаней між елементами h₁, h₂,..., h_t, для яких виконуються умови h₁ = 1 і h(i+1)< h_i При правильно підібраних t і h складність алгоритму Шелла є Θ (n(1.2)), що істотно менша за складність простих алгоритмів сортування.

Блок-схема методу Шелла подана на рисунку 15. У ньому використано змінні:

а[] – масив, який необхідно відсортувати,

t – допоміжна змінна того ж типу, що і масив,

n – розмірність масиву.

Рисунок 15 – Блок-схема методу Шелла.

Обмінне сортування

Просте обмінне сортування (≪методом бульбашки≫) для масиву a a[1], a[2], ..., а[n] працює таким чином. Починаючи з кінця масиву порівнюються два сусідні елементи (а[n] і а[n-1]). Якщо виконується умова a[n-1 ]>a[n], то значення елементів міняються місцями. Процес продовжується для a[n-l] і а[n-2] і т.ін., поки не буде здійснено порівняння а[2] і а[1]. Зрозуміло, що після цього на місці а[1] виявиться елемент масиву з якнайменшим значенням. На другому кроці процес повторюється, але останніми порівнюються а[3] і а[2]. І так далі. На останньому кроці порівнюватимуться тільки поточні значення а[n] і а[n-1]. Зрозуміла аналогія з бульбашкою, оскільки найменші елементи (≪найлегші≫) поступово ≪спливають≫ до верхньої межі масиву. Приклад сортування методом бульбашки показаний в таблиці 3.

Для методу простого обмінного сортування потрібна кількість порівнянь nх(n-1)/2, мінімальна кількість пересилань 0, а середня і максимальна кількість пересилань - Θ (n²).

Блок-схема методу бульбашки поданана рисунку 16.

Рисунок 16 – Алгоритм сортування методом бульбашки.

Таблиця 3 – Приклад сортування методом бульбашки.

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

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

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

Шейкерне сортування дозволяє скоротити кількість порівнянь (за оцінкою Кнута середньою кількістю порівнянь є (n2 - n(const + ln n)), хоча порядком оцінки як і раніше залишається n2. Кількість посилань загалом не змінюється. Шейкерне сортування рекомендується використовувати в тих випадках, коли відомо, що масив ≪майже впорядкований≫.

Таблиця 4 – Приклад шейкерного сортування.

Сортування вибором

При сортуванні масиву а[1], а[2],..., a[n] методом простого вибору серед всіх елементів знаходиться елемент з якнайменшим значенням а[і], і а[1] і а[і] обмінюються значеннями. Потім цей процес повторюється для одержуваних підмасивів а[2], а[3],..., а[n]... a[j], a[j+1],..., а[n] до тих пір, поки ми не дійдемо до підмасиву а[n], що містить до цього моменту найбільше значення. Робота алгоритму ілюструється прикладом в таблиці 5.

Для методу сортування простим вибором необхідна кількість порівнянь – n[n-1)/2. Порядок необхідної кількості посилань (включаючи ті, які потрібні для вибору мінімального елемента) у гіршому разі складає Θ (n²). Проте порядок середньої кількості пересилань є (n ln n), що у ряді випадків робить цей метод одним із найкращих.

Таблиця 5 – Приклад сортування простим вибором.

Функція сортування вибором виглядає так:

void sort_vyb()

{

Int i,j a[10],t;

for (i=0; i<10-1; i++

for (j=i+1;j<10;j++)

if(a[i]<a[j]);

{

t=a[i];

a[i]=a[j];

a[j]=t;

}

}

Сортування поділом (Хоара)

Метод сортування поділом був запропонований Чарльзом Хоаром 1962 року. Цей метод є розвитком методу простого обміну і настільки ефективний, що його почали називати ≪методом швидкого сортування - Quicksort≫.

Основна ідея алгоритму полягає в тому, що випадковим чином вибирається деякий елемент масиву х, після чого масив є видимим зліва, поки не зустрінеться елемент а[і] такий, що а[і]>х, а потім масив є видимим справа, поки не зустрінеться елемент a[j] такий, що a[j]<x. Ці два елементи міняються місцями, і процес перегляду, порівняння і обміну продовжується, поки ми не дійдемо до елемента х. У результаті масив виявиться розбитим на дві частини - ліву, в якій значення ключів будуть менші від х, і праву із значеннями ключів, більшими від х. Далі процес рекурсивно продовжується для лівої і правої частин масиву до тих пір, поки кожна частина не міститиме лише один елемент (рисунок 17). Зрозуміло, що, як завжди, рекурсію можна замінити ітераціями, якщо запам'ятовувати відповідні індекси масиву. Прослідкуємо цей процес на прикладі нашого стандартного масиву (таблиця 6).

Таблиця 6 – Приклад швидкого сортування.

Рисунок 17 – Блок-схема рекурсивного методу Хоара

Алгоритм недаремно називається швидким сортуванням, оскільки для нього оцінкою кількості порівнянь і обмінів є Θ (n log n). Насправді, в більшості утиліт, що виконують сортування масивів, використовується саме цей алгоритм.

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычис­лить, когда этот...

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: