Главная » Java, Структуры данных и алгоритмы » Сортировка методом выбора и сортировка методом ввода

0

Обратимся к схеме PriorityQueueSort, приведенной в п. 7.1.2. В этой схеме несортированная последовательность S, имеющая п элементов, сортируется с помощью очереди Рв две стадии. На первой стадии осуществляется ввод элементов друг за другом, а на второй — элементы последовательно удаляются с помощью операции removeMin. В этом разделе рассматриваются два варианта такого алгоритма сортировки.

Сортировка методом выбора

Если очередь с приоритетами Рреализуется с помбщью несортированной последовательности, то первая стадия будет занимать О(п) времени, а каждый ввод элемента потребует постоянного времени. На второй стадии, исходя из постоянных затрат времени на сравнение двух ключей, время выполнения каждой операции removeMin будет пропорционально количеству элементов очереди Р. Следовательно, самым узким местом этой реализации будет повторяющийся «выбор» минимального элемента из несортированной последовательности на второй стадии. Поэтому такой алгоритм больше известен как сортировка методом выбора (см. рис. 7.1).

Рис. 7.7. Иллюстрация процесса выполнения сортировки методом выбора в S=(7, 4, 8, 2, 5, 3, 9). Алгоритм обеспечивает двухфазную схему PriorityQueueSort и использует очередь с приоритетами, реализованную с помощью несортированной последовательности. На первой стадии последовательно удаляется из S и вставляется в конец очереди Р первый элемент. Обратите внимание, что в конце первой стадии Р представляет собой копию первоначальной S. На второй стадии последовательно выполняется операция removeMin над Р(то есть для нахождения нужного элемента сканируется вся последовательность, реализующая Р), а затем возвращаемый элемент добавляется в конец S

Теперь проанализируем алгоритм сортировки методом выбора. Как отмечалось, узкое место в нем — вторая стадия, где из очереди удаляются элементы с наименьшим ключом. Первоначальный размер Р составляет п элементов и 1три выполнении операции removeMin последовательно уменьшается на.один элемент до тех пор, пока не достигнет нуля. Таким образом, первая операция removeMin занимает О(п) времени, следующая — 0(п – 1) и так далее, до тех пор пока время выполнения последней операции не составит 0(1), Следовательно, общее время, необходимое для выполнения второй стадии, составит

Рис. 7.2. Схематическое визуальное представление процесса выполнения сортировки методом ввода в S= (7, 4, 8, 2, 5, 3, 9). Алгоритм соответствует двушаговой схеме PriorityQueueSort и использует очередь с приоритетами, реализованную с помощью сортированной последовательности. На первой фазе последовательно удаляется из( 5 и вводится в Р первый элемент, сканируя для поиска нужной позиции элемента последовательность, реализуемую очередью. На второй стадии последовательно выполняется операция removeMin над Р, в результате которой возвращается первый элемент последовательности, реализуемой Р, добавляемый затем в конец S

Другими словами, время выполнения схемы PriorityQueueSort, реализованной с помощью сортированной последовательности, составит 0{п2). Следовательно, и тот и другой вариант сортировки имеют одинаковое время выполнения. Это означает, что в обоих случаях наихудший вариант выполнения будет аналогичен времени пузырьковой сортировки (см. раздел 5.4), которая составляет 0(п2).

Хотя алгоритмы сортировки методом выбора и методом ввода подобны, они все же имеют любопытные отличия. Например, сортировка методом выбора для поиска наименьшего ключа на второй стадии постоянно сканирует всю последовательность, на что уходит 0(п2) времени. Время выполнения сортировки методом ввода, с другой стороны, зависит от последовательности вводимых элементов. Например, если исходная последовательность S выстроена в обратном порядке (по возрастанию), то сортировка ввода занимает 0(п) времени, поскольку каждый следующий элемент вводится на первой стадии в конец приоритетной очереди.

Можно проводить сортировку методом ввода таким образом, чтобы вводить элементы, начиная с конца последовательности очереди с приоритетами на первой стадии, в результате чего сортировка уже отсортированной последовательности займет О(п) времени. В самом деле, время выполнения сортировки методом ввода в этом случае составит 0(п + /),

где / — количество инверсий последовательности, то есть количество пар элементов, образующих последовательность исходных элементрв в обратном порядке. Количество инверсий в небольшой последовательности невелико. Однако наихудшее время выполнения 0(п2) делает сортировку методом ввода очень медленной при работе с последовательностями, имеющими значительное количество элементов.

Два вида реализации схемы PriorityQueueSort, приведенные в этом разделе, предлагают возможное решение для уменьшения времени сортировки очереди с приоритетами. Однако при этом первый алгоритм (сортировка методом выбора), очень быстро выполняя первую стадию процесса, медленно работает во второй. Соответственно второй алгоритм (сортировка методом ввода), хотя и медленно выполняется на первом этапе, на втором работает очень быстро. Если сбалансировать время выполнения на каждой стадии, значительно ускорится общее время выполнения сортировки. Именно этого можно достичь, воспользовавшись реализацией, описанной в следующем разделе.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии