Информатика. Курс лекций. Громов Ю.Ю - 91 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

Рис. 4.10. Сортировка списка имен Fred, Alice, David, Bill и Carol
В этом варианте два верхних имени образуют отсортированный подсписок, а три верхних – нет. Подымем третью кар-
точку с именем David, опустим карточку с именем Fred вниз, туда, где только что была карточка с именем David, а затем по-
местим карточку с именем David в ту позицию, которую раньше занимала карточка с именем Fred, как показано во второй
строке на рис. 4.10. Теперь три верхних элемента списка образуют отсортированный подсписок. Продолжая действовать та-
ким способом, мы можем получить список, в котором будут отсортированы четыре верхних элемента. Для этого нужно под-
нять четвертую карточку с именем Bill, опустить вниз карточки с именами Fred и David, а затем поместим карточку с именем
Bill в освободившуюся позицию (третья строка на рис. 4.10). И наконец, чтобы завершить процесс сортировки, необходимо
поднять карточку с именем Carol, опустить вниз карточки с именами Fred и David, а затем поместить карточку с именем
Carol в освободившуюся позицию – как показано в четвертой строке на рис. 4.10.
Теперь наша задача состоит в том, чтобы проанализировать процесс сортировки конкретного списка и попытаться
обобщить его в целях получения алгоритма сортировки любого списка. С этой точки зрения каждая строка на рис. 4.10 пред-
ставляет собой один и тот же повторяющийся процесс: "Поднять карточку с именем, первую в неотсортированной части
списка, сдвинуть вниз карточки с именами, которые находятся ниже по алфавиту, чем имя на взятой нами карточке, а затем
поместить эту взятую карточку на освободившееся место в списке". Если назвать выбранное имя опорным элементом, то с
помощью нашего псевдокода данный процесс можно описать следующим образом:
Переместить ОпорныйЭлемент во временное хранилище, оставив в списке пустое место;
while (над пустым местом есть имя, и оно > ОпорныйЭлемент) do
{переместить имя, находящееся над пустым местом, вниз,
оставив в его прежней позиции пустое место}
Поместить ОпорныйЭлемент на пустое место в списке
Обратите внимание, что этот процесс должен выполняться многократно. Чтобы начать процедуру сортировки, в качест-
ве опорного элемента должен быть выбран второй элемент списка. Затем, перед каждым последующим выполнением опи-
санной процедуры, должен выбираться новый опорный элемент, находящийся на одну позицию ниже предыдущего, и так до
тех пор, пока не будет достигнут конец списка, т.е. положение опорного элемента должно перемещаться от второго элемента
к третьему, затем к четвертому и т.д. Следуя этому, мы можем организовать требуемое управление путем повторения проце-
дуры с помощью следующей последовательности инструкций:
N ← 2;
while (N ≤ ДлинаСписка) do
{выбрать N-й элемент как ОпорныйЭлемент;
.
.
.
N ← N + 1}

Страницы