Модели и структуры данных



         

Сортировки слиянием. - часть 2


индекс 1-го множества пары } while i0 < N do begin { цикл пока не пересмотрим весь массив } j0:=i0+si; { нач. индекс 2-го множества пары } i:=i0; j:=j0; { размер 2-го множества пары может ограничиваться концом массива } if si > N-j0+1 then sj:=N-j0+1 else sj:=si; if sj > 0 then begin k:=i0; { нач. индекс слитого множества } while (i < i0+si+sj) and (j a[j] then begin { если эл-т 1-го a[j] } k:=k+1; { вых. множество увеличилось } i:=i+1; { если был перенос - за счет сдвига, если не было - за счет перехода эл-та в вых. } end; { while } end; { if sj > 0 } i0:=i0+si*2; { начало следующей пары } end; { while i0 < N } si:=si*2; { размер эл-тов пары увеличивается вдвое } end; { while si < N } end;

Результаты трассировки примера приведены в таблице 3.11. Для каждого прохода показаны множества, которые на этом проходе сливаются. Обратите внимание на обработку последнего множества, оставшегося без пары.

Таблица 3.11

КаталогИндекс раздела

НазадОглавлениеВперед




Содержание  Назад  Вперед