Сортировка массивов

Часто удобно иметь данные (особенно когда их много), расположенные в определенном порядке, например, в порядке возрастания или убывания. Такое упорядочение в программировании называется сортировкой.

Сортировка – это процесс упорядочения информации по определенному признаку. Сортировать можно любые данные – важно только, чтобы их можно было тем или иным образом сравнивать. Сортировать можно, например, значения скалярных типов, символы, строки. При решении задачи сортировки обычно выдвигается требование минимального использования дополнительной памяти, из которого вытекает недопустимость применения дополнительных массивов.

Для оценки быстродействия алгоритмов различных методов сортировки, как правило, используют два показателя:

§ количество присваиваний;

§ количество сравнений.

Все методы сортировки можно разделить на две большие группы:

§ прямые методы сортировки;

§ улучшенные методы сортировки.

Прямые методы сортировки по принципу, лежащему в основе метода, в свою очередь разделяются на три подгруппы:

1) сортировка вставкой (включением);

2) сортировка выбором (выделением);

3) сортировка обменом («пузырьковая» сортировка).

Улучшенные методы сортировки основываются на тех же принципах, что и прямые, но используют некоторые оригинальные идеи для ускорения процесса сортировки. Прямые методы на практике используются довольно редко, так как имеют относительно низкое быстродействие. Однако они хорошо показывают суть основанных на них улучшенных методов. Кроме того, в некоторых случаях (как правило, при небольшой длине массива и/или особом исходном расположении элементов массива) некоторые из прямых методов могут даже превзойти улучшенные методы.

Улучшенные методы в настоящей разработке рассматриваются на примере быстрой сортировки.