Структуры и алгоритмы обработки данных
Краткая теория
Пузырьковая сортировка
Идея : (N-1) раз массив проходится снизу вверх (сверху вниз), при этом элементы попарно сравниваются, если нижний элемент меньше верхнего, то элементы переставляются.
Пример : массив - 4, 3, 7, 2, 1, 6.
Можно улучшить "пузырьковый" метод, если проходить массив элементов и вверх и вниз одновременно.
Количество сравнений :
Количество перемещений :
Пример вычисления "пузырьковым" методом
На примере представлен массив из пяти элементов, это означает, что массив проходится снизу вверх (сверху вниз) 5-1=4 раза. Так же на примере видно, что алгоритм "в пустую" обрабатывает массив начиная уже с третьего шага внутреннего цикла, а 4-й шаг можно уже не выполнять.
Преимущества данного метода :
1) Самый простой алгоритм
2) Простой в реализации
3) Не нужно дополнительных переменных
Недостатки:
1) Долго обрабатывает большие массивы
2) В любом случае количество проходов не уменьшается
Quiksort - метод быстрой сортировки
Идея : В основе данного метода положен метод разделение ключей по отношению к выбранному.
Пример :
После первого прохода выбранный элемент становится на свое место.
Улучшение "пузырькового" метода.
1) Если проходить массив не только сверху вниз, но и снизу вверх одновременно, то не только "легкие" элементы будут "всплывать", но и "тяжелые" "тонуть".
2) Для отмены прохода массива "впустую" нужно в во внешний цикл вставить проверку на отсортированность массива.
