Метод бульбашки c послідовний висновок. Бульбашкова сортування і все-все-все. Вдосконалений алгоритм сортування бульбашкою в Pascal

Розташуємо масив зверху вниз, від нульового елемента - до останнього.

Ідея методу: крок сортування полягає в проході знизу вгору по масиву. По дорозі проглядаються пари сусідніх елементів. Якщо елементи деякої пари знаходяться в неправильному порядку, то міняємо їх місцями.

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

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

Template void bubbleSort (T a, long size) (long i, j; T x; for (i \u003d 0; i< size; i++) { // i - номер проходу for (j \u003d size-1; j\u003e i; j--) ( // внутрішній цикл проходу if (a\u003e a [j]) (x \u003d a; a \u003d a [j]; a [j] \u003d x;))))

Середнє число порівнянь і обмінів мають квадратичний порядок зростання: Theta (n 2), звідси можна зробити висновок, що алгоритм бульбашки дуже повільний і малоефективний.
Проте, у нього є величезний плюс: він простий і його можна по-всякому покращувати. Чим ми зараз і займемося.

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

Це означає, що всі пари розташовані в правильному порядку, так що масив вже відсортований. І продовжувати процес не має сенсу (особливо, якщо масив був відсортований з самого початку!).

Отже, перше поліпшення алгоритму полягає в запам'ятовуванні, чи проводився на даному проході будь-якої обмін. Якщо немає - алгоритм закінчує роботу.

Процес поліпшення можна продовжити, якщо запам'ятовувати не тільки сам факт обміну, але і індекс останнього обміну k. Дійсно: всі пари сусідів елементів з індексами, меншими k, вже розташовані в потрібному порядку. Подальші проходи можна закінчувати на індексі k, замість того щоб рухатися до встановленої заздалегідь верхньої межі i.

Якісно інше поліпшення алгоритму можна отримати з наступного спостереження. Хоча легкий бульбашка знизу підніметься наверх за один прохід, важкі бульбашки опускаються зі мінімальною швидкістю: один крок за ітерацію. Так що масив 2 3 4 5 6 1 буде відсортований за 1 прохід, а сортування послідовності 6 1 2 3 4 5 зажадає 5 проходів.

Щоб уникнути подібного ефекту, можна змінювати напрямок наступних один за іншим проходів. Одержаний алгоритм іноді називають " шейкер-сортуванням".

Template void shakerSort (T a, long size) (long j, k \u003d size-1; long lb \u003d 1, ub \u003d size-1; // кордону невідсортоване частини масиву T x; do ( // прохід від низу до верху for (j \u003d ub; j\u003e 0; j--) (if (a\u003e a [j]) (x \u003d a; a \u003d a [j]; a [j] \u003d x; k \u003d j;)) lb \u003d k + 1; // прохід зверху вниз for (j \u003d 1; j<=ub; j++) { if (a > a [j]) (x \u003d a; a \u003d a [j]; a [j] \u003d x; k \u003d j;)) ub \u003d k-1; ) While (lb< ub); }

Наскільки описані зміни вплинули на ефективність методу? Середня кількість порівнянь, хоч і зменшилася, але залишається O (n 2), в той час як число обмінів залишається такою взагалі ніяк. Середнє (воно ж гірше) кількість операцій залишається квадратичним.

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

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

метод бульбашки

Сортування простими обмінами , сортування бульбашкою (Англ. bubble sort) - простий алгоритм сортування. Для розуміння і реалізації цей алгоритм - найпростіший, але ефективний він лише для невеликих масивів. Складність алгоритму: O ( n²).

Алгоритм вважається навчальним і практично не застосовується поза навчальної літератури, замість нього на практиці застосовується сортування вставками.

алгоритм

Приклад сортування бульбашкою списку випадкових чисел.

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

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

приклади реалізації

Python

Def swap (arr, i, j): arr [i], arr [j] \u003d arr [j], arr [i] def bubble_sort (arr): i \u003d len (arr) while i\u003e 1: for j in xrange (i - 1): if arr [j]\u003e arr [j + 1]: swap (arr, j, j + 1) i - \u003d 1

VBA

Sub Sort (Mus () As Long) Dim n As Long, i As Long, tmp As Long i \u003d 1 Do While (i< UBound (Mus) ) If Mus(i) > Mus (i + 1) Then tmp \u003d Mus (i) Mus (i) \u003d Mus (i + 1) Mus (i + 1) \u003d tmp If i\u003e 1 Then i \u003d i - 1 Else i \u003d i + 1 End If Else i \u003d i + 1 End If Loop End Sub

Вдосконалений алгоритм сортування бульбашкою в Pascal

P: \u003d True; (Перестановка є) K: \u003d 1; (Номер перегляду) While P Do Begin P: \u003d false; For i: \u003d 1 To n-k Do If X [i]\u003e X [i + 1] Then Begin A: \u003d X [i]; X [i]: \u003d X [i + 1]; X [i + 1]: \u003d A; P: \u003d true; End; k: \u003d k + 1; End;

PHP

$ Size \u003d count ($ arr) -1; for ($ i \u003d $ size; $ i\u003e \u003d 0; $ i -) (for ($ j \u003d 0; $ j<=($i -1 ) ; $j ++) if ($arr [ $j ] >$ Arr [$ j +1]) ($ k \u003d $ arr [$ j]; $ arr [$ j] \u003d $ arr [$ j +1]; $ arr [$ j +1] \u003d $ k;))

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

Звідки взялося таке незвичайне назва?

Назва методу придумали, використовуючи аналогію з повітряними бульбашками в воді. Це метафора. Подібно до того, як маленькі бульбашки повітря піднімаються нагору - адже їх щільність більше, ніж будь-якої рідини (в даному випадку - води), так і кожен елемент масиву, чим менше він за значенням, тим більше він поступово пробирається до початку переліку чисел.

опис алгоритму

Сортування бульбашкою виконується наступним чином:

перший прохід: елементи масиву чисел беруться за два і також парами порівнюються. Якщо в якийсь двійці елементів перше значення виявляється більше другого, програма робить їх обмін місцями;
отже, потрапляє в кінець масиву. У той час як всі інші елементи залишаються, як і були, в хаотичному порядку і вимагають ще сортування;
тому й потрібен другий прохід: проводиться він за аналогією з попереднім (вже описаним) і має число порівнянь - мінус один;
біля проходу номер три порівнянь на одиницю менше, ніж у другого, і на двійку, ніж у першого. І так далі;
підсумуємо, що кожен прохід має (всього значень в масиві, конкретне число) мінус (номер проходу) порівнянь.

Ще коротше алгоритм майбутньої програми можна записати так:

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

Псевдокод на основі описаного алгоритму

Найпростіша реалізація виконується так:

процедура Sortirovka_Puzirkom;

початок

цикл для j від nachalnii_index до konechii_index;

цикл для i від nachalnii_index до konechii_index-1;

якщо massiv [i]\u003e massiv

(Міняємо значення місцями);

кінець

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

Потрібна була реалізація краще. Наприклад, враховує обмін значень в масиві місцями:

процедура Sortirovka_Puzirkom;

початок

sortirovka \u003d Істина;

цикл поки sortirovka \u003d Істина;

sortirovka \u003d Брехня;

цикл для i від nachalnii_index до konechii_index-1;

якщо massiv [i]\u003e massiv (Перший елемент більше другого), то:

(Міняємо елементи місцями);

sortirovka \u003d Істина; (Позначили, що обмін був проведений).

Кінець.

недоліки методу

Основний мінус - тривалість процесу. Скільки ж часу виконується бульбашкою?

Час виконання розраховується з квадрата кількості чисел в масиві - кінцевий результат йому пропорційний.

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

Крім того, ефективний метод сортування простими обмінами, як його ще називають, тільки для масивів невеликого розміру. Великі обсяги даних з його допомогою обробити не вийде: результатом стануть або помилки, або збій роботи програми.

переваги

Сортування бульбашкою вельми проста для розуміння. У навчальних програмах технічних ВНЗ при вивченні упорядкування елементів масиву її проходять в першу чергу. Метод легко реалізується як на мові програмування Delphi (Д (Делфі), так і на C / C ++ (Сі / Сі плюс плюс), неймовірно простий алгоритм розташування значень в правильному порядку і на Сортування бульбашкою ідеально підходить для початківців.

Унаслідок недоліків алгоритм не застосовують під позанавчальних цілях.

Наочний принцип сортування

Початковий вид масиву 8 22 4 74 44 37 1 7

Крок 1 8 22 4 74 44 37 1 7

8 22 4 74 44 1 37 7

8 22 4 74 1 44 37 7

8 22 4 1 74 44 37 7

8 22 1 4 74 44 37 7

8 1 22 4 74 44 37 7

1 8 22 4 74 44 37 7

крок 2 1 8 22 4 74 44 7 37

1 8 22 4 74 7 44 37

1 8 22 4 7 74 44 37

1 8 4 22 7 74 44 37

1 4 8 22 7 74 44 37

крок 3 1 4 8 22 7 74 37 44

1 4 8 22 7 37 74 44

1 4 8 7 22 37 74 44

1 4 7 8 22 37 74 44

крок 4 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

крок 5 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

крок 6 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

крок 7 1 4 7 8 22 37 44 74

Приклад сортування бульбашкою на мові Pascal

приклад:

const kol_mas \u003d 10;

var massiv: array of integer;

a, b, k: integer;

writeln ( "input", kol_mas, "elements of array");

for a: \u003d 1 to kol_mas do readln (massiv [a]);

for a: \u003d 1 to kol_mas-1 do begin

for b: \u003d a + 1 to kol_mas do begin

if massiv [a]\u003e massiv [b] then begin

k: \u003d massiv [a]; massiv [a]: \u003d massiv [b]; massiv [b]: \u003d k;

end;

writeln ( "after sort");

for a: \u003d 1 to kol_mas do writeln (massiv [a]);

Приклад сортування бульбашкою на мові С (Сі)

#include

int main (int argc, char * argv)

int massiv \u003d (36, 697, 73, 82, 68, 12, 183, 88), i, ff;

for (;;) (

ff \u003d 0;

for (i \u003d 7; i\u003e 0; i -) (

if (massiv [i]< massiv) {

swap (massiv [i], massiv);

if (ff \u003d\u003d 0) break;

getch (); // затримка екрану

Теги: Сортування бульбашкою сі, сі бульбашкова сортування, Сортування бульбашкою двовимірного масиву

Сортування бульбашкою

І дея алгоритму дуже проста. Йдемо по масиву чисел і перевіряємо порядок (наступне число повинно бути більше і дорівнює попередньому), як тільки натрапили на порушення порядку, тут же обмінюємо місцями елементи, доходимо до кінця масиву, після чого починаємо спочатку.

Відсортуємо масив (1, 5, 2, 7, 6, 3)
Йдемо по масиву, перевіряємо перше число і друге, вони йдуть в порядку зростання. Далі йде порушення порядку, міняємо місцями ці елементи
1, 2, 5, 7, 6, 3
Продовжуємо йти по масиву, 7 більше 5, а ось 6 менше, так що обмінюємо з місцями
1, 2, 5, 6, 7, 3
3 порушує порядок, міняємо місцями з 7
1, 2, 5, 6, 3, 7
Повертаємося до початку масиву і проробляємо те ж саме

1, 2, 5, 3, 6, 7
1, 2, 3, 5, 6, 7

Кажуть, що це схоже на "спливання" більш "легких" елементів, як бульбашок, чому алгоритм і отримав таку назву. void bubbleSort (int * a, size_t size) (size_t i, j; int tmp; for (i \u003d 1; i< size; i++) { for (j = 1; j < size; j++) { if (a[j] > a) (tmp \u003d a [j]; a [j] \u003d a; a \u003d tmp;))))

Цей алгоритм завжди буде робити (n-1) 2 кроків, незалежно від вхідних даних. Навіть якщо масив відсортований, все одно він буде пройдений (n-1) 2 раз. Більш того, будуть в черговий раз перевірені вже відсортовані дані.

Нехай потрібно впорядкувати масив 1, 2, 4, 3

1 2 4 3
1 2 4 3
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4

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

Void bubbleSort2 (int * a, size_t size) (size_t i, j; int tmp; for (i \u003d 1; i< size; i++) { for (j = i; j > 0; j--) (if (a [j]< a) { tmp = a[j]; a[j] = a; a = tmp; } } } }

Ще одна реалізація

Void bubbleSort2b (int * a, size_t size) (size_t i, j; int tmp; for (i \u003d 1; i< size; i++) { for (j = 1; j <= size-i; j++) { if (a[j] < a) { tmp = a[j]; a[j] = a; a = tmp; } } } }

В даному випадку буде вже наполовину менше кроків, але все одно залишається проблема сортування вже відсортованого масиву: потрібно зробити так, щоб відсортований масив функція переглядала один раз. Для цього введемо змінну-прапор: він буде опущений (flag \u003d 0), якщо масив відсортований. Як тільки ми натрапимо на порушення порядку, то прапор буде піднято (flag \u003d 1) і ми почнемо сортувати масив як зазвичай.

Void bubbleSort3 (int * a, size_t size) (size_t i; int tmp; char flag; do (flag \u003d 0; for (i \u003d 1; i< size; i++) { if (a[i] < a) { tmp = a[i]; a[i] = a; a = tmp; flag = 1; } } } while (flag); }

У цьому випадку складність також порядку n 2, але в разі відсортованого масиву буде всього один прохід.

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

Int intSort (const void * a, const void * b) (return * ((int *) a)\u003e * ((int *) b);) void bubbleSort3g (void * a, size_t item, size_t size, int (* cmp) (const void *, const void *)) (size_t i; void * tmp \u003d NULL; char flag; tmp \u003d malloc (item); do (flag \u003d 0; for (i \u003d 1; i< size; i++) { if (cmp(((char*)a + i*item), ((char*)a + (i-1)*item))) { memcpy(tmp, ((char*)a + i*item), item); memcpy(((char*)a + i*item), ((char*)a + (i-1)*item), item); memcpy(((char*)a + (i-1)*item), tmp, item); flag = 1; } } } while (flag); free(tmp); }

Функція виглядає негарно - часто обчислюється адреса поточного і попереднього елемента. Виділимо окремі змінні для цього.

Void bubbleSort3gi (void * a, size_t item, size_t size, int (* cmp) (const void *, const void *)) (size_t i; void * tmp \u003d NULL; void * prev, * cur; char flag; tmp \u003d malloc (item); do (flag \u003d 0; i \u003d 1; prev \u003d (char *) a; cur \u003d (char *) prev + item; while (i< size) { if (cmp(cur, prev)) { memcpy(tmp, prev, item); memcpy(prev, cur, item); memcpy(cur, tmp, item); flag = 1; } i++; prev = (char*)prev + item; cur = (char*)cur + item; } } while (flag); free(tmp); }

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

Void main () (int a \u003d (1, 0, 9, 8, 7, 6, 2, 3, 4, 5); int i; bubbleSort3gi (a, sizeof (int), 10, intSort); for (i \u003d 0; i< 10; i++) { printf("%d ", a[i]); } _getch(); }

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

З ортіровка статичного багатовимірного масиву по суті не відрізняється від сортування одновимірного. Можна скористатися тим властивістю, що статичний одновимірний і багатовимірний масиви мають однакове уявлення в пам'яті.

Void main () (int a \u003d (1, 9, 2, 8, 3, 7, 4, 6, 5); int i, j; bubbleSort3gi (a, sizeof (int), 9, intSort); for (i \u003d 0; i< 3; i++) { for (j = 0; j < 3; j++) { printf("%d ", a[i][j]); } } } Сортировка динамически созданного двумерного массива может быть произведена двумя способами. Во-первых, можно по определённому алгоритму находить индекс i-го и j-го элемента по порядковому номеру k от 0 до n * m. #include #include #include #include void bubbleSort2d (int ** a, size_t m, size_t n) (int tmp; size_t i, j, k, jp, ip; size_t size \u003d m * n; char flag; do (flag \u003d 0; for (k \u003d 1 ; k< size; k++) { //Вычисляем индексы текущего элемента j = k / m; i = k - j*m; //Вычисляем индексы предыдущего элемента jp = (k-1) / m; ip = (k-1) - jp*m; if (a[i][j] > a) (tmp \u003d a [i] [j]; a [i] [j] \u003d a; a \u003d tmp; flag \u003d 1;))) while (flag); ) #Define SIZE_X 3 #define SIZE_Y 4 void main () (int ** a \u003d NULL; int i, j; a \u003d (int **) malloc (sizeof (int *) * SIZE_X); for (i \u003d 0; i< SIZE_X; i++) { a[i] = (int*) malloc(sizeof(int) * SIZE_Y); for (j = 0; j < SIZE_Y; j++) { a[i][j] = rand(); printf("%8d ", a[i][j]); } printf("\n"); } printf("\nafter sort\n"); bubbleSort2d(a, SIZE_X, SIZE_Y); for (i = 0; i < SIZE_X; i++) { for (j = 0; j < SIZE_Y; j++) { printf("%8d ", a[i][j]); } printf("\n"); } for (i = 0; i < SIZE_X; i++) { free(a[i]); } free(a); _getch(); }

По-друге, можна спочатку перемістити масив в одновимірний, впорядкувати одновимірний масив, після чого перемістити його назад в двовимірний.

Void bubbleSort3gi2d (void ** a, size_t item, size_t m, size_t n, int (* cmp) (const void *, const void *)) (size_t size \u003d m * n, sub_size \u003d n * item; size_t i, j , k; void * arr \u003d malloc (size * item); char * p1d \u003d (char *) arr; char * p2d \u003d (char *) a; // копіюємо двовимірний масив типу void в одновимірний for (i \u003d 0; i< m; i++) { memcpy(p1d + i*sub_size, *((void**)(p2d + i*item)), sub_size); } bubbleSort3gi(arr, item, size, cmp); //Копируем одномерный массив обратно в двумерный for (i = 0; i < m; i++) { memcpy(*((void**)(p2d + i*item)), p1d + i*sub_size, sub_size); } }

Якщо вас бентежить ця функція, то скористайтеся типизированной. Виклик, з попереднього прикладу

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

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

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

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

У цій статті наведені приклади реалізації стандартних алгоритмів сортування.

Сортування вибором (Selection sort)

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

Код C ++

void SortAlgo :: selectionSort (int data, int lenD) (int j \u003d 0; int tmp \u003d 0; for (int i \u003d 0; i data [k]) (j \u003d k;)) tmp \u003d data [i]; data [i] \u003d data [j]; data [j] \u003d tmp; ))

Бульбашкова сортування (Bubble sort)

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

Код C ++

void SortAlgo :: bubbleSort (int data, int lenD) (int tmp \u003d 0; for (int i \u003d 0; i \u003d (I + 1); j -) (if (data [j]

Сортування вставками (Insertion sort)

При сортуванні вставками масив розбивається на дві області: впорядковану і та невпорядкованих. Спочатку весь масив є невпорядкованою областю. При першому проході перший елемент з невпорядкованою області вилучається і поміщається в правильному положенні в впорядкованої області.

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

Основний цикл працює в інтервалі від 1 до N-1. На j-й ітерації елемент [i] вставлений в правильне положення в впорядкованої області. Це зроблено шляхом зсуву всіх елементів впорядкованої області, які більше, ніж [i], на одну позицію вправо. [I] вставляється в інтервал між тими елементами, які менше [i], і тими, які більше [i].

Код C ++

void SortAlgo :: insertionSort (int data, int lenD) (int key \u003d 0; int i \u003d 0; for (int j \u003d 1; j \u003d 0 && data [i]\u003e key) (data \u003d data [i]; i \u003d i-1; data \u003d key;)))

Сортування злиттям (Merge sort)

Код C ++

void SortAlgo :: mergeSort (int data, int lenD) (if (lenD\u003e 1) (int middle \u003d lenD / 2; int rem \u003d lenD-middle; int * L \u003d new int; int * R \u003d new int; for ( int i \u003d 0; i

Швидке сортування (Quick sort)

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

Код C ++

void SortAlgo :: quickSort (int * data, int const len) (int const lenD \u003d len; int pivot \u003d 0; int ind \u003d lenD / 2; int i, j \u003d 0, k \u003d 0; if (lenD\u003e 1) (int * L \u003d new int; int * R \u003d new int; pivot \u003d data; for (i \u003d 0; i