Сортировка – упорядочение данных определенным образом. Необходимость отсортировать какие-либо величины возникает в программировании очень часто. К примеру, входные данные подаются "вперемешку", а нашей программе удобнее обрабатывать упорядоченную последовательность. Существуют ситуации, когда предварительная сортировка данных позволяет сократить содержательную часть алгоритма в разы, а время его работы - в десятки раз. Методы сортировки делятся на три типа:
- методы сортировки, которые сортируют без использования дополнительной памяти, за исключением, возможно, небольшого стека и/или массива;
- методы, которые используют для сортировки связанные списки и поэтому используют N дополнительных указателей хранящихся в памяти;
- и методы, которые нуждаются в дополнительной памяти для хранения копии сортируемого файла.
Сортировка данных используется для эффективного решения других задач при программировании. Для упорядоченной совокупности данных быстро и легко решается задача, как поиск и отбор информации по заданному условию. Существует много алгоритмов, обеспечивающих решение задачи сортировки. Одни из них обладают низким быстродействием, другие обладают очень высокой эффективностью и практически используются в современных компьютерных системах (рисунок 1). При анализе всякой сортировки определяется число операций сравнения и обмена, выполняемых в лучшем, среднем и худшем случаях. При сортировке пузырьковым методом всегда выполняется 1/ 2 (n2-n) операций сравнения, где "n" задает число сортируемых элементов массива. Эта формула выводится на том основании, что внешний цикл сортировки пузырьковым методом выполняется n-1 раз, а внутренний цикл выполняется n/2 раз. Их перемножение даст указанную формулу. Число операций обмена будет нулевым для наилучшего случая, когда исходный массив уже является отсортированным. Число операций обмена для среднего случая будет равно 3/4 (n2-n), а для наихудшего случая будет равно 3/2 (n2-n) раз. Сортировку пузырьковым методом называют квадратичным алгоритмом, поскольку время его выполнения пропорционально квадрату числа сортируемых элементов. Сортировка большого числа элементов пузырьковым методом потребует очень много времени, т.к. время выполнения сортировки находится в квадратичной зависимости от числа элементов массива. Сортировку пузырьковым методом можно в некоторой степени улучшить и тем самым немного улучшить ее временные характеристики. Можно, например, заметить, что сортировка пузырьковым методом обладает одной особенностью: расположенный не на своем месте в конце массива элемент (например, элемент "а" в массиве "dcab") достигает своего места за один проход, а элемент, расположенный в начале массива (например, элемент "d"), очень медленно достигает своего места. Необязательно все просмотры делать в одном направлении. Вместо этого всякий последующий просмотр можно делать в противоположном направлении. В этом случае сильно удаленные от своего места элементы будут быстро перемещаться в соответствующее место.