Методы сортировки данных.

В общем виде задача сортировки данных может быть сформулирована следующим образом.

Пусть задан массив a, состоящий из N элементов некоторого типа T, называемого базовым типом этого массива:

T a[N];

Пусть также задана некоторая функция f от двух элементов этого же типа:

int compare(T a, T b);

Эта функция называется функцией сравнения двух элементов типа T, т.е. функцией, которая определяет, какой из этих элементов считать большим, а какой – меньшим. Функция сравнения однозначно определяет операцию сравнения. Соотношение элементов a и b связано с результатом функции f следующим образом:

compare(a, b)<0  a<b

compare(a, b)=0  a=b

compare(a, b)>0  a>b

Массив a называется отсортированным в соответствии с функцией compare (или отсортированным по критерию compare), если выполняется следующее правило:

 i, j  [0, N-1] : i < j  a[i] < a[j]

Иными словами, в отсортированном массиве любой последующий элемент больше любого предыдущего элемента.

Как видно из данного определения, о сортировке массива имеет смысл говорить только тогда, когда на его базовом типе определена операция сравнения. Именно эту операцию и реализует функция compare. Задавая разные функции сравнения, можно по-разному определять операцию сравнения элементов массива и, тем самым, получать различное упорядочение его элементов.

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

a < b & b < c  a < c

a < b  b > a

Операция сравнения может быть определена для самых разнообразных типов данных. Более того, для каждого типа данных она может быть определена различными способами. Например, массив целых чисел можно сортировать в порядке их возрастания, в этом случае функцию сравнения следует задать следующим образом:

int f(int a, int b)

{

return a – b;

}

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

Метод сортировки массива – это некоторый алгоритм. Исходными данными для этого алгоритма является массив, об упорядочении элементов которого в общем случае ничего не известно, т.е. предполагается, что этот массив не отсортирован. Также на вход алгоритма сортировки подается функция сортировки. Задачей алгоритма сортировки является такое переупорядочение элементов массива, чтобы этот массив стал отсортированным в соответствии с заданной функцией сравнения. Этот отсортированный массив и является результатом работы алгоритма сортировки.