Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Сортировка — это упорядочивание набора однотипных данных по возрастанию или убыванию. Сортировка является одной из наиболее приятных для умственного анализа категорией алгоритмов, поскольку процесс сортировки очень хорошо определен. Алгоритмы сортировки были подвергнуты обширному анализу, и способ их работы хорошо понятен. К сожалению, вследствие этой изученности сортировка часто воспринимается как нечто само собой разумеющееся. При необходимости отсортировать данные многие программисты просто вызывают стандартную функцию qsort(), входящую в стандартную библиотеку С. Однако различные подходы к сортировке обладают разными характеристиками. Несмотря на то, что некоторые способы сортировки могут быть в среднем лучше, чем другие, ни один алгоритм не является идеальным для всех случаев. Поэтому широкий набор алгоритмов сортировки — полезное добавление в инструментарий любого программиста.
Будет полезно кратко остановиться на том, почему вызов qsort() не является универсальным решением всех задач сортировки. Во-первых, функцию общего назначения вроде qsort() невозможно применить во всех ситуациях. Например, qsort() сортирует только массивы в памяти. Она не может сортировать данные, хранящиеся в связанных списках. Во-вторых, qsort() - параметризованная функция, благодаря чему она может обрабатывать широкий набор типов данных, но вместе с тем вследствие этого она работает медленнее, чем эквивалентная функция, рассчитанная на какой-то один тип данных. Наконец, как вы увидите, хотя алгоритм быстрой сортировки, примененный в функцииqsort(), очень эффективен в общем случае, он может оказаться не самым лучшим алгоритмом в некоторых конкретных ситуациях.
Существует две общие категории алгоритмов сортировки: алгоритмы, сортирующие объекты с произвольным доступом (например, массивы или дисковые файлы произвольного доступа), и алгоритмы, сортирующие последовательные объекты (например, файлы на дисках и лентах или связанные списки[1]). В данной главе рассматриваются только алгоритмы первой категории, поскольку они наиболее полезны для среднестатистического программиста.
Чаще всего при сортировке данных лишь часть их используется в качестве ключа сортировки. Ключ — это часть информации, определяющая порядок элементов. Таким образом, ключ участвует в сравнениях, но при обмене элементов происходит перемещение всей структуры данных. Например, в списке почтовой рассылки в качестве ключа может использоваться почтовый индекс, но сортируется весь адрес. Для простоты в нижеследующих примерах будет производиться сортировка массивов символов, в которых ключ и данные совпадают. Далее вы увидите, как адаптировать эти методы для сортировки структур данных любого типа.
Самый известный (и пользующийся дурной славой) алгоритм — пузырьковая сортировка (bubble sort, сортировка методом пузырька, или просто сортировка пузырьком)[1]. Его популярность объясняется интересным названием и простотой самого алгоритма. Тем не менее, в общем случае это один из самых худших алгоритмов сортировки.
Пузырьковая сортировка относится к классу обменных сортировок, т.е. к классу сортировок методом обмена. Ее алгоритм содержит повторяющиеся сравнения (т.е. многократные сравнения одних и тех же элементов) и, при необходимости, обмен соседних элементов. Элементы ведут себя подобно пузырькам воздуха в воде — каждый из них поднимается на свой уровень. Простая форма алгоритма сортировки показана ниже:
/* Пузырьковая сортировка. */
void bubble(char *items, int count)
{
register int a, b;
register char t;
for(a=1; a < count; ++a)
for(b=count-1; b >= a; --b) {
if(items[b-1] > items[b]) {
/* exchange elements */
t = items[b-1];
items[b-1] = items[b];
items[b] = t;
}
}
}
Здесь items — указатель на массив символов, подлежащий сортировке, a count — количество элементов в массиве. Работа пузырьковой сортировки выполняется в двух циклах. Если количество элементов массива равно count, внешний цикл приводит к просмотру массиваcount - 1 раз. Это обеспечивает размещение элементов в правильном порядке к концу выполнения функции даже в самом худшем случае. Все сравнения и обмены выполняются во внутреннем цикле. (Слегка улучшенная версия алгоритма пузырьковой сортировки завершает работу, если при просмотре массива не было сделано ни одного обмена, но это достигается за счет добавления еще одного сравнения при каждом проходе внутреннего цикла.)
С помощью этой версии алгоритма пузырьковой сортировки можно сортировать массивы символов по возрастанию. Например, следующая короткая программа сортирует строку, вводимую пользователем:
/* Программа, вызывающая функцию сортировки bubble */
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
void bubble(char *items, int count);
int main(void)
{
char s[255];
printf("Введите строку:");
gets(s);
bubble(s, strlen(s));
printf("Отсортированная строка: %s.\n", s);
return 0;
}
Чтобы наглядно показать, как работает пузырьковая сортировка, допустим, что исходный массив содержит элементы dcab. Ниже показано состояние массива после каждого прохода:
Начало d c a b
Проход 1 a d c b
Проход 2 a b d c
Проход 3 a b c d
При анализе любого алгоритма сортировки полезно знать, сколько операций сравнения и обмена будет выполнено в лучшем, среднем и худшем случаях. Поскольку характеристики выполняемого кода зависят от таких факторов, как оптимизация, производимая компилятором, различия между процессорами и особенности реализации, мы не будем пытаться получить точные значения этих параметров. Вместо этого сконцентрируем свое внимание на общей эффективности каждого алгоритма.
В пузырьковой сортировке количество сравнений всегда одно и то же, поскольку два цикла for повторяются указанное количество раз независимо от того, был список изначально упорядочен или нет. Это значит, что алгоритм пузырьковой сортировки всегда выполняет
(n2-n)/2
сравнений, где n — количество сортируемых элементов. Данная формула выведена на том основании, что внешний цикл выполняется n - 1 раз, а внутренний выполняется в среднем n/2 раз. Произведение этих величин и дает предыдущее выражение.
Обратите внимание на член n2 в формуле. Говорят, что пузырьковая сортировка является алгоритмом порядка n2, поскольку время ее выполнения пропорционально квадрату количества сортируемых элементов. Необходимо признать, что алгоритм порядка n2 не эффективен при большом количестве элементов, поскольку время выполнения растет экспоненциально в зависимости от количества сортируемых элементов. На рис. 21.1 показан график роста времени сортировки с увеличением размера массива.
В алгоритме пузырьковой сортировки количество обменов в лучшем случае равно нулю, если массив уже отсортирован. Однако в среднем и худшем случаях количество обменов также является величиной порядка n2.
|
Рис. 21.1. Время сортировки порядка n2 в зависимости от размера массива. (На самом деле здесь нарисована кривая у=n2/1000, а не кривая у=n2, крутизна которой в 1000 раз выше. Фактически это все равно, что нарисовать кривую у=n2, выбрав по оси ординат более мелкий масштаб (в 1000 раз). Начертить кривую у=n2 без растяжения вдоль оси абсцисс, на которой откладываются значения n, практически невозможно. Дело в том, что при выбранном интервале изменения n (от 0 до 1000) кривая у=n2 практически сливается с осью ординат.) |
Алгоритм пузырьковой сортировки можно немного улучшить, если попытаться повысить скорость его работы. Например, пузырьковая сортировка имеет такую особенность: неупорядоченные элементы на "большом" конце массива (например, "а" в примере dсаb) занимают правильные положения за один проход, но неупорядоченные элементы в начале массива (например, "d") поднимаются на свои места очень медленно. Этот факт подсказывает способ улучшения алгоритма. Вместо того чтобы постоянно просматривать массив в одном направлении, в последовательных проходах можно чередовать направления. Этим мы добьемся того, что элементы, сильно удаленные от своих положений, быстро станут на свои места. Данная версия пузырьковой сортировки носит название шейкер-сортировки (shaker sort)[2], поскольку действия, производимые ею с массивом, напоминают взбалтывание или встряхивание. Ниже показана реализация шейкер-сортировки.
/* Шейкер-сортировка. */
void shaker(char *items, int count)
{
register int a;
int exchange;
char t;
do {
exchange = 0;
for(a=count-1; a > 0; --a) {
if(items[a-1] > items[a]) {
t = items[a-1];
items[a-1] = items[a];
items[a] = t;
exchange = 1;
}
}
for(a=1; a < count; ++a) {
if(items[a-1] > items[a]) {
t = items[a-1];
items[a-1] = items[a];
items[a] = t;
exchange = 1;
}
}
} while(exchange); /* сортировать до тех пор, пока не будет обменов */
}
Хотя шейкер-сортировка и является улучшенным вариантом по сравнению с пузырьковой сортировкой, она по-прежнему имеет время выполнения порядка n2. Это объясняется тем, что количество сравнений не изменилось, а количество обменов уменьшилось лишь на относительно небольшую константу. Шейкер-сортировка лучше пузырьковой, но есть еще гораздо лучшие алгоритмы сортировки.