Теги: Сортування бульбашкою сі, сі бульбашкова сортування, сортування бульбашкою двовимірного масиву
Сортування бульбашкою
І дея алгоритму дуже проста. Йдемо по масиву чисел і перевіряємо порядок (наступне число повинно бути більше і дорівнює попередньому), як тільки натрапили на порушення порядку, тут же обмінюємо місцями елементи, доходимо до кінця масиву, після чого починаємо спочатку.
Відсортуємо масив (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
По-друге, можна спочатку перемістити масив в одновимірний, впорядкувати одновимірний масив, після чого перемістити його назад в двовимірний.
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); } }
Якщо вас бентежить ця функція, то скористайтеся типизированной. Виклик, з попереднього прикладу
Розташуємо масив зверху вниз, від нульового елемента - до останнього.
Ідея методу: крок сортування полягає в проході знизу вгору по масиву. По дорозі проглядаються пари сусідніх елементів. Якщо елементи деякої пари знаходяться в неправильному порядку, то міняємо їх місцями.
Після нульового проходу по масиву "вгорі" виявляється самий "легкий" елемент - звідси аналогія з бульбашкою. Наступний прохід робиться до другого зверху елемента, таким чином другий за величиною елемент піднімається на правильну позицію ...
Робимо проходи по все зменшується нижній частині масиву до тих пір, поки в ній не залишиться тільки один елемент. На цьому сортування закінчується, так як послідовність впорядкована за зростанням.
Template
Середнє число порівнянь і обмінів мають квадратичний порядок зростання: Theta (n 2), звідси можна зробити висновок, що алгоритм бульбашки дуже повільний і малоефективний.
Проте, у нього є величезний плюс: він простий і його можна по-всякому покращувати. Чим ми зараз і займемося.
По-перше, розглянемо ситуацію, коли на якому-небудь з проходів не відбулося жодного обміну. Що це означає?
Це означає, що всі пари розташовані в правильному порядку, так що масив вже відсортований. І продовжувати процес не має сенсу (особливо, якщо масив був відсортований з самого початку!).
Отже, перше поліпшення алгоритму полягає в запам'ятовуванні, чи проводився на даному проході будь-якої обмін. Якщо немає - алгоритм закінчує роботу.
Процес поліпшення можна продовжити, якщо запам'ятовувати не тільки сам факт обміну, але і індекс останнього обміну k. Дійсно: всі пари сусідів елементів з індексами, меншими k, вже розташовані в потрібному порядку. Подальші проходи можна закінчувати на індексі k, замість того щоб рухатися до встановленої заздалегідь верхньої межі i.
Якісно інше поліпшення алгоритму можна отримати з наступного спостереження. Хоча легкий бульбашка знизу підніметься наверх за один прохід, важкі бульбашки опускаються зі мінімальною швидкістю: один крок за ітерацію. Так що масив 2 3 4 5 6 1 буде відсортований за 1 прохід, а сортування послідовності 6 1 2 3 4 5 зажадає 5 проходів.
Щоб уникнути подібного ефекту, можна змінювати напрямок наступних один за іншим проходів. Одержаний алгоритм іноді називають " шейкер-сортуванням".
Template
Наскільки описані зміни вплинули на ефективність методу? Середня кількість порівнянь, хоч і зменшилася, але залишається O (n 2), в той час як число обмінів залишається такою взагалі ніяк. Середнє (воно ж гірше) кількість операцій залишається квадратичним.
Додаткова пам'ять, очевидно, не потрібно. Поведінка вдосконаленого (але не початкового) методу досить природне, майже відсортований масив буде відсортований набагато швидше випадкового. Сортування бульбашкою стійка, однак шейкер-сортування втрачає цю якість.
На практиці метод бульбашки, навіть з поліпшеннями, працює, на жаль, занадто повільно. А тому - майже не застосовується.
Всі чудово знають, що з класу обмінних угруповань найшвидший метод - це так звана швидке сортування. Про неї пишуть дисертації, її присвячено чимало статей на Хабре, на її основі придумують складні гібридні алгоритми. Але сьогодні мова піде не про quick sort, А про інший обмінний спосіб - стару добру бульбашкову сортування і її поліпшення, модифікації, мутації і різновиди.
Практичний вихлоп від даних методів не дуже який і багато хабрапользователі все це проходили ще в першому класі. Тому стаття адресована тим, хто тільки-тільки зацікавився теорією алгоритмів і робить в цьому напрямку перші кроки.
image: бульбашки
Сьогодні поговоримо про найпростіші сортуваннях обмінами.
Якщо кому цікаво, скажу, що є й інші класи - сортування вибором, сортування вставками, сортування злиттям, сортування розподілом, гібридні сортування і паралельні сортування. Є, до речі, ще езотеричні сортування. Це різні фейковий, принципово не реалізовуються, жартівливі та інші псевдо-алгоритми, про які я в хабі «IT-гумор» як-небудь напишу пару статей.
Але до сьогоднішньої лекції це не має відношення, нас зараз цікавлять тільки простенькі сортування обмінами. Самих угруповань обмінами теж чимало (я знаю більше дюжини), тому ми розглянемо так звану бульбашкову сортування і деякі інші, з нею тісно взаємопов'язані.
Заздалегідь попереджу, що майже всі наведені способи вельми повільні і глибокого аналізу їх тимчасової складності не буде. Якісь швидше, якісь повільніше, але, грубо кажучи, можна сказати, що в середньому O(n 2). Також я не бачу резону захаращувати статтю реалізаціями на будь-яких мовах програмування. Зацікавлені без найменшого праці зможуть знайти приклади коду на Розетті, в Вікіпедії або де-небудь ще.
Але повернемося до сортувань обмінами. Упорядкування відбувається в результаті багаторазового послідовного перебору масиву і порівняння пар елементів між собою. Якщо порівнювані елементи не відсортовані один щодо одного - то міняємо їх місцями. Питання тільки в тому, яким саме чином масив обходити і за яким принципом обирати пари для порівняння.
Почнемо ні з еталонною бульбашкового сортування, а з алгоритму, який називається ...
дурна сортування
Сортування і справді дивна. Переглядаємо масив зліва-направо і по шляху порівнюємо сусідів. Якщо ми зустрінемо пару взаємно невідсортованих елементів, то міняємо їх місцями і повертаємося на круги своя, чи то пак в самий початок. Знову проходимо-перевіряємо масив, якщо зустріли знову «неправильну» пару сусідніх елементів, то міняємо місцями і знову починаємо все заново. Продовжуємо до тих пір поки масив потихеньку-легенько НЕ відсортують.«Так будь-який дурень сортувати вміє» - скажете Ви і будете абсолютно праві. Саме тому сортування і прозвали «дурною». На цій лекції ми будемо послідовно вдосконалювати і видозмінювати даний спосіб. Зараз у нього тимчасова складність O(n 3), Зробивши одну корекцію, ми вже доведемо до O(n 2), Потім прискоримо ще трохи, потім ще, а в кінці кінців ми отримаємо O(n log n) - і це буде зовсім не «Швидке сортування»!
Внесемо в дурну сортування одне-єдине поліпшення. Виявивши при проході два сусідніх невідсортованих елемента і помінявши їх місцями, не станемо відкочуватися в початок масиву, а незворушно продовжимо його обхід до самого кінця.
У цьому випадку перед нами не що інше як усім відома ...
бульбашкова сортування
або сортування простими обмінами. Безсмертна класика жанру. Принцип дій простий: обходимо масив від початку до кінця, попутно змінюючи місцями невідсортовані сусідні елементи. В результаті першого проходу на останнє місце «спливе» максимальний елемент. Тепер знову обходимо невідсортовану частина масиву (від першого елемента до передостаннього) і міняємо по шляху невідсортованих сусідів. Другий за величиною елемент виявиться на передостанньому місці. Продовжуючи в тому ж дусі, будемо обходити все зменшується невідсортовану частина масиву, запихаючи знайдені максимуми в кінець.Якщо не тільки в кінець засовувати максимуми, а ще й в початок перекидати мінімуми то у нас виходить ...
шейкерні сортування
вона ж сортування перемішуванням, Вона ж коктейльна сортування. Починається процес як в «бульбашці»: видавлюємо максимум на самі задвірки. Після цього повертаємося на 180 0 і йдемо в протилежний бік, при цьому вже перекочуючи в початок не максимум, а мінімум. Відсортувавши в масиві перший і останній елементи, знову робимо кульбіт. Обійшовши туди-назад кілька разів, в результаті закінчуємо процес, опинившись в середині списку.Шейкерні сортування працює трохи швидше ніж бульбашкова, оскільки по масиву в потрібних напрямках поперемінно мігрують і максимуми і мінімуми. Покращення, як говориться, у наявності.
Як бачите, якщо до процесу перебору підійти творчо, то виштовхування важких (легких) елементів до кінців масиву відбувається швидше. Тому умільці запропонували для обходу списку ще одну нестандартну «дорожню карту».
Парно-непарна сортування
Цього разу ми не будемо снувати по масиву взад-вперед, а знову повернемося до ідеї планомірного обходу зліва-направо, але тільки зробимо ширше крок. На першому проході елементи з непарним ключем порівнюємо з сусідами, що базується на парних місцях (1-й порівнюємо з 2-м, потім 3-й з 4-м, 5-й з 6-м і так далі). Потім навпаки - «парні за рахунком» елементи порівнюємо / міняємо з «непарними». Потім знову «нечёт-чет», потім знову «чет-непарне». Процес зупиняється тоді, коли після поспіль двох проходів по масиву ( «непарній-парному» і «парно-непарному») не відбулося жодного обміну. Стало бути, відсортували.У звичайному «бульбашці» під час кожного проходу ми планомірно видавлюємо в кінець масиву поточний максимум. Якщо ж пересуватися підстрибом по парних і непарних індексам, то відразу все більш-менш великі елементи масиву одночасно за один пробіг проштовхуються вправо на одну позицію. Так виходить швидше.
розберемо останнім покращення* для сортуваннях Бульбашка** - сортуваннях гребінцем***. Цей спосіб впорядковує вельми спритно, O(n 2) - його найгірша складність. В середньому за часом маємо O(n log n), А найкраща навіть, не повірите, O(n). Тобто, досить гідний конкурент всяким «швидким сортувань» і це, зауважте, без використання рекурсії. Втім, я обіцяв, що в крейсерські швидкості ми сьогодні заглиблюватися не будемо, Засим замовкаю і переходжу безпосередньо до алгоритму.
У всьому винні черепашки
Невелика передісторія. У 1980 році Влодзімеж Добосіевіч пояснив чому бульбашкова і похідні від неї сортування працюють так повільно. Це все через черепашок. «Черепахи» - невеликі за значенням елементи, які знаходяться в кінці списку. Як Ви, можливо, помітили бульбашкові сортування орієнтовані на «кроликів» (не плутати з «кроликами» Бабушкіна) - великих за значенням елементів на початку списку. Вони досить жваво переміщаються до фінішу. А ось повільні плазуни на старт повзуть неохоче. Підганяти «Тортила» можна за допомогою гребінця.image: винувата черепашка
Сортування гребінцем
У «бульбашці», «шейкері» і «чет-непарне» при переборі масиву порівнюються сусідні елементи. Основна ідея «гребінця» в тому, щоб спочатку брати досить велику відстань між порівнюваними елементами і в міру упорядкування масиву звужувати це відстань аж до мінімального. Таким чином ми як би зачісуватися масив, поступово розгладжуючи на все більш акуратні пасма.Початковий розрив між порівнюваними елементами краще брати не аби який, а з урахуванням спеціальної величини званої фактором зменшення, Оптимальне значення якої дорівнює приблизно 1,247. Спочатку відстань між елементами дорівнює розміру масиву розділеного на фактор зменшення (Результат, природно, округляється до найближчого цілого). Потім, пройшовши масив з цим кроком, ми знову ділимо крок на фактор зменшення і проходимо за списком знову. Так триває до тих пір, поки різниця індексів не досягне одиниці. В цьому випадку масив досортіровивается звичайним бульбашкою.
Досвідченим і теоретичним шляхом встановлено оптимальне значення фактора зменшення:
Коли був винайдений цей метод, на нього на стику 70-х і 80-х мало хто звернув увагу. Десятиліття потому, коли програмування перестало бути долею вчених і інженерів IBM, а вже лавиноподібно набирало масового характеру, спосіб перевідкрити, досліджували і популяризували в 1991 році Стівен Лейсі і Річард Бокс.
Ось власне і все що я хотів Вам розповісти про бульбашкову сортування і іже з нею.
- Примітки
* Покращення ( укр.) - поліпшення
** сортуваннях Бульбашка ( укр.) - Сортування бульбашкою
*** сортуваннях гребінцем ( укр.) - Сортування гребінцем
Всім привіт!
Сьогодні ми розберемо сортування методом "бульбашки". Даний алгоритм часто проходиться в школах і університетах, тому будемо використовувати мову Pascal. І, так, що таке сортування? Сортування - це впорядкування елементів від меншого до більшого (сортування по зростанню) або від більшого елемента до меншого (сортування за убуванням). Сортують зазвичай масиви.
Існують різні алгоритми сортування. Деякі, добре сортують велику кількість елементів, інші, більш ефективні при дуже невеликій кількості елементів. Наш метод бульбашки характерний:
плюси:
- Простота реалізації алгоритму
- Красива назва
- Один з найбільш повільних методів сортування (Час виконання квадратично залежить від довжини масиву n 2)
- Майже не застосовується в реальному житті (використовується в основному в навчальних цілях)
алгоритм: Беремо елемент масиву, порівнюємо з наступним, якщо наш елемент, повинна перевищувати елемента, то ми їх міняємо місцями. Після проходження всього масиву, ми можемо бути впевнені, що максимальний елемент буде "виштовхнуть" - і стояти найостаннішим. Таким чином, один елемент у нас вже точно стоїть на своєму місці. Оскільки нам треба їх все розташувати на свої місця, отже, ми повинні повторити цю операцію, стільки раз, скільки у нас елементів масиву мінус 1. Останній елемент встане автоматично, якщо інші стоять на своїх місцях.
Повернемося до нашого масиву: 3 1 4 2
Беремо перший елемент "3" порівнюємо з наступним "1". Оскільки "3"\u003e "1", то міняємо місцями:
1 3 4 2
Тепер порівнюємо "3" і "4", трійка не більш четвірки, значить нічого не робимо. Далі, порівнюємо "4" і "2". Чотири більше, ніж два - значить міняємо місцями: 1 3 2 4. Цикл закінчився. Значить найбільший елемент вже повинен стояти на своєму місці !! Бачимо, що у нас так і сталося. Де б "4" (наш найбільший елемент) не перебувала - він все одно, після проходження циклом всього масиву, буде останнім. Аналогія - як бульбашка повітря спливає у воді - так і наш елемент, спливає в масиві. Тому і алгоритм, називається "Бульбашкова сортування". Щоб розташувати наступний елемент, необхідно, почати цикл спочатку, але останній елемент можна вже не розглядати, тому що він стоїть на своєму місці.
Порівнюємо "1" і "3" - нічого не змінюємо.
Порівнюємо "3" і "2" - Три більше двох, значить міняємо місцями. Виходить: 1 2 3 4. Другий цикл закінчили. Ми зробили вже два цикли - значить, з упевненістю можна сказати, що у нас, два останніх елемента вже відсортовані. Залишилося нам впорядкувати третій елемент, а четвертий, встане в потрібне місце, автоматично. Ще раз, порівнюємо перший елемент і другий - бачимо, що у нас вже все на своїх місцях, значить, масив, можна вважати, відсортоване за зростанням елементів.
Тепер залишилося запрограмувати даний алгоритм на мові Pascal. const n \u003d 4; (Заводимо константу, це буде довжина масиву) var i, j, k: integer; (Дві змінні для вкладеного циклу, одна для того щоб елементи міняти місцями) m: array of integer; (Заводимо масив) begin (Будемо запрошувати масив з клавіатури :) Writeln ( "Введіть масив:"); for i: \u003d 1 to n do begin Writeln (i, "елемент:"); Readln (m [i]); end; (Зовнішній цикл відповідає за те, що ми повинні повторити внутрішній цикл стільки раз, скільки у нас елементів масиву мінус 1.) for i: \u003d 1 to n-1 do begin (Внутрішній цикл вже перебирає елементи і порівнює між собою.) For j : \u003d 1 to ni do begin (Якщо елемент, повинна перевищувати, то міняємо місцями.) if m [j]\u003e m then begin k: \u003d m [j]; m [j]: \u003d m; m: \u003d k; end; end; end; (Виводь результат :) for i: \u003d 1 to n do Write (m [i], ""); end.
Ось результат: 
А ось видеоурок
Сортування бульбашкою - найпростіший алгоритм сортування, застосовуваний чисто для навчальних цілей. Практичного застосування цього алгоритму немає, так як він не ефективний, особливо якщо необхідно впорядкувати масив великого розміру. До плюсів сортування бульбашкою відноситься простота реалізації алгоритму.
Алгоритм сортування бульбашкою зводиться до повторення проходів за елементами сортованого масиву. Прохід по елементам масиву виконує внутрішній цикл. За кожен прохід порівнюються два сусідні елементи, і якщо порядок невірний елементи міняються місцями. Зовнішній цикл буде працювати до тих пір, поки маса не буде відсортований. Таким чином зовнішній цикл контролює кількість спрацьовувань внутрішнього циклу Коли при черговому проході за елементами масиву не буде здійснено жодної перестановки, то масив буде вважатися відсортованим. Щоб добре зрозуміти алгоритм, відсортуємо методом бульбашки масив, наприклад, з 7 чисел (див. Таблиця 1).
вихідний масив: 3 3 7 1 2 5 0
| № ітерації | елементи масиву | перестановки | ||||||
|---|---|---|---|---|---|---|---|---|
| вих. масив | 3 | 3 | 7 | 1 | 2 | 5 | 0 | |
| 0 | 3 | 3 | false | |||||
| 1 | 3 | 7 | false | |||||
| 2 | 1 | 7 | 7\u003e 1, true | |||||
| 3 | 2 | 7 | 7\u003e 2, true | |||||
| 4 | 5 | 7 | 7\u003e 5, true | |||||
| 5 | 0 | 7 | 7\u003e 0, true | |||||
| тек. масив | 3 | 3 | 1 | 2 | 5 | 0 | 7 | |
| 0 | 3 | 3 | false | |||||
| 1 | 1 | 3 | 3\u003e 1, true | |||||
| 2 | 2 | 3 | 3\u003e 2, true | |||||
| 3 | 0 | 3 | 3\u003e 0, true | |||||
| 4 | 3 | 5 | false | |||||
| 5 | 5 | 7 | false | |||||
| тек. масив | 3 | 1 | 2 | 0 | 3 | 5 | 7 | |
| 0 | 1 | 3 | 3\u003e 1, true | |||||
| 1 | 2 | 3 | 3\u003e 2, true | |||||
| 2 | 0 | 3 | 3\u003e 0, true | |||||
| 3 | 3 | 3 | false | |||||
| 4 | 3 | 5 | false | |||||
| 5 | 5 | 7 | false | |||||
| тек. масив | 1 | 2 | 0 | 3 | 3 | 5 | 7 | |
| 1 | 2 | false | ||||||
| 0 | 2 | 2\u003e 0, true | ||||||
| 2 | 3 | false | ||||||
| 3 | 3 | false | ||||||
| 3 | 5 | false | ||||||
| 5 | 7 | false | ||||||
| тек. масив | 1 | 0 | 2 | 3 | 3 | 5 | 7 | |
| 0 | 1 | 1\u003e 0, true | ||||||
| 1 | 2 | false | ||||||
| 2 | 3 | false | ||||||
| 3 | 3 | false | ||||||
| 3 | 5 | false | ||||||
| 5 | 7 | false | ||||||
| кінцевий масив | 0 | 1 | 2 | 3 | 3 | 5 | 7 | |
| кінець сортування | ||||||||
Для того щоб впорядкувати масив вистачило п'яти запусків внутрішнього циклу, for. Запустити, цикл for спрацьовував 6 разів, так як елементів в масиві 7, то ітерацій (повторень) циклу for повинно бути на одне менше. На кожній ітерації порівнюються два сусідні елементи масиву. Якщо поточний елемент масиву повинна перевищувати, то міняємо їх місцями. Таким чином, поки маса не буде відсортований, буде запускатися внутрішній цикл і виконуватися операція порівняння. Зверніть увагу на те, що за кожне повне виконання циклу for як мінімум один елемент масиву знаходить своє місце. У гіршому випадку, знадобиться n-2 запуску внутрішнього циклу, де n - кількість елементів масиву. Це говорить про те, що сортування бульбашкою вкрай неефективна для великих масивів.
Розробимо програму, в якій спочатку необхідно ввести розмір одновимірного масиву, після чого масив заповнюється випадковими числами і сортується методом бульбашки.
// bu_sort.cpp: визначає точку входу для консольного застосування. #include "stdafx.h" #include
Результат роботи програми показаний на малюнку 1.
