Программирование на языке Паскаль Массивы

2 Массив – это группа однотипных элементов, имеющих общее имя и расположенных в памяти рядом. Особенности: все элементы имеют один тип весь массив имеет одно имя все элементы расположены в памяти рядом Примеры: список учеников в классе квартиры в доме школы в городе данные о температуре воздуха за год

3 Массивы A массив 3 15 НОМЕР элемента массива (ИНДЕКС) НОМЕР элемента массива (ИНДЕКС) A[1] A[2] A[3] A[4] A[5] ЗНАЧЕНИЕ элемента массива A[2] НОМЕР (ИНДЕКС) элемента массива: 2 ЗНАЧЕНИЕ элемента массива: 10 A[5]:=3; 3

Объявление массивов 4 Зачем объявлять? определить имя массива определить тип массива определить число элементов выделить место в памяти Массив целых чисел: Размер через константу: имя начальный индекс конечный индекс тип элементов тип элементов var A: array[1.. ] of integer; const N=5; N var A : array[ ] of integer ;

Объявление массивов 5 Массивы других типов: Другой диапазон индексов: Индексы других типов: var X, Y: array [1..10] of real; C: array [1..20] of char; var X, Y: array [1..10] of real; C: array [1..20] of char; var Q: array [0..9] of real; C: array [-5..13] of char; var Q: array [0..9] of real; C: array [-5..13] of char; var A: array ['A'..'Z'] of real; B: array [False..True] of integer;... A['C'] := *A['B']; B[False] := B[False] + 1; var A: array ['A'..'Z'] of real; B: array [False..True] of integer;... A['C'] := *A['B']; B[False] := B[False] + 1;

Что неправильно? 6 var a: array[10..1] of integer;... A[5] := 4.5; var a: array[10..1] of integer;... A[5] := 4.5; [1..10] var a: array ['z'..'a'] of integer;... A['B'] := 15; var a: array ['z'..'a'] of integer;... A['B'] := 15; A['b'] ['a'..'z'] var a: array [0..9] of integer;... A[10] := 'X'; var a: array [0..9] of integer;... A[10] := 'X';

7 Массивы Объявление: Ввод с клавиатуры: Поэлементные операции: Вывод на экран: var a: array[1..100] of integer; n,i: integer; var a: array[1..100] of integer; n,i: integer; WriteLn( 'Введите кол-во элементов массива:' ); ReadLn(n); for i:=1 to n do begin write('a[', i, ']='); readln ( a[i] ); end; WriteLn( 'Введите кол-во элементов массива:' ); ReadLn(n); for i:=1 to n do begin write('a[', i, ']='); readln ( a[i] ); end; a[1] = a[2] = a[3] = a[4] = a[5] = Почему write ? ? for i:=1 to n do a[i]:=a[i]*2; for i:=1 to n do a[i]:=a[i]*2; writeln('Массив A:'); for i:=1 to n do write(a[i]:4); writeln('Массив A:'); for i:=1 to n do write(a[i]:4); Массив A:

Задания 8 «3»: Ввести c клавиатуры массив из 5 элементов, умножить их на 2 и вывести на экран. Пример: Введите пять чисел: Результат: «4»: Ввести c клавиатуры массив из 5 элементов, найти среднее арифметическое всех элементов массива. Пример: Введите пять чисел: среднее арифметическое При изменении N остальная программа не должна изменяться! !

Задания 9 «5»: Ввести c клавиатуры массив из 5 элементов, найти минимальный из них. Пример: Введите пять чисел: минимальный элемент 3

Программирование на языке Паскаль Максимальный элемент массива

Максимальный элемент 11 Задача: найти в массиве максимальный элемент. Алгоритм: Псевдокод: { считаем, что первый элемент – максимальный } for i:=2 to N do if a[i] > { максимального } then { запомнить новый максимальный элемент a[i] } { считаем, что первый элемент – максимальный } for i:=2 to N do if a[i] > { максимального } then { запомнить новый максимальный элемент a[i] } Почему цикл от i=2 ? ?

Максимальный элемент 12 max := a[1]; { считаем, что первый – максимальный } iMax := 1; for i:=2 to N do { проверяем все остальные } if a[i] > max then { нашли новый максимальный } begin max := a[i]; { запомнить a[i] } iMax := i; { запомнить i } end; max := a[1]; { считаем, что первый – максимальный } iMax := 1; for i:=2 to N do { проверяем все остальные } if a[i] > max then { нашли новый максимальный } begin max := a[i]; { запомнить a[i] } iMax := i; { запомнить i } end; Дополнение: как найти номер максимального элемента? Как упростить? ? По номеру элемента iMax всегда можно найти его значение a[iMax]. Поэтому везде меняем max на a[iMax] и убираем переменную max. a[iMax]

Программа 13 program qq; const N = 5; var a: array [1..N] of integer; i, iMax: integer; begin { здесь нужно ввести массив с клавиатуры } iMax := 1; {считаем, что первый – максимальный} for i:=2 to N do { проверяем все остальные} if a[i] > a[iMax] then { новый максимальный} iMax := i; { запомнить i } writeln; {перейти на новую строку} writeln('Максимальный элемент a[', iMax, ']=', a[iMax]); end. program qq; const N = 5; var a: array [1..N] of integer; i, iMax: integer; begin { здесь нужно ввести массив с клавиатуры } iMax := 1; {считаем, что первый – максимальный} for i:=2 to N do { проверяем все остальные} if a[i] > a[iMax] then { новый максимальный} iMax := i; { запомнить i } writeln; {перейти на новую строку} writeln('Максимальный элемент a[', iMax, ']=', a[iMax]); end. iMax := 1; {считаем, что первый – максимальный} for i:=2 to N do { проверяем все остальные} if a[i] > a[iMax] then { новый максимальный} iMax := i; { запомнить i } iMax := 1; {считаем, что первый – максимальный} for i:=2 to N do { проверяем все остальные} if a[i] > a[iMax] then { новый максимальный} iMax := i; { запомнить i }

Задания 14 «3»: Ввести с клавиатуры массив из 5 элементов, найти в нем минимальный элемент и его номер. Пример: Исходный массив: мимимальный A[4]=-10 «4»: Ввести с клавиатуры массив из 5 элементов, найти в нем максимальный и минимальный элементы и их номера. Пример: Исходный массив: максимальный A[3]=10 минимальный A[4]=-10

Задания 15 «5»: Ввести с клавиатуры массив из 5 элементов, найти в нем два максимальных элемента и их номера. Пример: Исходный массив: максимальные A[3]=10, A[5]=5

Программирование на языке Паскаль Обработка массивов

Случайные процессы 17 Случайно… 1)встретить друга на улице 2)разбить тарелку 3)найти 10 рублей 4)выиграть в лотерею Случайный выбор: 1)жеребьевка на соревнованиях 2)выигравшие номера в лотерее Как получить случайность?

Случайные числа на компьютере 18 Электронный генератор нужно специальное устройство нельзя воспроизвести результаты малый период (последовательность повторяется через 10 6 чисел) Метод середины квадрата (Дж. фон Нейман) в квадрате Псевдослучайные числа – обладают свойствами случайных чисел, но каждое следующее число вычисляется по заданной формуле.

Распределение случайных чисел 19 Модель: снежинки падают на отрезок [a,b] a b a b распределение равномерное неравномерное Сколько может быть разных распределений? ?

Распределение случайных чисел 20 Особенности: распределение – это характеристика всей последовательности, а не одного числа равномерное распределение одно, компьютерные датчики случайных чисел дают равномерное распределение неравномерных – много любое неравномерное можно получить с помощью равномерного a b a b равномерное распределение неравномерное распределение

Генератор случайных чисел в Паскале 21 Целые числа в интервале [0,N): var x: integer;... x := random ( 100 ); { интервал [0,99] } Вещественные числа в интервале [0,1) var x: real;... x := random; { интервал [0,1) }

Заполнение массива случайными числами 22 const N = 5; var A: array [1..N] of integer; i: integer; begin writeln('Исходный массив:'); for i:=1 to N do begin A[i] := random(100) + 50; write(A[i]:4); end;... const N = 5; var A: array [1..N] of integer; i: integer; begin writeln('Исходный массив:'); for i:=1 to N do begin A[i] := random(100) + 50; write(A[i]:4); end;... Зачем сразу выводить? ? случайные числа в интервале [50,150)

Подсчет элементов 23 Задача: заполнить массив случайными числами в интервале [-1,1] и подсчитать количество нулевых элементов. Идея: используем переменную-счётчик. Решение: 1)записать в счётчик ноль 2)просмотреть все элементы массива: если очередной элемент = 0, то увеличить счётчик на 1 3)вывести значение счётчика

Подсчет элементов 24 начало конец нет да нет да i

Подсчет элементов 25 program qq; const N = 5; var A: array [1..N] of integer; i, count: integer; begin { здесь надо заполнить массив } count:= 0; for i:=1 to N do if A[i] = 0 then count:= count + 1; writeln('Нулевых элементов: ', count); end. program qq; const N = 5; var A: array [1..N] of integer; i, count: integer; begin { здесь надо заполнить массив } count:= 0; for i:=1 to N do if A[i] = 0 then count:= count + 1; writeln('Нулевых элементов: ', count); end. for i:=1 to N do if A[i] = 0 then count:= count + 1; for i:=1 to N do if A[i] = 0 then count:= count + 1; перебираем все элементы массива

Задания 26 «3»: Заполнить массив случайными числами в интервале [-2,2] и подсчитать количество положительных элементов. «4»: Заполнить массив случайными числами в интервале [20,100] и подсчитать отдельно число чётных и нечётных элементов. «5»: Заполнить массив случайными числами в интервале [1000,2000] и подсчитать число элементов, у которых вторая с конца цифра – четная.

Сумма выбранных элементов 27 Задача: заполнить массив случайными числами в интервале [-10,10] и подсчитать сумму положительных элементов. Идея: используем переменную S для накопления суммы. Решение: 1)записать в переменную S ноль 2)просмотреть все элементы массива: если очередной элемент > 0, то добавить к сумме этот элемент 3)вывести значение суммы S:=0S:= A[1]S:= A[1]+A[2] S:= A[1]+A[2]+A[3] S:= A[1]+A[2]+…+A[N] S:= S+A[i]

Сумма выбранных элементов 28 начало конец нет да нет да i 0? S:= S + A[i] i:= i + 1 пока ни одного не нашли начать с 1-ого перейти к следующему нашли еще 1

Сумма выбранных элементов 29 program qq; const N = 5; var A: array [1..N] of integer; i, S: integer; begin { здесь надо заполнить массив } S:= 0; for i:=1 to N do if A[i] = 0 then count:= count + 1; writeln('Cумма полож. элементов: ', S); end. program qq; const N = 5; var A: array [1..N] of integer; i, S: integer; begin { здесь надо заполнить массив } S:= 0; for i:=1 to N do if A[i] = 0 then count:= count + 1; writeln('Cумма полож. элементов: ', S); end. for i:=1 to N do if A[i] > 0 then S:= S + A[i]; for i:=1 to N do if A[i] > 0 then S:= S + A[i]; перебираем все элементы массива

Задания 30 «3»: Заполнить массив из 10 элементов случайными числами в интервале [-10,10] и подсчитать сумму всех отрицательных элементов. «4»: Заполнить массив из 10 элементов случайными числами в интервале [0,100] и подсчитать среднее значение всех элементов, которые

Поиск в массиве 31 Задача – найти в массиве элемент, равный X, или установить, что его нет. Пример: если в классе ученик с фамилией Пупкин? Алгоритм: 1)начать с 1-ого элемента ( i:=1 ) 2)если очередной элемент ( A[i] ) равен X, то закончить поиск иначе перейти к следующему элементу:

Поиск элемента, равного X 32 начало конец нет да нет да i

Поиск элемента в массиве 33 program qq; const N=5; var a:array[1..N] of integer; i, X: integer; begin { здесь надо заполнить массив } i:=1; while A[i]X do i:=i+1; if i

Задания 34 «3»: Заполнить массив из 10 элементов случайными числами в интервале [10..20] и найти элемент, равный X. Пример: Исходный массив: Что ищем? 20 A[5] = 20 «4»: Заполнить массив из 10 элементов случайными числами в интервале [0..4] и вывести номера всех элементов, равных X. Пример: Исходный массив: Что ищем? 0 A[2], A[5], A[10]

Задания 35 «5»: Заполнить массив из 10 элементов случайными числами в интервале [0..4] и определить, есть ли в нем одинаковые соседние элементы. Пример: Исходный массив: Ответ: есть

Реверс массива 36 Задача: переставить элементы массива в обратном порядке. Алгоритм: поменять местами A[1] и A[N], A[2] и A[N-1], … Псевдокод: 35…97 79…53 12…N-1N 12… N for i:=1 to N do { поменять местами A[i] и A[N+1-i] } for i:=1 to N do { поменять местами A[i] и A[N+1-i] } сумма индексов N+1 Что неверно? ? N div 2 do

Как переставить элементы? Задача: поменять местами содержимое двух чашек. Задача: поменять местами содержимое двух ячеек памяти ? ? x y c c := x; x := y; y := c; c := x; x := y; y := c; x := y; y := x; x := y; y := x; Можно ли обойтись без c ? ?

Программа 38 program qq; const N = 10; var A: array[1..N] of integer; i, c: integer; begin { заполнить массив } { вывести исходный массив } { вывести полученный массив } end. program qq; const N = 10; var A: array[1..N] of integer; i, c: integer; begin { заполнить массив } { вывести исходный массив } { вывести полученный массив } end. for i:=1 to N div 2 do begin c:=A[i]; A[i]:=A[N+1-i]; A[N+1-i]:=c; end; for i:=1 to N div 2 do begin c:=A[i]; A[i]:=A[N+1-i]; A[N+1-i]:=c; end;

Задания 39 «3»: Заполнить массив из 10 элементов случайными числами в интервале [ ] и сделать реверс всех элементов, кроме последнего. Пример: Исходный массив: Результат: «4»: Заполнить массив из 10 элементов случайными числами в интервале [ ] и сделать реверс всех элементов, кроме последнего. Пример: Исходный массив: Результат:

Задания 40 «5»: Заполнить массив из 10 элементов случайными числами в интервале [ ] и сделать реверс отдельно для 1-ой и 2-ой половин массива. Пример: Исходный массив: Результат: «6»: Заполнить массив из 12 элементов случайными числами в интервале [ ] и выполнить реверс для каждой трети массива. Пример: Исходный массив: Результат:

Циклический сдвиг 41 Задача: сдвинуть элементы массива влево на 1 ячейку, первый элемент становится на место последнего. Алгоритм: A[1]:=A[2]; A[2]:=A[3];… A[N-1]:=A[N]; Цикл: 3581… …N-1N 581…973 for i:=1 to N-1 do A[i]:=A[i+1]; for i:=1 to N-1 do A[i]:=A[i+1]; Что неверно? ? почему не N ?

Программа 42 program qq; const N = 10; var A: array[1..N] of integer; i, c: integer; begin { заполнить массив } { вывести исходный массив } { вывести полученный массив } end. program qq; const N = 10; var A: array[1..N] of integer; i, c: integer; begin { заполнить массив } { вывести исходный массив } { вывести полученный массив } end. c := A[1]; for i:=1 to N-1 do A[i]:=A[i+1]; A[N] := c; c := A[1]; for i:=1 to N-1 do A[i]:=A[i+1]; A[N] := c;

Задания 43 «3»: Заполнить массив из 10 элементов случайными числами в интервале [ ] и выполнить циклический сдвиг влево без первого элемента. Пример: Исходный массив: Результат: «4»: Заполнить массив из 10 элементов случайными числами в интервале [ ] и выполнить циклический сдвиг ВПРАВО. Пример: Исходный массив: Результат:

Задания 44 «5»: Заполнить массив из 12 элементов случайными числами в интервале [ ] и выполнить циклический сдвиг ВПРАВО на 4 элемента. Пример: Исходный массив: Результат:

Выбор нужных элементов 45 Задача – найти в массиве элементы, удовлетворяющие некоторому условию (например, отрицательные), и скопировать их в другой массив. Примитивное решение: const N = 5; var i: integer; A, B: array[1..N] of integer; begin { здесь заполнить массив A } for i:=1 to N do if (A[i] < 0) then B[i]:= A[i];... end. const N = 5; var i: integer; A, B: array[1..N] of integer; begin { здесь заполнить массив A } for i:=1 to N do if (A[i] < 0) then B[i]:= A[i];... end ? ? ? ? ? A B Что плохо? ?

Выбор нужных элементов 46 Решение: ввести счетчик найденных элементов count, очередной элемент ставится на место B[count]. count:=0; for i:=1 to N do if (A[i] < 0) then begin B[ ]:= A[i]; count:=count+1; end; count:=0; for i:=1 to N do if (A[i] < 0) then begin B[ ]:= A[i]; count:=count+1; end; ? ? ? ? ? A B count

Как вывести массив B? 47 Примитивное решение: writeln('Выбранные элементы:'); for i:=1 to N do write(B[i], ' '); writeln('Выбранные элементы:'); for i:=1 to N do write(B[i], ' '); Что плохо? ? Правильное решение: writeln('Выбранные элементы:'); for i:=1 to do write(B[i], ' '); writeln('Выбранные элементы:'); for i:=1 to do write(B[i], ' '); count

Задания 48 «3»: Заполнить массив случайными числами в интервале [-10,10] и записать в другой массив все положительные числа. Пример: Исходный массив: Положительные числа: 3 7 «4»: Заполнить массив случайными числами в интервале [20,100] и записать в другой массив все числа, которые оканчиваются на 0. Пример: Исходный массив: Заканчиваются на 0: 40 30

Задания 49 «5»: Заполнить массив случайными числами и выделить в другой массив все числа, которые встречаются более одного раза. Пример: Исходный массив: Результат: 1 2

Программирование на языке Паскаль Сортировка массивов

Сортировка 51 Сортировка – это расстановка элементов массива в заданном порядке (по возрастанию, убыванию, последней цифре, сумме делителей, …). Задача: переставить элементы массива в порядке возрастания. Алгоритмы: простые и понятные, но неэффективные для больших массивов метод пузырька метод выбора сложные, но эффективные «быстрая сортировка» (Quick Sort) сортировка «кучей» (Heap Sort) сортировка слиянием пирамидальная сортировка сложность O(N 2 ) время N O(N 2 )

Метод пузырька 52 Идея – пузырек воздуха в стакане воды поднимается со дна вверх. Для массивов – самый маленький («легкий» элемент перемещается вверх («всплывает») начиная снизу, сравниваем два соседних элемента; если они стоят «неправильно», меняем их местами за 1 проход по массиву один элемент (самый маленький) становится на свое место ый проход 2-ой проход 3-ий проход Для сортировки массива из N элементов нужен N-1 проход (достаточно поставить на свои места N-1 элементов).

Программа 53 1-ый проход: 5 2 … … N-1 N сравниваются пары A[N-1] и A[N], A[N-2] и A[N-1] … A[1] и A[2] A[j] и A[j+1] 2-ой проход A[1] уже на своем месте! ! for j:=N-1 downto 2 do if A[j] > A[j+1] then begin c:=A[j]; A[j]:=A[j+1]; A[j+1]:=c; end; for j:=N-1 downto 2 do if A[j] > A[j+1] then begin c:=A[j]; A[j]:=A[j+1]; A[j+1]:=c; end; 2 for j:=N-1 downto 1 do if A[j] > A[j+1] then begin c:=A[j]; A[j]:=A[j+1]; A[j+1]:=c; end; for j:=N-1 downto 1 do if A[j] > A[j+1] then begin c:=A[j]; A[j]:=A[j+1]; A[j+1]:=c; end; 1 i -ый проход for j:=N-1 downto i do... for j:=N-1 downto i do... i 1 5 … … N-1 N

Программа 54 program qq; const N = 10; var A: array[1..N] of integer; i, j, c: integer; begin { заполнить массив } { вывести исходный массив } { вывести полученный массив } end. program qq; const N = 10; var A: array[1..N] of integer; i, j, c: integer; begin { заполнить массив } { вывести исходный массив } { вывести полученный массив } end. for i:=1 to N-1 do begin for j:=N-1 downto i do if A[j] > A[j+1] then begin с := A[j]; A[j] := A[j+1]; A[j+1] := с; end; for i:=1 to N-1 do begin for j:=N-1 downto i do if A[j] > A[j+1] then begin с := A[j]; A[j] := A[j+1]; A[j+1] := с; end; Почему цикл по i до N-1 ? ? i элементы выше A[i] уже поставлены

Задания 55 «3»: Заполнить массив из 10 элементов случайными числами в интервале [ ] и отсортировать его по убыванию. Пример: Исходный массив: Результат: «4»: Заполнить массив из 10 элементов случайными числами в интервале [0..100] и отсортировать его по последней цифре. Пример: Исходный массив: Результат:

Задания 56 «5»: Заполнить массив из 10 элементов случайными числами в интервале [0..100] и отсортировать первую половину по возрастанию, а вторую – по убыванию. Пример: Исходный массив: Результат:

Метод пузырька с флажком 57 Идея – если при выполнении метода пузырька не было обменов, массив уже отсортирован и остальные проходы не нужны. Реализация: переменная-флаг, показывающая, был ли обмен; если она равна False, то выход. repeat flag := False; { сбросить флаг } for j:=N-1 downto 1 do if A[j] > A[j+1] then begin с := A[j]; A[j] := A[j+1]; A[j+1] := с; flag := True; { поднять флаг } end; until not flag; { выход при flag=False } repeat flag := False; { сбросить флаг } for j:=N-1 downto 1 do if A[j] > A[j+1] then begin с := A[j]; A[j] := A[j+1]; A[j+1] := с; flag := True; { поднять флаг } end; until not flag; { выход при flag=False } flag := False; flag := True; not flag; var flag: boolean; Как улучшить? ?

Метод пузырька с флажком 58 i := 0; repeat i := i + 1; flag := False; { сбросить флаг } for j:=N-1 downto 1 do if A[j] > A[j+1] then begin с := A[j]; A[j] := A[j+1]; A[j+1] := с; flag := True; { поднять флаг } end; until not flag; { выход при flag=False } i := 0; repeat i := i + 1; flag := False; { сбросить флаг } for j:=N-1 downto 1 do if A[j] > A[j+1] then begin с := A[j]; A[j] := A[j+1]; A[j+1] := с; flag := True; { поднять флаг } end; until not flag; { выход при flag=False } i := 0; i i := i + 1;

Метод выбора 59 Идея: найти минимальный элемент и поставить на первое место (поменять местами с A[1] ) из оставшихся найти минимальный элемент и поставить на второе место (поменять местами с A[2] ), и т.д

Метод выбора 60 for i := 1 to N-1 do begin nMin:= i ; for j:= i+1 to N do if A[j] < A[nMin] then nMin:=j; if nMin i then begin c:=A[i]; A[i]:=A[nMin]; A[nMin]:=c; end; N-1 N нужно N-1 проходов поиск минимального от A[i] до A[N] если нужно, переставляем Можно ли убрать if ? ? i+1 i

Задания 61 «3»: Заполнить массив из 10 элементов случайными числами в интервале [0..99] и отсортировать его по убыванию последней цифры. Пример: Исходный массив: Результат: «4»: Заполнить массив из 10 элементов случайными числами в интервале [0..99] и отсортировать его по возрастанию суммы цифр ( подсказка: их всего две ). Пример: Исходный массив: Результат:

Задания 62 «5»: Заполнить массив из 10 элементов случайными числами в интервале [0..100] и отсортировать первую половину по возрастанию, а вторую – по убыванию. Пример: Исходный массив: Результат:

«Быстрая сортировка» (Quick Sort) 63 Идея – более эффективно переставлять элементы, расположенные дальше друг от друга. Сколько перестановок нужно, если массив отсортирован по убыванию, а надо – по возрастанию? ? N div 2 2 шаг: переставить элементы так: при сортировке элементы не покидают « свою область»! 1 шаг: выбрать некоторый элемент массива X A[i] = X 3 шаг: так же отсортировать две получившиеся области Разделяй и властвуй (англ. divide and conquer)

«Быстрая сортировка» (Quick Sort) 64 Медиана – такое значение X, что слева и справа от него в отсортированном массиве стоит одинаковое число элементов (для этого надо отсортировать массив…). Разделение: 1)выбрать средний элемент массива ( X=67 ) 2)установить L:=1, R:=N 3)увеличивая L, найти первый элемент A[L], который >= X (должен стоять справа) 4)уменьшая R, найти первый элемент A[R], который

«Быстрая сортировка» (Quick Sort) LR LR LR RL L > R : разделение закончено !

«Быстрая сортировка» (Quick Sort) 66 procedure QSort ( first, last: integer); var L, R, c, X: integer; begin if first < last then begin X:= A[(first + last) div 2]; L:= first; R:= last; QSort(first, R); QSort(L, last); end; end. procedure QSort ( first, last: integer); var L, R, c, X: integer; begin if first < last then begin X:= A[(first + last) div 2]; L:= first; R:= last; QSort(first, R); QSort(L, last); end; end. ограничение рекурсии while L X do R:= R - 1; if L

«Быстрая сортировка» (Quick Sort) 67 program qq; const N = 10; var A: array[1..N] of integer; begin { заполнить массив } { вывести исходный массив на экран } Qsort ( 1, N ); { сортировка } { вывести результат } end. program qq; const N = 10; var A: array[1..N] of integer; begin { заполнить массив } { вывести исходный массив на экран } Qsort ( 1, N ); { сортировка } { вывести результат } end. procedure QSort ( first, last: integer);... Сложность (в среднем) ! !

NQuickSort«пузырек» Количество перестановок 68 (случайные данные) От чего зависит скорость? ? Как хуже всего выбирать X? ?

Задания 69 «3»: Заполнить массив из 10 элементов случайными числами в интервале [ ] и отсортировать его с помощью алгоритма быстрой сортировки. «4»: Заполнить массив из 10 элементов случайными числами в интервале [ ] и отсортировать его по убыванию с помощью алгоритма быстрой сортировки. «5»: Заполнить массив из 500 элементов случайными числами в интервале [0..100]. Отсортировать его по возрастанию двумя способами – методом «пузырька» и методом «быстрой сортировки». Вывести на экран число перестановок элементов массива в том и в другом случае. Массив выводить на экран не нужно.