|
Читайте также: |
Квадратичная выборка по сравнению с сортировкой выбором имеет
меньшее число сравнений элементов, однако требует дополнительного
объема памяти.
Сущность метода квадратичной выборки состоит в том, что исходный
массив А из п элементов разделяется на т групп A, A,, A по n
элементов в каждой. Если п не является точным квадратом, то массив разделяетсяна m ¢ групп,где m ¢ естьближайшийквадрат,больший п.
На первой итерации из каждой группы выбирается наименьший элемент,
которыйпересылается во вспомогательный массив В, вмещающий т элементов. В
этом массиве находится наименьший элемент, который присоединяется к
отсортированным элементам в результирующем массиве. Массив В
пополняется наименьшим элементом из той группы, которой принадлежал
элемент, отправленный в результирующий массив. На этом итерация
завершается. Затем снова находится наименьший элемент в массиве В и т.д. В
каждой группе выбранный элемент заменяется большими фиктивными
величинами.
Работа заканчивается, когда все группы будут заполнены фиктивными
величинами.
Пример 6.1.1. Квадратичной выборкой упорядочить массив
А = {8,4,6,3,7,2, 1,5}.
Исходный массив разбивается на три группы элементов:
A = {8, 4, 6}, A = {3, 7, 2}, A = {1, 5}.
Формируем вспомогательный массив, выбирая по наименьшему
элементу из каждой группы
В = {4, 2, 1}.
Находим наименьший элемент 1 из вспомогательного массива и
отправляем его в результирующий массив.
|
Далее изменения вспомогательного массива будут иметь следующийвид
{4, 2, 5}выбран элемент 2
{4,3, 5} выбран элемент 3
{4, 7, 5} выбран элемент 4
{6, 7, 5} выбран элемент 5
{6, 7, f } выбран элемент 6
{8, 7, f } выбран элемент 7
{8, f, f } выбран элемент 8
{ f, f, f } псе элементы фиктивные, конец.
Так как на всех итерациях выбор наименьшего элемента производится
только из одной группы, содержащей n элементов, то одна итерация метода
требует n сравнений. Учитывая, что для выбора элемента во вспомогательном
массиве требуется т сравнений, получаем общее число сравнений на одной
итерации, равное n + m. Всего выполняется п итераций, поэтому для
упорядочения массива квадратичной выборкой необходимо (в худшем случае) выполнить(n + m)× n сравнений.Таккак m = n / n,тополучаем nn + n
сравненийвхудшемслучае.
Дата добавления: 2015-11-16; просмотров: 263 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Cортировка вставками | | | Быстрая сортировка |