Первый шаг по организации и систематизации данных – сортировка. Все компьютерные системы содержат реализации алгоритмов сортировки, которые используются юзерами и самими системами.
На заре компьютерных вычислений было распространено мнение, что до 30% вычислительных действий уходило на сортировку. Если в наши дни эта доля и снизилась, то в основном из-за повышения эффективности алгоритмов сортировки, а не из-за уменьшения ее важности.
Возможно, вы будете в своей деятельности пользоваться только системной сортировкой, но изучение алгоритмов сортировки важно по нескольким практическим причинам:
* анализ алгоритмов сортировки представляет собой хорошее введение в сравнение производительности алгоритмов;
* на основе алгоритмов сортировки разрабатываются алгоритмы для решения других задач;
* есть множество алгоритмов сортировки, в которых применяются самые разные методы и приемы разработки. Вы познакомитесь с ними при разработке и анализе алгоритмов сортировки.
В качестве первого знакомства мы рассмотрим два элементарных метода – сортировку выбором и сортировку вставками.