Встановити практичне застосування одного з алгоритмів сортування.
Створити візуалізацію одного зі способів сортування масивів (демонстрація, презентація, опис та ін.)
Ответы
Сортування елементів - одна з категорій алгоритмів, до яких розробник має звикнути. Якщо колись, коли я навчався, інформатика не сприймалася так серйозно, то зараз уже в школі повинні вміти реалізовувати алгоритми сортування та розуміти їх. Базові алгоритми, найпростіші, реалізовані за допомогою циклу for. Звичайно, щоб відсортувати колекцію елементів, наприклад, масив, потрібно по цій колекції якось пройти. Що можна сказати про цю ділянку коду? Ми маємо цикл, у якому змінюємо значення індексу ( int i) з 0 до останнього елемента у масиві. Фактично ми просто беремо кожен елемент у масиві і друкуємо його вміст. Чим більше елементів у масиві, тим довше виконуватиметься код. Тобто, якщо n — кількість елементів, при n=10 програма виконуватиметься довше, ніж за n=5, у 2 рази. Коли в нашій програмі є один цикл, час виконання зростає лінійно: що більше елементів, то довше виконання. Виходить, що алгоритм коду працює за лінійний час (n). У разі говорять, що " складність алгоритму " дорівнює O(n). Це позначення ще називають "велике" або "асимптотичне поведінка". Але можна запам'ятати просто "складність алгоритму". Найпростіше сортування (Bubble Sort)
Отже, ми маємо масив і можемо ним ітеруватися. Чудово. Давайте спробуємо його відсортувати за зростанням. Що це означає для нас? Це означає, що маючи два елементи (наприклад, a=6, b=5), ми повинні переставити місцями a та b, якщо a більше ніж b (якщо a > b). Що для нас це означає при роботі з колекцією за індексом (як у випадку з масивом)? Це означає, якщо елемент з індексом а більше, ніж елемент з індексом b, (array[a] > array[b]), такі елементи треба поміняти місцями. Зміну місць часто називають swap. Існують різні способи зміни місць. Але ми використовуємо простий, зрозумілий код, що легко запам'ятовується. Як бачимо, елементи дійсно помінялися місцями. Ми почали із одного елемента, т.к. якщо масив буде всього з одного елемента, вираз 1 < 1 не поверне true і тим самим ми убезпечимо себе від випадків масиву в один елемент або зовсім без них, а код буде виглядати краще. Але наш підсумковий масив не відсортовано однаково, т.к. за один прохід не вдається відсортувати всіх. Прийде додати ще цикл, в якому ми будемо виконувати проходи один за одним до тих пір, поки не отримаємо відсортований масив. Ось наше перше сортування і відпрацювало. Ми ітеруємося у зовнішньому циклі (while) До тих пір, поки не вирішимо, що ітерацій більше не потрібно. За умовчанням перед кожною новою ітерацією ми припускаємо, що наш масив відсортований, і більше не хочемо ітеруватися. Тому ми проходимо елементи послідовно і перевіряємо це припущення. Але якщо елементи не по порядку, ми виконуємо swap елементів та розуміємо, що немає впевненості, що тепер елементи у правильному порядку. Отже хочемо виконати ще одну ітерацію. Наприклад, [3, 5, 2]. 5 більше трьох, все гаразд. Але 2 менше 5. Проте [3, 2, 5] потребує ще одного проходу, т.к. 3 > 2 та його треба поміняти місцями. Оскільки ми використовуємо цикл у циклі, виходить, що складність нашого алгоритму збільшується. За n елементів вона стає n * n, тобто O(n^2). Така складність називається квадратичною. Як ми розуміємо, ми можемо точно знати, скільки знадобиться ітерацій. Показник складності алгоритму має на меті показати тенденцію зростання складності, найгірший випадок. Наскільки сильно збільшуватиметься час роботи при зміні кількості елементів n. Сортування бульбашкою - одне з найпростіших і неефективних сортувань. Її ще іноді називають "дурним сортуванням". Матеріал на тему