Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Швидке сортування
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2026
Тип роботи:
Інші
Предмет:
Інші
Частина тексту файла (без зображень, графіків і формул):
Швидке сортування (Чарльз Хоар, 1962)
Ідея цього методу полягає в тому, що список L = <l1, l2, …, ln> реорганізується в списки L', L'' де L' - список, максимальний елемент якого є не більший за мінімальний елемент списку L''. Надалі до списків L', L'' застосовується упорядкування швидким сортуванням рекурсивно.
Приклад.
Впорядкувати за зростанням масив: 42, 55, 12, 44, 94, 18, 06, 67
Використовуємо алгоритм швидкого сортування.
На початку беремо як список весь масив. Кількість елементів – n=8 (від 0-го до 7-го).
Середній елемент – 4-й (n/2 = 8/2 = 4).
Послідовність дій для кожного списку
Обчислюємо медіану (v) – середнє значення з 3-х елементів – двох розташованих по краях (a[0] = 42, a[n-1] = 67) і розташованого посередині (a[n/2] = 94)
v (42, 94, 67) = 67 – медіана
Тоді починаємо рухатись по елементах у зустрічних напрямках:
від початку списку (i=0) – вперед, збільшуючи i;
При цьому шукаємо т.зв. великі елементи (більші або рівні медіані)
Знаходимо число 94, зупиняємось (i=4).
від кінця списку (j=7) – назад, зменшуючи j;
При цьому шукаємо т.зв. малі елементи (менші або рівні медіані)
Знаходимо число 67, зупиняємось (j=7).
42, 55, 12, 44, 94, 18, 06, 67
i=4 j=7
Оскільки EMBED Equation.3 міняємо ці елементи місцями
42, 55, 12, 44, 67, 18, 06, 94
Продовжуємо рух далі:
- по i – зупиняємось на числі 94 (i=7);
- по j – зупиняємось на числі 06 (j=6);
42, 55, 12, 44, 67, 18, 06; 94
j=6 i=7
Оскільки умова EMBED Equation.3 не виконується, ми знайшли точку, у якій можна поділити список на 2 нові списки: p = j = 6 (позначена кольором і символом “;”).
Будь-який елемент з лівого списку не перевищує жодного елемента з правого.
Якщо у списку є лише 2 елементи – порівнюємо і міняємо місцями (якщо треба); якщо 1 – лишаємо на місці (у нашому прикладі – правий список).
Для кожного нового списку з числом елементів EMBED Equation.3 повторюємо вказану послідовність дій від початку.
42, 55, 12, 44, 67, 18, 06; 94 v (42,44,06) = 42
i=0 j=6
06, 55, 12, 44, 67, 18, 42; 94
i=1 j=5
06, 18, 12; 44, 67, 55, 42; 94
j=2 i=3 i>=j p = j = 2
06, 18, 12; 44, 67, 55, 42; 94 v (06,18,12) = 12
i=1 j=2
06, 12, 18; 44, 67, 55, 42; 94
06, 12; 18; 44, 67, 55, 42; 94 v (44,55,42) = 44
i=3 j=6
06, 12; 18; 42; 67, 55, 44; 94
j=3 i=4 i>=j p = j = 3
06, 12; 18; 42; 67, 55, 44; 94 v (67,55,44) = 55
i=4 j=6
06, 12; 18; 42; 44, 55; 67; 94
Інший приклад (дещо скорочено, можна спробувати самому і порівняти результати):
Впорядкувати за зростанням масив: 6, 2, 4, 7, 1, 3, 8, 5
6, 2, 4, 7, 1, 3, 8, 5 v = 5
6, 2, 4, 7, 1, 3, 8, 5 i=0, j=7
5, 2, 4, 7, 1, 3, 8, 6 i=3, j=5
5, 2, 4, 3, 1; 7, 8, 6 i=5, j=4; i>=j - поділ
5, 2, 4, 3, 1 v = 4
5, 2, 4, 3, 1 i=0, j=4
1, 2, 4, 3, 5 i=2, j=3
1, 2, 3; 4, 5 i=3, j=2; i>=j - поділ
1, 2, 3 v = 2
1, 2; 3 i=2, j=2; i>=j - поділ
; 7, 8, 6 v = 7
; 7, 8, 6 i=5, j=7
; 6; 8, 7 i=6; j=5; i>=j - поділ
; 6; 7, 8 вибором
1, 2, 3, 4, 5, 6, 7, 8
(Як зміняться ці приклади при впорядковуванні за спаданням ?)
Програмна реалізація швидкого сортування.
Рекурсивна функція quick_sort упорядковує швидким сортуванням ділянку масиву цілих чисел довжиною n, перший елемент якої визначається вказівником a.
/* quick_sort - швидке сортування елементів *a, *(a+1), …, *(a+n-1) */
void quick_sort (int *a, int n)
{
if (n<3)
{
selection_sort(a,n);
return;
}
int p = partition (a, n);
int ln = p + 1;
int rn = n - ln;
quick_sort (a, ln);
quick_sort (a+ln, rn);
}
int median3 (int x, int y, int z)
{
return x<y ? (y<z ? y : (x<z ? z : x)) : (z<y ? y : (z<x ? z : x));
}
int partition (int *a, int n)
{
int v = median3(a[0], a[n/2], a[n-1]);
int i=-1;
int j=n;
int temp;
while (1)
{
do { ++i; } while (a[i]<v);
do { --j; } while (a[j]>v);
if (i<j)
{ temp=a[i];
a[i]=a[j];
a[j]=temp;
}
else return j;
}
}
Якщо ділянка масиву містить більше двох елементів (n>=3), то використовуються два індекса i та j, які проходять частини масиву назустріч один одному у функції partition. Тоді p позначить елемент у точці поділу; ліворуч від p стоять числа не більші a[p], a праворуч від p - числа, більші a[p].
Час впорядковування швидким сортуванням дуже залежить від початкового вигляду масиву. Час буде мінімальним, якщо кожний крок поділу дає списки приблизно рівної довжини; тоді необхідно EMBED Equation.3 кроків. Якщо початковий список мало відрізняється від звичайного упорядкованого, то необхідно EMBED Equation.3 кроків. Швидке сортування вимагає додаткової пам’яті порядку EMBED Equation.3 для виконання рекурсивної функції quick_sort.
Сортування злиттям (Джон фон Нейман, 1945).
Злиття списків. Упорядковані списки A і B довжини m і n зливаються в один упорядкований список C довжини m + n, якщо кожний елемент з A та B входить в C тільки один раз. Так, злиття списків A = <12, 42, 44, 55> і B = <06, 18, 67, 94> дає список
C = <06, 12, 18, 42, 44, 55, 67, 94>.
Злиття списків A = <2, 4, 6, 7> і B = <1, 3, 5, 8> дає список
C = <1, 2, 3, 4, 5, 6, 7, 8>.
Для злиття списків A і B список C спочатку має бути порожнім, а потім до нього послідовно додається менший з перших вузлів A і B, який ще відсутній в C.
Програмна реалізація злиття списків
Скласти функцію для злиття двох упорядкованих і розміщених поряд частин масиву A: A[p], A[p+1], …, A[q]; і A[q+1], A[q+2], …, A[r].
Параметрами функції є масив A, індекс першого елемента першої частини p, індекс останнього елемента першої частини q, індекс останнього елемента другої частини r. Функція merge здійснює злиття цих підмасивів, утворюючи впорядкований масив A[p], A[p+1], …, A[r].
void merge(int *A, int p, int q, int r)
{
int *L,*R;
int i,j,k,n1,n2;
n1=q-p+1; // довжина першої частини
n2=r-q; // довжина другої частини
L=(int *)calloc(n1+1,sizeof(int)); // допоміжний масив
// для першої частини
R=(int *)calloc(n2+1,sizeof(int)); // допоміжний масив
// для другої частини
for(i=0;i<n1;i++)
L[i]=A[p+i]; // переписуємо першу частину
for(j=0;j<n2;j++)
R[j]=A[q+j+1]; // переписуємо другу частину
L[n1]=MAXINT; // зверніть
R[n2]=MAXINT; // увагу !
i=0;
j=0;
for (k=p; k<=r; k++)
if (L[i]<=R[j]) // порівнюємо елементи
// на початку списків L і R
{
A[k]=L[i]; i++; // беремо елемент з першої частини
}
else
{
A[k]=R[j]; j++; // беремо елемент з другої частини
}
free(R);
free(L);
}
Для побудови упорядкованого списку L' зі списку L = <l1, l2, …, ln>:
список L ділиться на m підсписків L1 = <l1>, L2 = <l2>, … , Lm = <lm> довжиною 1;
утворені EMBED Equation.3 упорядкованих списків L1, L2, …, Lm замінюються на m/2 (або (m+1)/2) упорядкованих списків, що утворюються злиттям сусідніх списків L1 і L2, L3 і L4, ..., і дописуванням Lm (якщо число m – непарне);
повторюємо п. 2 до появи однієї впорядкованої послідовності довжиною n.
Приклад. Виконуємо сортування злиттям заданого списку, відокремлюючи послідовності вертикальною рискою, елементи всередині послідовності – комою:
42 | 55 | 12 | 44 | 94 | 18 | 06 | 67 m =8
L1 | L2 | L3 | L4 | L5 | L6 | L7 | L8
42, 55 | 12, 44 | 18, 94 | 06, 67 m =4
L1 | L2 | L3 | L4
12, 42, 44, 55 | 06, 18, 67, 94 m =2
L1 | L2
06, 12, 18, 42, 44, 55; 67, 94 m =1;
L1
6 | 2 | 4 | 7 | 1 | 3 | 8 | 5
L1 | L2 | L3 | L4 | L5 | L6 | L7 | L8
2, 6 | 4, 7 | 1, 3 | 5, 8
L1 | L2 | L3 | L4
2, 4, 6, 7 | 1, 3, 5, 8
L1 | L2
1, 2, 3, 4, 5, 6, 7, 8
L1
Кількість дій, необхідних для сортування злиттям, дорівнює O (n log2 n), бо за одне проходження виконується n порівнянь, а всього потрібно здійснити log2 n проходжень. Сортування злиттям досить ефективне і застосовується при великих значеннях n.
Програмна реалізація сортування злиттям
Напишемо рекурсивну функцію merge_sort для сортування масиву A[]. За кожним викликом масив для сортування ділиться на дві частини - від A[p] до A[q] та від A[q+1] до A[r], кожна з яких сортується окремо, а потім виконується іхнє злиття.
/* merge_sort - рекурсивне сортування злиттям */
void merge_sort (int *A, int p, int r)
{
int q;
if (p<r)
{
q=(p+r)/2; // поділ списку на частини
merge_sort(A,p,q); // сортування списку у лівій частині
merge_sort(A,q+1,r); // сортування списку у правій частині
merge(A,p,q,r); //злиття сусідніх впорядкованих списків
}
}
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора