Алгоритм сортування бульбашкою можна трохи покращити, якщо проаналізувати, як він працює у разі вже впорядкованого масиву. Навіть тоді відбудуться всі проходи в кількості штук (- кількість елементів), і в ході кожного з них жодна пара елементів не буде переставлена.
Пухирцева сортування і її покращення Тут потрібно послідовно порівнювати значення сусідніх елементів та змінювати числа місцями, якщо попереднє виявляється більшим за наступне. Таким чином, елементи з більшими значеннями виявляються в кінці списку, а з меншими залишаються на початку.
З майже завжди застосовних алгоритмів quicksort IMHO найшвидший (Час O(N*log N)), хоча (навіть правильно реалізований) зрідка (на практиці дуже рідко) може призвести до часу порядку O(N^2).
Алгоритм складається з трьох кроків:
- Вибрати елемент із масиву. Назвемо його опорним.
- Розбиття: перерозподіл елементів у масиві таким чином, що менші опорні елементи поміщаються перед ним, а великі або рівні – після.
- Рекурсивно застосувати перші два кроки до двох підмасивів зліва та праворуч від опорного елемента.