Базовий алгоритм.
Суть полягає у поділі набору на дві частини, котрі сортуються незалежно одна від одної. Розташування точки поділу залежить від вихідного порядку елементів у наборі. Елемент, що поділяє набір, визначається випадково (часто - крайній правий елемент), потім (після першого «перегляду» набору даних) розміщується у свою кінцеву позицію і виконується перегрупування набору даних наступним чином: елементи з меншим значенням поміщаються зліва, з більшим – справа. Потім кожна частина сортується окремо.
public static int next(char m[], int k, int r) {
int i = k,
j = r;
char ch = m[r], t;
while(true) {
while (m[i] < ch) i++;
while (m[--j] > ch)
if (j == k) break;
if (i >= j) break;
t = m[i]; m[i] = m[j]; m[j] = t;
}
t = m[i]; m[i] = m[r]; m[r] = t;
return i;
}
public static void sort(char m[], int k, int r) {
if (r <= k) return;
int i = next(m, k, r);
sort(m, k, i-1);
sort(m, i+1, r);
}
З поділом на три частини.
Суть полягає у поділі набору даних на три частини: елементи із значенням рівним елементу-роздільнику, що зустрічаються у лівій частині, переміщуються до лівого краю, а елементи з цим же значенням, але з правої частини, переміщуються до правого краю, потім частини сортуються окремо. (Тобто, після першого «перегляду» набору даних, зліва – менші елементи, справа – більші, а посередині – розподільник і рівні йому елементи)
public static void sort(char m[], int k, int r) {
if (r <= k) return;
char ch = m[r], temp;
int i = k, j = r, p = k, q = r;
while(true) {
while (m[i] < ch) i++;
while (m[--j] > ch)
if (j == k) break;
if (i >= j) break;
temp = m[i]; m[i] = m[j]; m[j] = temp;
if (m[i] == ch) {
temp = m[p]; m[p] = m[i]; m[i] = temp; p++;
}
if (m[j] == ch) {
q--; temp = m[q]; m[q] = m[j]; m[j] = temp;
}
}
temp = m[i]; m[i] = m[r]; m[r] = temp;
j = i-1; i = i+1;
for (int n=k; n<p; n++, j--) {
temp = m[n]; m[n] = m[j]; m[j] = temp;
}
for (int n=r-1; n>=q; n--, i++) {
temp = m[n]; m[n] = m[i]; m[i] = temp;
}
sort(m, k, j);
sort(m, i, r);
}
З розрахунком медіани з трьох елементів.
Суть – розподільник обирається випадково з трьох (в основному з першого, останнього і середнього);
Середній міняється місцями з передостаннім;
Перший, передостанній і останній елементи впорядковуються (найменший – на перше місце, найбільший – на останнє);
Сортується набір даних між першим і передостаннім елементами (знову беруться перший і останній у цьому наборі, порівнюються їх значення; );
Завершенням рекурсивного сортування є перевірка умови: якщо кількість елементів у під-наборі менше деякого встановленого значення, то сортування у такій частині даним алгоритмом ігнорується.
Сортування з’єднанням («слиянием»)
«Слияние» - це процес поєднання двох відсортованих наборів даних в один.
Алгоритми: дво-шляхового з’єднання, низхідного та висхідного сортування.
З двох відсортованих наборів даних послідовно обираються найменші (найбільші) і переміщуються у третій (і-й елемент з одного набору порівнюється з j-тим елементом з другого набору і найменший (найбільший) записується у третій). Для виконання такого сортування треба додаткова пам’ять об’ємом не менша, ніж сумарний об’єм поєднаних даних.
Альтернатива прямому сортуванню – це обмінне «з’єднання», при виконанні якого спочатку відбувається копіювання двох наборів даних в один (елементи розподіляються за зростанням назустріч один одному), а потім відбувається порівняння елементів поєднаного набору даних лівого кінця з правим і переміщення найменшого у результуючий набір даних.
public static char[] sort(char m1[], char m2[]) {
char rez[] = new char [m1.length+m2.length];
for (int i=0, j=0, k=0; k<(m1.length+m2.length); k++) {
if (i == m1.length) {
rez[k] = m2[j++]; continue;
}
if (j == m2.length) {
rez[k] = m1[i++]; continue;
}
if (m1[i] <m2[j])
rez[k] = m1[i++];
else
rez[k] = m2[j++];
}
return rez;
}
Набір даних ділиться на дві частини і виконується рекурсивне сортування обох частин, а потім їх поєднання.
Нерекурсивне сортування, виконання якого передбачає використання принципу «об’єднуй і пануй» (спочатку виконується поєднання сусідніх елементів, потім сусідніх пар, потім сусідніх подвійних пар і т.д.).
Алгоритми пірамідального сортування
Таке сортування базується на обробці такої структури даних як «черга за пріоритетом» – структури даних, у якій:
елементи визначаються ключем;
операція вставки додає елемент у кінець набору даних або на початок;
операція видалення видаляє елемент з найбільшим значенням ключа.
Використовується: а) системи планування завдань у комп’ютерних системах; б) системи моделювання.
Реалізація операцій вставки і видалення дуже сильно залежить від представлення набору даних: впорядкований чи невпорядкований, векторне чи зв’язане представлення (у вигляді масиву чи списку): невпорядковане представлення визначає «лінивий» підхід до вирішення задачі видалення елемента (коли виконання роботи відкладається до необхідного моменту); впорядковане – «енергійний» (коли заздалегідь виконується необхідний об’єм робіт, щоб забезпечити максимальну ефективність реалізації операції видалення).
Дерево, що сортує – це сукупність вузлів з ключами, що формують повне пірамідально впорядковане бінарне дерево, яке представлене у вигляді масиву.
Повне пірамідально впорядковане бінарне дерево - структура даних, в якій кожен вузол містить ключ із значенням більшим чи рівним значенню ключів вузлів-нащадків (тобто, ключ в кожному вузлі дерева менше або рівний ключу вузла, що є батьківський для нього).
Формування:
створюється корінь;
спускаючись вниз, переміщуються зліва направо, додаючи до кожного вузла попереднього рівня по два вузли даного рівня.
Представлення такого дерева у вигляді масиву формується відповідно наступному правилу: значення елемента з індексом і або більше, або рівне значенням елементів з індексами 2і та 2і+1.
Сортування
Усі алгоритми для черг за пріоритетом, що представлені у вигляді «сортуючого» дерева, працюють за правилом:
Вноситься проста зміна;
Виконується прохід по піраміді (знизу вверх для встановлення нового порядку структури даних – висхідний; зверху донизу – низхідний), із внесенням змін, що зв’язані з підтримкою структури, яку сортують.
Приклад реалізації базового сортування чергою за пріоритетом:
Створити пусту чергу -> сформувати чергу, використовуючи висхідну вставку (установку) -> видалити чергу, використовуючи низхідну вставку.
interface Ob {
void Up(int m[], int k);
void Down(int m[], int k, int n);
}
class Q implements Ob {
int mas[];
int N;
Q(int x) { mas = new int [x+1]; }
public void Up(int m[], int k) {
while ((k > 1) && (m[k/2] < m[k])) {
int t = m[k/2];
m[k/2] = m[k];
m[k] = t;
k = k/2;
}
}
public void Down(int m[], int k, int n) {
while (2*k <= n) {
int p = 2*k;
if ((p<n) && (m[p] < m[p+1]))
p++;
if (m[k] < m[p]) {
int t = m[k];
m[k] = m[p];
m[p] = t;
k = p;
}
else break;
}
}
public void ins(int elem) {
mas[++N] = elem;
Up(mas, N);
System.out.println();
for(int i=1; i<=N; i++)
System.out.print(mas[i] + "\t");
}
public int del() {
int t = mas[1];
mas[1] = mas[N];
mas[N] = t;
Down(mas, 1,N-1);
return mas[N--];
}
}
public class Sort_11 {
public static void sort(int m[]) {
Q obj = new Q(m.length);
for (int k = 0; k<m.length; k++)
obj.ins(m[k]);
for (int k=m.length-1; k>=0; k--)
m[k] = obj.del();
}
Суть алгоритму пірамідального сортування полягає у реалізації операцій вставки і видалення, що основана на алгоритмі низхідного встановлення (сортування виконується без створення додаткової структури – черги за пріоритетом; побудова сорт. дерева виконується проходженням набору даних в оберненому порядку).
Кожна позиція масиву розглядається як корінь невеликого дерева і два нащадки цього вузла (під-дерева) являють собою сорт. дерева; (originally) перегляд набору даних, котрий сортується, починається з половини і далі набір даних проглядається в оберненому порядку (до початку).
public static void Down(int m[], int k, int n) {
while (2*k <= n) {
int p = 2*k;
if ((p<n) && (m[p] < m[p+1]))
p++;
if (m[k] < m[p]) {
int t = m[k];
m[k] = m[p];
m[p] = t;
k = p;
}
else break;
}
}
public static void sort(int m[]) {
int k, N = m.length-1;
for (k = N/2; k>=0; k--)
Down(m, k, N);
while (N>0) {
k = m[0]; m[0] = m[N]; m[N] = k;
Down(m, 0, --N);
}
}
Алгоритм порозрядного сортування MSD
Суть – використання алгоритму підрахунку з розподілом для сортування цифр (порцій) ключів.
Для більш ефективної роботи можливе додавання сортування вставками, якщо кількість цифр ключів, що лишилися, менше деякого встановленого значення.
static String dop[] = new String[count];
public static int digit(String value, int nomer) {
return (value.charAt(nomer) - '0');
}
public static void sort(String m[], int le, int ri, int pos) {
int i, j, key[] = new int [6];
if (pos > 4) return;
if ((ri-le) <= 0) return;
for(j=0; j<key.length; j++) key[j] = 0;
for (i=le; i<ri; i++) key[digit(m[i], pos)+1] ++;
for(j=1; j<key.length; j++) key[j] += key[j-1];
for(i=le; i<ri; i++) dop[le+key[digit(m[i], pos)]++] = m[i];
for(i=le; i<ri; i++) m[i] = dop[i];
sort(m, le, key[0], pos+1);
for(j=0; j<key.length-1; j++)
sort(m, le+key[j], le+key[j+1], pos+1);
}
Алгоритми пошуку
Пошук – це процес отримання (вилучення) інформації (даних) з деякого інформаційного простору з ціллю її обробки. Ефективність алгоритмів пошуку інформації залежить від впорядкованості і структурованості даних. Припускається, що дані зберігаються у вигляді записів, що мають ключ, який використовується під час пошуку. Пошук інформації базується на операції порівняння, результатом якої є повідомлення про вдалий (влучення) чи невдалий (промах) пошук.
Класифікація:
Послідовний:
застосовується для набору даних, котрий організовано у вигляді масиву чи списку (впорядкованого чи ні); ключ нового елемента порівнюється з ключами існуючих елементів (послідовно елементи порівнюються, у зворотному порядку).
Бінарний пошук:
отримаємо його якщо до впорядкованого набору даних застосувати принцип «Р і П». Суть - після поділу набору даних на дві частини визначається частина, якій належать шукані дані, і потім пошук виконується у відповідній частині. Швидший за послідовний.
Інтерполяційний пошук:
Вдосконалення бінарного пошуку – отримання інформації про розташування шуканого елемента у поточному інтервалі (вибір діапазону частини набору даних визначається у залежності від значення елемента).
m
= (le+ri)/2 <-> m = le+(ri-le)*
; m
= le+(ri-le)*
.
Пошук індексуванням за ключем:
Виконується у два етапи – 1) обчислення адреси (виконується перетворення ключа у індекс масиву) -> 2) вирішення конфліктів (обробка елементів з однаковим індексом). + хешування – це компроміс між часом виконання і об’ємом пам’яті.
(приклад – хеш-таблиця з роздільним зв’язуванням - динамічна)
Із збільшенням кількості елементів у хеш-таблиці продуктивність зменшується. Для вирішення цієї проблеми використовуються динамічні хеш-таблиці (розмір хеш-таблиці подвоюється, якщо її заповнення досягає деякого встановленого проценту).