Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
1. Управляющие автоматы. Сравнительная характеристика. Принципы функционирования. (Организация ЭВМ и систем)
Основная часть процессора, в которой выполняются основные математические операции состоит из двух автоматов: операционного (ОА) и управляющего (УА).
{x}
Д {y} КОп
Р
{x} – осведомительный сигнал, {y} – управляющий сигнал.
На УА поступает двоичный код выполняемой операции и осведомительные сигналы x из ОА (осведомительные сигналы – это флаги). УА формирует последовательность управляющих сигналов y, воздействующих на контрольные точки ОА. Напр., сложить, сдвинуть, обнулить, инкремент и т.д. Под воздействием этих сигналов y, ОА осуществляет обработку данных D и получает результаты Р.
Элементарные действия называются микрооперацией yi
Набор одновременно выполняемых микроопераций называется микрокомандой.
Последовательность микрокоманд , с помощью которых выполняется команда, называется микропрограммой.
Существует 2 типа УА:
В АПЛ микропрограммы выполнения команд хранятся в микропрограммной памяти. Они являются избыточными, медленнодействующими, но универсальными.
В АЖЛ микропрограмма хранится в схеме (“отображена на схему”). Любые изменения в микропрограмме приводят к необходимости изменения схемы автомата, что является недостатком. Однако они быстродействующие.
Структура АПЛ
t1 t2 t3
где Коп – код операции (берется из регистра команд);
ПНА – преобразователь начального адреса;
БФА – блок формирования адреса;
МПП – микропрограммная память;
ОЧ – операционная часть;
АЧ – адресная часть;
БФУС – блок формирования управляющих сигналов.
Очередная команда программы из программной памяти поступает в регистр команд. Входящий в ее состав код операции поступает на ПНА микропрограммы, выполняющей эту команду. Начальный адрес поступает в БФА (чаще всего это линейный счетчик, осуществляющий последовательную адресацию микрокоманд). Последовательная выборка может быть нарушена сигналами х (флаги, условные вершины, разветвления микропрограммы). В соответствии с сформированным адресом команды выбирается микрокоманда из МПП. Она записывается в регистр микрокоманд. На основании операционной и адресной частей микрокоманды БФУС формирует последовательность управляющих сигналов для этой микрокоманды. Последняя микрокоманда в микропрограмме изменяет состояние счетчика команд на 1, т.е. возвращает нас в основную программу, которая написана в командах, а не в микрокомандах.
Способы кодирования микропрограмм в АПЛ
Существует 3 способа кодирования:
1. Горизонтальный способ кодирования (унитарный, почти не применяется).
МК
Каждому {y}, т. е. каждой МОп отводится свой разряд:
Достоинства: быстро, просто.
Недостатки: громоздко (для ста {y} необходимо 100-разрядное поле).
2. Вертикальный способ кодирования.
Каждая микрокоманда кодируется своим двоичным кодом. y1 < yi < yn
Достоинства: регистр микрокоманд короче (экономия)
Недостатки: задержка в дешифраторе.
Поля между собой кодируются горизонтально. Внутри каждого поля используется вертикальное кодирование.
Способы адресации в АПЛ
Существует 4 способа адресации:
1. Принудительный способ.
Адрес следующей микрокоманды принудительно указывается в предыдущей микрокоманде.
поле условий
МК
0, 1
х
0, 1
А МК – адрес следующей микрокоманды
|
х |
Х |
А |
|
0 |
0 |
А0 |
|
0 |
1 |
А0 |
|
1 |
0 |
А0 |
|
1 |
1 |
А1 |
где х – условие;
Х – необходимость его проверки.
Недостатком этого способа является удлинение адресного поля микрокоманды. Применяется редко.
2. Естественный способ.
Предполагает размещение последовательно выполняемых микрокоманд в последовательно расположенных ячейках МПП. Если нет переходов, то адрес следующей микрокоманды определяется инкрементом предыдущей.
|
х |
Х |
А |
|
0 |
0 |
А+1 |
|
0 |
1 |
А+1 |
|
1 |
0 |
А+1 |
|
1 |
1 |
А0 |
поле условий
МК
0,1
х
0,1
+1
А
Этот метод реализован практически во всех машинах. Его достоинством является то, что, по сравнению с принудительным способом, все микрокоманды стали на адрес короче, однако на быстродействие это не влияет.
3. Функциональный способ.
Последовательно проверяет 2 флага:
0
1
1 0 1 0
А0 А1 А2 А3
Метод подразумевает объединение проверок в одну, т.е. оба флага проверяются в одной микрокоманде. Это является достоинством данного метода. Недостатком – аппаратная сложность, дороговизна.
х1
х2
А
4. Программируемый способ.
В УА аппаратно реализованы все 3 предыдущих метода. Программно выбирается наиболее эффективный.
УА с жесткой логикой
Алгоритм управления “отображен на схему” (запаян). Поэтому любые изменения микропрограммы связаны с переделкой схемы.
Достоинства: более высокое быстродействие.
Недостатки: узкая специализация (применяется только в специализированных ЭВМ).
Структурная схема
где d – сигналы установки триггеров;
x – осведомительные сигналы из ОА;
y – управляющие сигналы в ОА.
Любой автомат с жесткой логикой характеризуется двумя функциями:
Функция переходов определяет состояние автомата в следующем такте.
a(t+1)=f[a(t),x(t)] , где a(t) – предыдущий сигнал
x(t) – осведомительный сигнал.
Функция выходов:
либо , либо
От этого зависит выбор одного из двух автоматов: автомат Мура или автомат Мили.
Синтез автомата с жесткой логикой
|
аисх |
Nисх |
апер |
Nпер |
Y |
x |
d |
|
a1 |
001 |
a3 |
011 |
y0,y3 |
– |
d0,d1 |
каждому ai необходимо присвоить код Ni (разумно брать Ni=i. Число разрядов N зависит от
числа состояний, напр., если число состояний 10, то N=4 (24=16))
состояния и условия. На выходе – сигнал, говорящий о том, какие функции надо
сформировать.
ai
хi y0y3d0d1
Таких схем «И» столько, сколько строк или дуг. Одноименные выходы всех «И»
объединяются по «ИЛИ». На выходах схем «ИЛИ» сформируем семейство {yi}и семейство
{di}.
Примеры.
|
аисх |
Nисх |
апер |
Nпер |
Y |
x |
d |
|
a0 |
000 |
a1 |
001 |
Y1(y1y2y3) |
– |
d0 |
|
a1 |
001 |
a4 a2 |
100 010 |
Y2(y2y3y5) – |
x1 нех1 |
d2 d1 |
|
a2 |
010 |
a5 |
101 |
Y3(y1y6) |
– |
d2 d0 |
|
a3 |
011 |
a0 |
000 |
Y4(y3y5) |
– |
– |
|
a4 |
100 |
a2 |
010 |
Y5(y7) |
– |
d1 |
|
a5 |
101 |
a2 a4 a0 a3 |
010 100 000 011 |
– Y2(y2y3y5) – Y3(y1y6) |
х2 нех1 х2 х1 нех2 нех3 нех2 х3 |
d1 d2 d0 – |
Одновходовые схемы «И» и «ИЛИ» вырождаются в проводник.
2. Определите напряжения Uab, Ubc, Uac схемы, если Е=6 В, R1=10 Ом, R2=R3=40 Ом.
(Электроника и электротехника)
Метод свёртки:
1.) R2,3=(R2*R3)/(R2+R3)
R2,3=1600/80=20 Ом
R1
a I1 b
E
R2,3
I2
c
2.) Rвх=R1+R2,3
Rвх=10+20=30 Ом
I1
E
Rвх
3.) I1=I2=E/Rвх=6/30=2/10=0.2 A
4.) Uac=E=6 B
5.) Ubc=I2*R2,3=0.2*20=4 B
6.) Uab=R1*I1=10*0.2=2 B
3. Технология модульного программирования. Процедуры. (Программирование на языке высокого уровня)
Процедура состоит из заголовка и блока, содержащего, в свою очередь, раздел локальных описаний и раздел операторов процедуры:
Procedure <имя> [(<список формальных параметров>)];
[<раздел описаний>]
Begin
<оператор-1>;
<оператор-2>;
…..
<оператор-N>
End;
Здесь:
Procedure-служебное слово, определяющее заголовок процедуры;
<имя> - имя процедуры (идентификатор);
<список формальных параметров> - перечень имён для обозначения исходных данных и результатов работы процедуры с указанием их типов (имени типа); допускается описание процедуры без параметров;
<раздел описаний> - раздел локальных описаний, используемых в процедуре меток, констант, типов, переменных, процедур и функций;
Begin, End – служебные слова, ограничивающие содержательную часть процедуры (раздел операторов). Заканчивается блок процедуры точкой с запятой.
Пример 1. Оформить в виде процедуры алгоритм вычисления степени y=x^n с натуральным показателем.
Procedure Step1 (n:integer; x:real; Var y:real);
Var
i:integer;
Begin {Step1}
y:=1;
for i:=1 to n do
y:= y*x
End; {Step1};
В заголовке процедуры после её имени Step1 в круглых скобках перечислены формальные параметры n, x, определяющие исходные данные процедуры, и параметр y, обозначающий результат её выполнения (указывается после служебного слова Var). Указантип формальных параметров. Тело процедуры (блок) состоит, во-первых, из описательной части , где объявлена локальная переменная i, имеющая смысл и доступна только внутри данной процедуры; во-вторых, из раздела операторов, реализующих алгоритм вычисления x^n – значение переменной y.
Пример 2. Оформить в виде процедуры без параметров алгоритм вычисления степени y=x^n с натуральным показателем.
Procedure Step2;
Var
i:integer;
Begin {Step2}
y:=1;
for i:=1 to n do
y:= y*x
End; {Step2};
Процедура Step2 не имеет списка формальных параметров и работает с переменными n,x,y, которые должны быть описаны в основной программе, содержащей данную процедуру. Переменные n,x,y называются глобальными по отношению к процедуре Step2. Значения глобальных переменных доступны и могут быть использованы в любой точке основной программы, в том числе в процедуры Step2.
В процедурах в качестве формальных параметров могут быть использованы переменные структурированного типа, например, имена массивов. При определении их типа в заголовке процедуры указывается имя типа, описанное в вызывающей программе.
Пример 3. Опишем процедуру нахождения максимального элемента в массиве вещественных чисел Z1, Z2, …, Z3.
Procedure PrMax (n:integer; z:massiv; Var max:real; Var k:integer);
Var
i:integer;
Begin {PrMax}
max:=z[1];
k:=1;
for i:=2 to n do
if max < z[i]
then
begin
max:=z[i];
k:=i;
end;
End; {PrMax};
В процедуре PrMax в качестве исходных данных определены параметры z, представляющий собой имя массива, тип которого massiv должен быть определён в основной программе, и его размер n; в качестве результатов вычислений – параметры max, k, описанные в разделах Var заголовка процедуры и представляющие значение и номер максимального элемента в массиве.
Вызов процедур производится с помощью специального оператора вызова процедуры, имеющего вид:
<имя>[(<список фактических параметров>)]
Здесь:
<имя> - имя процедуры, к которой происходит обращение;
<список фактических параметров> – перечень конкретных значений (выражений) и имён, подставляемых на место формальных параметров процедуры при каждом её вызове и выполнении.
Замена формальных параметров фактическими осуществляется в порядке их следования слева направо. Число и типы формальных и фактических параметров должны совпадать!
Пример 4. Используя процедуру Step1, составим программу вычисления степени z=a^m с целым показателем m и a <>0. Степень с целым показателем определяется формулой:
1, если m=0;
a^m= a^m, если m>0;
1/a^-m, если m<0
{Определение степени с целым показателем}
Procedure Step4;
Var
m:integer;
a, z:real;
{Определение степени с натуральным показателем}
Procedure Step1 (n:integer; x:real; Var y:real);
Var
i:integer;
Begin {Step1}
y:=1;
for i:=1 to n do
y:= y*x
End; {Step1};
Begin {Step4} {Основная программа}
Write (‘Введите a,m’);
ReadLn(a, m);
Write (a, ‘в степени’, m);
if m=0
then
z:=1
else if m>0
then
Step1(m,a,z) {Вызов процедуры}
else
Step1(-m,1/a,z); {Вызов процедуры}
WriteLn(‘равно’, z)
End; {Step4};
Оператор вызова процедуры в программе использован дважды, в первом случае происходит замена формальных параметров n,x,y на фактические m,a,z, во втором- на –m,1/a,z. После выполнения действий, предусмотренных операторами процедуры, в программу возвращается значение результата, присвоенное переменной z. Возврат управления осуществляется к оператору программы, следующему за оператором вызова процедуры, к оператору WriteLn.
Если осуществляется вызов процедуры без параметров, то оператор вызова процедуры представляет собой указание только её имени.
Пример 5. Составим программу вычисления степени y=x^n с целым показателем, используя процедуру Step2 без параметров.
{Определение степени с целым показателем}
Procedure Step5;
Var
n:integer;
x, y:real;
Procedure Step2;
Var
i:integer;
Begin {Step2}
y:=1;
for i:=1 to n do
y:= y*x
End; {Step2};
Begin {Step5} {Основная программа}
Write (‘Введите x,n’);
ReadLn(x, n);
Write (x, ‘в степени’, n);
if n=0
then
y:=1
else if n>0
then
Step2
else
begin
n:=-n;
x:=1/x;
Step2 {Вызов процедуры}
end;
WriteLn(‘равно’, y)
End; {Step5};
В программе оператор вызова процедуры осуществляет только передачу управления этой процедуре. Исходные данные передаются в процедуру с помощью глобальных по отношению к ней переменных n,x, описанных и определённых в основной программе. Аналогично через глобальную переменную y возвращается в программу и результат вычислений.
4. Классификация программного обеспечения (ПО) ЭВМ. Свойства ПО. Функции операционных систем. (Операционные системы)
Классификация программного обеспечения ЭВМ
ПО
СПО ППО
MSOffice СОУВП САП MathCAD
AutoCAD
И т.д.
ОС отладчики
драйверы ассемблеры и микроассемблеры
загрузчики редакторы (текстовые)
системные загрузчики
библиотеки документация
оболочки препроцессоры
документация редакторы связи
текст. редакторы трансляторы
ППО (прикладное программное обеспечение) – это программы, комплексы программ и пакеты программ, которые предназначены для решения задач из данной предметной области. (MathCad , Microsoft Office , Бухгалтерия 1С и т. д.)
СПО (системное программное обеспечение) - это программы, комплексы программ и пакеты программ, которые предназначены для обеспечения эффективной организации вычислительного процесса на вычислительной системе.
САП (Системы автоматизированного программирования).
Текстовые редакторы: а) для составления программ;
б) для записи и редактирования пакетных файлов.
Ассемблер - это язык символического кодирования, предназначенный для записи алгоритма в виде псевдокоманд, имитирующий команды вычислительной машины.
Макроассемблер - это ассемблер, допускающий использование подпрограмм, представленных в виде макроопределений.
Препроцессор – это программа, позволяющая использовать в программном коде директивы, позволяющие включать файлы, обобщенные имена констант, условные конструкции и т. д.
Транслятор – переводит исходный модуль, написанный на языке высокого уровня в объектный код.
Компиляторы – это трансляторы, в которых сначала осуществляется полный перевод программы, а затем ее выполнение.
Интерпретаторы – это трансляторы, в которых фазы перевода и выполнения меняются (повторяются).
Загрузчик – это программа, которая позволяет разместить другую программу в определенное место памяти (назначить адреса).
Редакторы связи (связывающие загрузчики) – это загрузчики, которые позволяют не только размещать программу в памяти, но и компоновать ее из отдельно-транслируемых модулей.
Отладчики – это программы, позволяющие отыскивать ошибки времени исполнения. Синтаксические ошибки отлавливаются транслятором, а ошибки времени выполнения отлавливаются ОС.
Отладчик, включенный в состав ОС, обязательно ориентирован на конкретную версию ОС.
Свойства ПО.
1) Любое ПО характеризуется машинно-зависимыми свойствами и машинно-независимыми свойствами.
- Машинно-зависимые свойства определяются процентом операторов программ, написанных в коде данной машины.
- Машинно-независимые свойства определяются процентом операторов программ, записанных на языке высокого уровня.
пример: MS-DOS – фактически полностью машинно-зависима;
UNIX – машинно-независима.
2) Второе свойство ПО – переносимость.
Если СПО можно ставить на вычислительные системы различной архитектуры то оно переносимо.
3) Третье свойство ПО – Вариабельность.
Свойство ПО подвергаться модификации.
Системное обеспечение управления вычислительного процесса (СОУВП)
Операционная система – это комплекс программ, предназначенных для эффективной организации вычислительного процесса, управления ходом этого процесса и создания удобного интерфейса для пользователя.
Функции ОС:
загрузка и передача управления первой команде выполняемой программы;
выделяет необходимые ресурсы для выполнения данной программы или распределяет их между несколькими программами;
обнаруживает сбои или ошибки в ходе вычислительного процесса;
предоставляет пользователю средства для управления ходом вычислительного процесса, средства для настройки ОС, средства, информирующие пользователя о ходе вычислительного процесса (интерфейс пользователя);
Типы ОС:
1) однопрограммные ОС (в памяти только одна программа, и все ресурсу принадлежат ей(MS – DOS));
2) многопрограммные ОС (одновременно в памяти выполняется несколько задач). Различают истинную мультизадачность (в этом случае есть несколько процессоров в системе, каждый из которых выполняет свою задачу (ЕС1096)) и кажущуюся мультизадачность (процессор ОС переключается на выполнение первой, второй, третьей и т. д. программ).
В мультипрограммных ОС каждая программа имеет свой приоритет (OS/360, 370(IBM), Unix, Linux);
3) системы коллективного пользования (допускают одновременную работу нескольких пользователей под управлением одной ОС, выделяя каждому пользователю фиксированные ресурсы и определенное количество времени) – (UNIX , LINUX);
4) системы реального времени (в этих системах время реакции системы на любое событие в управляемом объекте не превышает времени завершения этого события(RT/11 , RSX));
5) Сетевые системы.(MS Windows NT)
Структура ОС и основные понятия ОС
Как правило, любая ОС состоит из двух основных частей: ядра и нерезидентной части, которая содержит процедуры, нечасто используемые при работе ОС. Ядро содержит загрузчик ОС и набор процедур, управляющих теми или иными функциями ОС, а именно:
подсистему управления процессов (диспетчер).
подсистему управления основной памяти.
подсистему управления виртуальной памяти (если она есть).
Кроме того ОС содержит совокупность резидентных драйверов: драйвер диска, мыши, клавиатуры и др.
Кроме того ОС содержит командные процессоры-интерпретаторы входного языка ОС. Командный процессор служит для обработки команд ОС и выдачи сообщений.
пример: command.com – интерпретатор для DOS;
Shell – интерпретатор для Linux.
Кроме того, в состав ядра входят подсистемы управления ввода – вывода (BIOS для DOS).
Для ОС отводится фиксированная область памяти, защищенная от несанкционированного доступа. В этой области располагается ядро и системная область памяти, где располагаются таблицы ОС, структуры данных ОС, и, возможно, системные библиотеки, которые содержат макроопределения примитивов ОС.
Примитивом называется процедура, реализующая ту или иную элементарную функцию ОС (создание буферов ввода-вывода, просмотр буфера ввода и т. д.).
В состав системных библиотек обычно входят команды ОС: внутренние и внешние.
В любой ОС в системной области выделяется «среда округления». Она играет роль почтового ящика для обмена информацией между программами.
Любая ОС имеет два файла:
файл конфигурации системы (config.sys для DOS). Он определяет конкретную на данный момент конфигурацию ОС и ее параметры.
Файл автозапуска (autoexec.bat для DOS). Он предназначен для формирования удобной для пользователя операционной среды.
Пример: MS –DOS v. 6.22.
1) BIOS – (базовая система ввода – вывода)
Микросхема, которая содержит все подпрограммы, соответствующие примитивам ОС. Обычно 64 килобайта.
команда int <номер прерывания>.
BIOS управляется специальными векторами прерываний, которые представляют собой ячейки из четырех байт, расположенных в начале оперативной памяти.
Вектора прерываний содержат адрес соответствующей программы обработки прерываний, которые заставляют ядро ОС выполнить ту/иную функцию.
2) _IO.SYS – (система ввода – вывода);
3) _DOS.SYS – содержит основные подпрограммы управления; в частности, примитивы, записанные в этом файле, аналогичны процедурам BIOS;
4) COMMAND.COM – командный процессор;
5) CONFIG.SYS – файл конфигурации;
6) AUTOEXEC.BAT
5. Ортографические и ортогональные проекции. (Геометрическое моделирование в САПР)
Прямоугольные ( ортогональные) проекции – это проекции, у которых плоскости проецирования параллельны координатным плоскостям. Частным случаем ортогональной проекции, при которой плоскости проецирования совпадают с координатными плоскостями, является ортографическая проекция.
Общий вид матрицы преобразований для получения прямоугольной (ортографической) проекции следующий:
а 0 0 0
0 е 0 0
Т = 0 0 i 0
0 0 0 1
При этом два из трёх диагональных элементов (a,e,i) равны единице, а третий должен быть нулевым. Например, ортографическая проекция на плоскость XOY (Z=0) определяется следующей матрицей преобразований:
1 0 0 0
0 1 0 0
Тz = 0 0 0 0
0 0 0 1
Ортогональные проекции являются частным случаем прямоугольной проекции, при котором проецирование осуществляется на координатные плоскости. Для выполнения ортогональных построений необходимо сместить плоскость проецирования параллельно одной из координатных плоскостей. Например, матрица преобразований для построения ортогональной проекции на плоскость Z=P будет иметь вид:
1 0 0 0
0 1 0 0
Тz=p = 0 0 0 0
0 0 p 1
Таким образом, ортогональное или прямоугольное проецирование определяется матрицей преобразований с нулевой строкой, соответствующей той оси, перпендикулярно которой находится плоскость проецирования.
6. Быстрая сортировка. (Лингвистическое и программное обеспечение САПР)
Этот алгоритм основан на сравнениях и обменах пар элементов расположенных не в соседних позициях, а удалённых друг от друга в сортируемом массиве. Это позволяет сократить среднее количество необходимых операций от О(n2) до О(nlog2n).
В основе быстрой сортировки лежит процедура разделения сортируемого массива на 2 части следующим образом: пусть А=(а1,а2,...,аn) – сортируемый массив. Выбирается некоторый элемент х из этого массива, который называется разделяющим элементом. Существует много способов выбора разделяющего элемента, например х = а1. Затем элементы массива А переупорядочиваются в соответствии с требованиями:
Если эти условия удалось выполнить, то элемент х занял свою окончательную позицию. Далее, чтобы отсортировать весь массив, следует повторить разделение подмассивов А1 и А2, а также всех других подмассивов, получаемых при последующих разделениях и имеющих не менее 2х элементов. Этот алгоритм является рекурсивным и основан на процедуре разделения. Рассмотрим один из вариантов процедуры разделения, в которой полагается, что разделяющий элемент является первым: х = а1. Вводятся 2 счётчика: i =1 и j = n. Процедура разделения включает шаги:
1. просматриваются элементы справа и их ключи сравнивают с ключом разделяющего элемента: x = ai, если ai <= aj, то j= j-1. Если ai > aj, то производится обмен пары ai aj и i= i+1. Теперь разделяющий элемент x= aj.
2. просматриваются элементы слева и их ключи сравнивают с ключом разделяющего элемента: x = ai, если ai <= aj, то j= j-1. Если ai > aj, то производится обмен пары ai aj и j= j-1. Теперь разделяющий элемент x= ai.
3. шаги 1 и 2 выполняются поочередно до тех пор, пока после некоторого из них не получим равенство i=j. Это означает, что разделение закончено и разделяющий элемент находится в этой позиции.
Пример. (25, 57, 48, 37, 12, 92, 86, 33)
|
Шаг |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
|
1 |
25 25 25 25 25 12 |
57 57 25 25 25 |
48 48 |
37 37 |
12 12 25 25 57 |
92 92 |
86 86 |
33 |
i=1, j=8 i=1, j=7 i=1, j=6 i=1, j=5 обмен i=2, j=5 обмен i=2, j=4 i=2, j=3 i=2, j=2 |
|
2 |
|||||||||
|
3 |
|||||||||
|
4 |
|||||||||
|
5 |
|||||||||
|
6 |
|||||||||
|
7 |
|||||||||
|
8 |
|||||||||
|
9 |
|||||||||
|
10 |
|||||||||
12 25 (48 37 57 92 86 33)
После выполнения первого разделения задача сортровки разбита на 2 подзадачи:
12 25 (33 37) 48 (92 86 57)
12 25 33 37 48 (92 86 57)
12 25 33 37 48 (57 86) 92
12 25 33 37 48 57 86 92
Алгоритм быстрой сортировки не является минимальным по памяти поскольку при выполнении рекурсивной процедуры или при её моделировании с помощью стеков требуются затраты памяти О(log2n).
Рассмотрим реализацию алгоритма в виде процедуры SORT (L,R). Будем считать, что массив ключей a[1..n] – целочисленный. Тогда:
procedure SW (i,j: integer);
var x: integer;
begin
x:=a[i];
a[i]:=a[j];
a[j]:=x;
end;
procedure SORT(L,R: integer);
var i,j: integer;
begin
if L<R then
begin
i:=L;
j:=R;
repeat {i=j}
while (a[i]<=a[j]) and
(i<j) then j:=j-1;
if i<j then
begin
SW(I,j);
i:=i+1;
end;
while (a[i]<=a[j]) and (i<j) *
then i:=i+1;
if i<j then
begin
SW(i,j);
j:=j-1;
end;
until i=j;
if L<i-1 then SORT(L, i-1);
if i+1<R then SORT(i+1, R);
end;
Покажем как рекурсию заменить итерацией на примере алгоритма быстрой сортировки. Для этого после каждого разделения сортируемого массива или подмассива одна из частей (например, левая) делится далее, а границы второй (правой) части сохраняется в стеке для последующего разделения. Покажем реализацию такой процедуры в предположении, что такая сортировка выполняется для a[1..n], а в программе используется 2 массива: STL[1..100], STR[1..100] – стеки для хранения левых и правых границ соответственно и указатель вершины top.
procedure SORT_S;
var i,j,top,L,R: integer;
STL,STR: array [1..100] of integer;
begin
top:=1; STL[top]:=1; STR[top]:=n;
repeat {top=0}
L:=STL[top]; R:=STR[top];
top:= top-1;
repeat {L=R}
i:=L; j:=R;
*
if L<i-1 then R:=i-1
else R:=L;
if i-1<R then
begin
top:=top+1;
STL[top]:=i+1; STR[top]:=R;
end;
until L=R;
until top=0;
end;
Быстрая сортировка – наиболее эффективный на данный момент алгоритм. Однако как и все усовершенствованные методы он имеет следующий недостаток: невысокая скорость работы при малых значениях n. Рекурсивная реализация быстрой сортировки позволяет легко устранить этот недостаток путём включения прямого метода сортировки массива с небольшим числом элементов. Экспериментальные исследования показывают: если подмассив содержит 9 или менее элементов, то более эффективно использовать прямой метод (метод сортировки простыми вставками).