Алгоритми сортування: level easy

Наступні декілька дописів поговоримо про сортування. Конкретно в цьому пропоную зосередитися на найбільш інтуїтивних і легких для розуміння:

1. Selection sort. Алгоритм простий: ми знаходимо найменший елемент в масиві і вставляємо його на поточний в ітерації індекс. Big O: time complexity - O(n2), space complexity - O(1);
Код: https://codepen.io/olenitut/pen/qBeQPxJ?editors=0011


2. Bubble sort. При кожній ітерації порівнюємо два сусідні елементи масиву, якщо вони не сортовані між собою - міняємо їх місцями. Це гарантує, що при першій же ітерації “максимальний” елемент масиву буде в правильному місці (звідси назва - він ніби спливає). Відповідно в наступних ітераціях “сплиті” елементи не треба перевіряти. Також, гарною оптимізацією для бабл сорта є вихід з нього, якщо при попередній ітерації не був змінений жодний елемент. Big O: time complexity - O(n2), space complexity - O(1);
Код: https://codepen.io/olenitut/pen/eYqQGLV?editors=0011

3. Insertion sort. Тут ми тримаємо ліву частину масиву сортованою. При першій ітерації ми вважаємо, що перший елемент масива вже відсортований. І тепер нам треба просто в правильне місце вставити (звідси назва алгоритму - insertion) другий елемент. Як наслідок в нас ліва частина масиву з 2-х елементів є відсортованою, і нам треба вставити на правильне місце третій елемент. І так до кінця масиву. Big O: time complexity - O(n2), space complexity - O(1);
Код: https://codepen.io/olenitut/pen/ZEgmXmv?editors=0011


Візуалізовану версію можна знайти у цій статті: https://medium.com/@nisfari/sorting-algorithm-bubble-sort-selection-sort-insertion-sort-fd6dadea3d1e