Функция qsortl быстро сортирует массив случайных чисел, но что, если на вход будет подана уже упорядоченная последовательность? Как мы видели в разделе 2Л главы 2, программисты часто используют сортировку для того, чтобы одинаковые элементы оказались рядом. Следовательно, нужно рассмотреть крайний случай: массив из п одинаковых элементов. Сортировка вставкой работает на таких данных очень быстро: каждый элемент сдвигается на 0 позиций, поэтому время выполнения растет как 0(п). Функция qsortl справляется с такими данными очень плохо. Каждое из п-1 разбиений требует время О(п) для выделения одного эле
мента, поэтому полное время выполнения растет как 0(п2). Время обработки для n = 1 ООО ООО возрастает с одной секунды до двух часов.
Можно обойти эту проблему, используя двусторонний алгоритм разбиения с приведенным на рис. 11.7 инвариантом.
Рис. 11.7. Инвариант двустороннего разбиения
Индексы i и j инициализируются граничными индексами разбиваемого массива. Главный цикл содержит два вложенных цикла. Первый вложенный цикл сдвигает i вверх, пропуская меньшие элементы, а второй увеличивает j, пропуская большие элементы и останавливаясь иа меньшем. Главный цикл проверяет, не пересекаются ли эти индексы, и переставляет соответствующие элементы.
Но как такой код будет работать в ситуации, когда все элементы равны? Первая мысль: пропустить эти элементы, чтобы не делать лишней работы, по в результате получается квадратичный для массива из одинаковых элементов алгоритм. Поэтому каждое сканирование будет останавливаться на одинаковых элементах, которые затем будут обмениваться. Хотя в этом варианте обменов будет производиться больше, чем требуется, такая программа будет превращать худший случай с массивом из одинаковых элементов в лучший, требующий почти в точности п log2 п сравнений. Программа, реализующая описанный алгоритм разбиения, приведена в листинге 11.5.
Листинг 11.5. Быстрая сортировка (версия 3)
void qsоrt3(1. u) if 1>= u return
t - x[1]. i=l: j - u+1 1 oop
do i++ while i <= u && x[i] < t do j- - whi1e x[j] > t if i > J break swapd , j) swap(1, j) qsort3(1. j-1) qsort3(j+l. u)
Избавляясь от квадратичного поведения в худшем случае, этот код и в среднем делает меньше обменов, чем qsortl.
Рассмотренные нами программы быстрой сортировки разбивали массив относительно первого встреченного элемента. Это хорошо подходит для случайных входных данных, но может сильно замедлить работу для некоторых упорядоченных последовательностей. Если массив уже отсортирован по возрастанию, его придется разбивать относительно первого элемента, затем относительно второго и так далее, что потребует времени 0(п2). Мы можем избежать этого, выбирая элемент для разбиения случайным образом — обменивая местами элемент х[1] со случайным элементом из диапазона х[1. .и]:
swap( 1 , ranch nt (1 . и))
Опубликовал vovan666
April 17 2013 00:02:40 ·
0 Комментариев ·
3322 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
