Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Топ:
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов...
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного...
Генеалогическое древо Султанов Османской империи: Османские правители, вначале, будучи еще бейлербеями Анатолии, женились на дочерях византийских императоров...
Интересное:
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Аура как энергетическое поле: многослойную ауру человека можно представить себе подобным...
Дисциплины:
2021-04-18 | 101 |
5.00
из
|
Заказать работу |
|
|
Очередь с приоритетами также часто реализуют с помощью пирамиды. При этом извлечение элемента с максимальным приоритетом из очереди осуществляется аналогично тому, как это делалось во 2-й фазе алгоритма пирамидальной сортировки.
Вставка элемента в очередь происходит похожим образом – помещаем элемент в конец пирамиды (увеличив её размер на единицу) и обеспечиваем выполнение основного свойства пирамиды для этого элемента. Основное отличие состоит в том, что при этом мы сравнивать элемент с его родителем (а не сыном) и при необходимости поднимать, а не опускать. Пример вставки элемента показан на рис.4.9.
Иногда требуется, чтобы элементы с одинаковым приоритетом выходили из очереди в том же порядке, в каком они и пришли. Для этого можно использовать разные способы, например, расширить приоритеты элементов очереди до двух частей – собственно приоритета и некоего порядкового номера, который будет увеличиваться на единицу для каждого нового элемента, помещаемого в очередь.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
9 | 7 | 5 | 6 | 2 | 4 | 1 | 3 |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 7 | 5 | 6 | 2 | 4 | 1 | 3 | 8 |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 7 | 5 | 8 | 2 | 4 | 1 | 3 | 6 |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 8 | 5 | 7 | 2 | 4 | 1 | 3 | 6 |
Рис 4.9. Вставка элемента в очередь с приоритетами на базе пирамиды
Сортировка слиянием
Прежде чем описывать данный способ сортировки, посмотрим, как можно эффективно слить две уже отсортированных последовательности в одну общую, также отсортированную. Для этого можно поступить следующим образом. Сравним первые элементы двух последовательностей, меньший из них извлечём и поместим на выход. Так будем продолжать до тех пор, пока одна из последовательностей не опустеет. После этого остаётся только добавить остаток второй последовательности в конец результирующей.
|
Например, пусть заданы последовательности <2,5,8> и <3, 4>. Сначала сравним элементы 2 и 3, меньший из них 2 – он станет первым элементом результата, а у нас остаётся <5,8> и <3,4>. Теперь 3 меньше чем 5, 3 уходит в результат, у нас остаётся <5,8> и <4>. На следующем шаге 4 уходит, и вторая последовательность становится пустой. Для завершения слияния остаток первой последовательности уходит в результат. Более наглядно этот процесс показан на рисунке.
В случае, когда последовательности заданы в массивах, для текущего первого элемента последовательности можно просто использовать отдельную переменную – индекс. приведём пример реализации (a и b – исходные массивы, n и m – их длины, r – массив, куда помещается результат):
void merge(int a[], int n, int b[], int m, int r[])
{ int i=0, j=0, k=0;
while (i<n && j<m)
r[k++] = (a[i]<=b[j])? a[i++]: b[j++];
//добавим остаток первого массива
for(; i<n; i++)
r[k++] = a[i];
//добавим остаток второго массива
for(; j<m; j++)
r[k++] = b[j];
}
Теперь перейдём к алгоритму сортировки слиянием. Рекурсивная реализация данного алгоритма очень легка и проста для понимания. Чтобы отсортировать массив, мы разбиваем его на две примерно равные части, рекурсивно сортируем каждую из них, после чего сливаем отсортированные части и получаем результирующий отсортированный массив.
Большим недостатком данного алгоритма является необходимость выделения памяти под вспомогательный массив, куда помещаются результаты слияния двух половинок исходного массива.
Пример реализации:
void _mergeSort(int a[], int n, int r[])
{ бif (n<2) return;
//разбиваем на две части, рекурсивно сортируем левую и правую часть
int p = n/2;
_mergeSort(a,p,r);
_mergeSort(a+p,n-p,r);
//сливаем отсортированные части во вспомогательный массив b
merge(a,p,a+p,n-p,r);
//копируем отсортированные данные из b обратно в a
memcpy(a,r,n * sizeof(int));
}
void mergeSort(int a[], int n)
{
int *r = new int[n];
_mergeSort(a,n,r);
delete [] r;
}
Здесь основная работа выполняется в функции _mergeSort, рекурсивно вызывающей саму себя, тогда как в функции-оболочке mergeSort выделяется и освобождается память под вспомогательный массив.
|
Нерекурсивный вариант данной сортировки будет рассмотрен в главе, посвященной внешней сортировке.
|
|
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!