Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Структуры и алгоритмы обработки данных

АЛГОРИТМЫ ОБРАБОТКИ СТРУКТУР ДАННЫХ

МЕТОДЫ СОРТИРОВКИ

Упорядочение элементов множества в возрастающем или убывающем порядке называется сортировкой. С упорядоченными элементами проще работать, чем с произвольно расположенными: легче найти необходимые элементы, исключить,вставить новые. Сортировка применяется при трансляции программ, при организации наборов данных на внешних носителях, при создании библиотек, каталогов, баз данных и т.д.

Алгоритмы сортировки можно разбить на несколько групп (рис. 5.1).

Алгоритмы сортировки

Рис. 5.1. Алгоритмы сортировки

Обычно сортируемые элементы множества называют записями и обозначают через кх, к2,..., кп.

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

Сортировка выбором состоит в том, что сначала в неупорядоченном списке наименьший или наибольший элемент выбирается и отделяется от остальных. После этого исходный список оказывается измененным. Этот список принимается за исходный, и процесс продолжается до тех пор, пока все элементы не будут выбраны. Очевидно, что выбранные элементы образуют упорядоченный список.

Например, требуется найти минимальный элемент списка

Процесс выбора показан на рис. 5.2, где в каждой строчке выписаны сравниваемые пары.

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

Рис. 5.2. Сортировка выбором

Нетрудно видеть, что число сравнений соответствует числу строк, а число перемещений — числу изменений выбранного элемента. Выбранный в исходном списке минимальный элемент размещается на предназначенном ему месте несколькими способами:

  • 1) минимальный элемент после /-го просмотра перемещается на /-е место нового списка (/ = 1,2,..., п), а в исходном списке на место выбранного элемента записывается какое-то очень большое число, превосходящее по величине любой элемент списка, при этом длина заданного списка остается постоянной. Измененный таким образом список можно принять за исходный;
  • 2) минимальный элемент записывается на /-е место исходного списка (/ = 1, 2,п), а элемент с /-го места — на место выбранного. При этом очевидно, что уже упорядоченные элементы (а они будут расположены, начиная с первого места) исключаются из дальнейшей сортировки, поэтому длина каждого последующего списка (списка, участвующего в каждом последующем просмотре) должна быть на один элемент меньше предыдущего;
  • 3) выбранный минимальный элемент, как и в предыдущем случае, перемещается на /-е место заданного списка, а чтобы это /-е место освободилось для записи очередного минимального элемента, левая от выбранного элемента часть списка перемещается вправо на одну позицию так, чтобы заполнилось место, занимаемое до этого выбранным элементом.

На последующих этапах элементы стека образуют исходное множество.

Сложность метода сортировки выбором — 0(п2).

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >
 

Популярные страницы