Сортировка данных. 
Теоретические основы информатики

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

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

Главными требованиями к алгоритмам сортировки являются экономное использование памяти и быстродействие выполнения. Быстродействие сортировки определяется количеством сравнений и количеством обменов (перестановок элементов), произведенных в процессе работы. Как правило, эффективность алгоритмов сортировки оценивается степенью роста количества операций сравнения.

Относительно небольшие объемы данных могут целиком помещаться в оперативной памяти. При этом имеется произвольный доступ к сортируемым элементам. В этом случае сортировка называется внутренней. Если объем данных велик и оперативной памяти нс хватает, то информацию размещают на внешних запоминающих устройствах. В этом случае доступ к элементам данных осуществляется последовательно (см. параграф 12.2), а сортировку называют внешней. Такую сортировку применяют и в тех случаях, когда данные изначально хранятся на внешних носителях, например, для файлов баз данных. Очевидно, что внутренняя сортировка для одинаковых данных будет выполняться быстрее, чем внешняя, так как в последнем случае основное время выполнения алгоритма будет затрачено на последовательный доступ к элементам.

Рассмотрим виды сортировок, применяемые к различным данным: числовым, строковым (текстовым), записям в файлах.

Сортировка числовых данных. Пусть даны числа а, «2,…, а_п (представленные, например, в виде массива). В зависимости от того, имеются ли среди них равные элементы, сортировка может быть выполнена:

• — по возрастанию (неубыванию) — каждый следующий элемент больше (нс меньше) предыдущего: а_х < а₂ < … < а_п (или ах < а₂ ^ … ^ а_п);
• — по убыванию (невозрастанию) — каждый следующий элемент меньше (не больше) предыдущего: а > а₂ > … > а" (или ах ^ а₂ ^ … ^ а_п).

Сортировка, текстовых данных обычно заключается в расположении текстовых фрагментов в алфавитном порядке. Ее суть заключается в следующем. Первоначально выполняется сортировка по первому символу текста. Затем каждое подмножество фрагментов, имеющих одинаковые первые символы, сортируется по второму символу и т. д. При этом, если сравниваются две строки длиной п и т (гп > гс), у которых первые п символов совпадают, то считается, что первая строка меньше второй, например, «abc» < «abed».

Порядок символов при алфавитной сортировке может выбираться различными способами: он может задаваться вручную или соответствовать порядку AS СП-кодов символов. В последнем случае для текстовых строк, начинающихся с цифр, можно получить не совсем ожидаемые результаты сортировки, например, «5» < «23». Для устранения подобных ситуаций применяют специальные алгоритмы.

Сортировка записей в файлах выполняется по ключу записи. Он может быть числовым, текстовым или состоять из полей с различными типами данных. Записи перемещаются по возрастанию (убыванию) ключа. В случае составного ключа сначала выполняется последовательная сортировка по отдельным полям ключа.

Рассмотрим основные алгоритмы сортировки данных. Для определенности будем считать, что требуется выполнить сортировку по возрастанию для множества чисел А = {ах, «2,…, On}, г — номер позиции элемента а*.