Здрастуй, дорогий гість. У цій статті я розповім про алгоритм сортування масиву методом бульбашки.
Елементи масиву, як бульбашки
Алгоритм бульбашкового сортування - це досить простий в реалізації алгоритм для сортування масивів. Можна зустріти й інші назви: бульбашкова сортування. Buble sort або сортування простими обмінами - але всі вони будуть обозночало один і той же алгоритм. Названий так, тому що більше чи менше значення «спливає» (зсувається) до краю масиву після кожної ітерації, це буде видно в прикладі.
Складність цього алгоритму виражається формулою О (n ^ 2) (n в ступені 2). Алгоритм працює повільно з великими масивами, а тому малоефективний і на практиці використовується рідко. найчастіше в навчальних цілях. Для сортування масивів на практиці використовують інші більш швидкі алгоритми, один з них - QuickSort (швидке сортування). Функція для швидкого сортування включена в багато стандартні бібліотеки мов програмування, наприклад в мові C функція qsort () зі стандартної бібліотеки.
Алгоритм працює дуже просто. Програма проходить за всіма елементами масиву по порядку. Кожен поточний елемент порівнюється з сусіднім і, якщо він менше / більше (якщо сортуємо по спадаючій / зростанню відповідно) міняється місцями з сусіднім.
Приклад роботи алгоритму бульбашкового сортування
Розглянемо приклад роботи алгоритму з масивом, що складається з чотирьох елементів.
Є масив [4, 5, 2, 6]. Сортувати його будемо по спадаючій.
N - кількість елементів в масиві. i - номер проходу. Алгоритм буде робити проходи по масиву, всього N-1 проходів до N-i осередки в кожній ітерації для будь-якого масиву.
Перший прохід циклом від першого до N-1 елемента, порівняння умовою і зміна місцями в разі задоволення умови - якщо лівий елемент менше правого.
Порівнюємо 4 і 5, 4 менше 5, а значить ми їх міняємо місцями.
Порівнюємо 4 і 2, 4 не менш 2, а значить пропускаємо і йдемо далі.
Порівнюємо 2 і 6, 4 менше 6, а значить ми їх міняємо місцями.
Тепер ми у нас масив [5, 4, 6, 2]. Як видно, він ще не впорядкований до кінця. Після першого проходу в кінець масиву пересунулася найменше значення, тепер нам потрібно зробити ще прохід до елемента N-2 (адже йде 2-а ітерація).
Робимо прохід, починаючи з першого елемента.
Порівнюємо 5 і 4, 5 не менш 4, а значить пропускаємо і йдемо далі.
Порівнюємо 6 і 4, 6 менше 4, а значить ми їх міняємо місцями. Ми досягли елемента N-2, завершуємо ітерацію.
Тепер ми маємо масив [5, 6, 4, 2]. 2 останніх елемента впорядковані як потрібно. Для завершення потрібно виконати ще один прохід до N-3.
Порівнюємо 5 і 6, 5 менше 6, а значить ми їх міняємо місцями. Ми досягли елемента N-3, завершуємо ітерацію.
У підсумку на виході ми отримали масив упорядкований по спадаючій - [6, 5, 4, 2].
Реалізація алгоритму на мові C ++
Програма виконає послідовно наступні дії:
- Встановить розмір масиву, просячи користувача ввести числове значення.
- Заповнить масив значеннями, введеними користувачем для кожного елемента масиву.
- Виведе вихідний масив.
- Відсортує масив по спадаючій.
- Виведе відсортований масив.
Тепер власне код по кожному з пунктів.
1. Оголосимо змінну і инициализируем її значення даними, введеними користувачем.
Зверніть увагу. що в коді програми використовувалися російські символи, якщо у вас їх відображення некоректно, то почитайте статтю про вирішення проблеми з відображенням російських символів в консолі.
Написання програми завершено, тепер перевіримо результати. А для цього введемо в програму масив, сортування якого ми зробили, розглядаючи приклад роботи алгоритму трохи вище в цій статті.
Після введення даних і виконання програми ми отримали результат.
Результат сортування масиву методом бульбашки
Як видно на зображенні, масив відсортований за спаданням. Програма працює.
Як я зазначав раніше, алгоритм працює дуже повільно з великим об'ємом даних, а тому непридатний для використання на практиці, а придатний лише в навчальних та ознайомлювальних цілях. Подивіться на вирішення інших завдань з програмування.
Для вас це може бути цікаво:
- Знайти максимальний і мінімальний елемент масиву на C ++
- Паліндром. Перевірити, чи є слово, рядок, ...
- Програма для вирішення квадратних рівнянь на C ++
Навігація по публікаціям
Скрізь про неї пишуть, але за швидкодією вона поступається будь-яким іншим. Напишіть про QuickSort, буде корисно 🙂
Так, дійсно, за швидкодією вона поступається багатьом іншим. QuickSort в планах є, в недалекому майбутньому.
А як впорядкувати масив по зростанню?
if (mass [r]
Ееее
а хіба можна оголошувати int mas [n].
де n - це int n.
в C ++ статичний масив оголошується тільки константою.
або так: int mas [10] наприклад
або так:
const int n = 5;
int mas [n];
як у Вас це скомпілілось.
Можна, головне щоб n було присвоєно значення.