Краткая теория

Пузырьковая сортировка

Идея : (N-1) раз массив проходится снизу вверх (сверху вниз), при этом элементы попарно сравниваются, если нижний элемент меньше верхнего, то элементы переставляются.

Пример : массив - 4, 3, 7, 2, 1, 6.

Можно улучшить "пузырьковый" метод, если проходить массив элементов и вверх и вниз одновременно.

Количество сравнений :

Количество перемещений :

Пример вычисления "пузырьковым" методом

На примере представлен массив из пяти элементов, это означает, что массив проходится снизу вверх (сверху вниз) 5-1=4 раза. Так же на примере видно, что алгоритм "в пустую" обрабатывает массив начиная уже с третьего шага внутреннего цикла, а 4-й шаг можно уже не выполнять.

Преимущества данного метода :

1) Самый простой алгоритм

2) Простой в реализации

3) Не нужно дополнительных переменных

  Недостатки:

1) Долго обрабатывает большие массивы

2) В любом случае количество проходов не уменьшается

Quiksort - метод быстрой сортировки

Идея : В основе данного метода положен метод разделение ключей по отношению к выбранному.

Пример :

После первого прохода выбранный элемент становится на свое место.

Улучшение "пузырькового" метода.

1) Если проходить массив не только сверху вниз, но и снизу вверх одновременно, то не только "легкие" элементы  будут "всплывать", но и "тяжелые" "тонуть".

2)   Для отмены прохода массива "впустую" нужно в во внешний цикл вставить проверку на отсортированность массива.