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

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

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

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

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

5 2 способ Var a:array [1.. Большое число] of тип эл-тов; … Begin Readln(n); For i:=1 to n do …… 5

6 Объявление массивов 6 Массивы других типов: Другой диапазон индексов: Индексы других типов: 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;

7 Что неправильно? 7 var a: array[10..1] of integer;... A[5] := 4.5; var a: array[10..1] of integer;... A[5] := 4.5; integer 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';

8 8 Массивы Объявление: Ввод с клавиатуры: Поэлементные операции: Вывод на экран: 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:

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

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

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

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

13 Максимальный элемент 13 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]

14 Программа 14 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 }

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

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

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

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

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

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

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

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

23 Заполнение массива случайными числами 23 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)

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

25 Подсчет элементов 25 начало конец нет да нет да i <= N? count:= 0 i:= 1 A[i] = 0? count:= count + 1 i:= i + 1 пока ни одного не нашли начать с 1-ого перейти к следующему нашли еще 1

26 Подсчет элементов 26 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; перебираем все элементы массива

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

28 Сумма выбранных элементов 28 Задача: заполнить массив случайными числами в интервале [-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]

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

30 Сумма выбранных элементов 30 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]; перебираем все элементы массива

31 Задания 31 «3»: Заполнить массив из 10 элементов случайными числами в интервале [-10,10] и подсчитать сумму всех отрицательных элементов. «4»: Заполнить массив из 10 элементов случайными числами в интервале [0,100] и подсчитать среднее значение всех элементов, которые <50. «5»: Заполнить массив из 10 элементов случайными числами в интервале [10,12] и найти длину самой длинной последовательности стоящих рядом одинаковых элементов. Пример: Исходный массив: Длина последовательности: 3

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

33 Поиск элемента, равного X 33 начало конец нет да нет да i <= N? i:= 1 A[i] = X? i:= i + 1 начать с 1-ого перейти к следующему Не нашли Есть! Как найти номер? ?

34 Поиск элемента в массиве 34 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 <= N then writeln('A[', i, ']=', X) else writeln('Не нашли...'); end. 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 <= N then writeln('A[', i, ']=', X) else writeln('Не нашли...'); end. (i X) do

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

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

37 Реверс массива 37 Задача: переставить элементы массива в обратном порядке. Алгоритм: поменять местами 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

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

39 Программа 39 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;

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

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

42 Циклический сдвиг 42 Задача: сдвинуть элементы массива влево на 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 ?

43 Программа 43 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;

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

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

46 Выбор нужных элементов 46 Задача – найти в массиве элементы, удовлетворяющие некоторому условию (например, отрицательные), и скопировать их в другой массив. Примитивное решение: 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 Что плохо? ?

47 Выбор нужных элементов 47 Решение: ввести счетчик найденных элементов 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

48 Как вывести массив B? 48 Примитивное решение: 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

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

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

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

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

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

54 Программа 54 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

55 Программа 55 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] уже поставлены

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

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

58 Метод пузырька с флажком 58 Идея – если при выполнении метода пузырька не было обменов, массив уже отсортирован и остальные проходы не нужны. Реализация: переменная-флаг, показывающая, был ли обмен; если она равна 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; Как улучшить? ?

59 Метод пузырька с флажком 59 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;

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

61 Метод выбора 61 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

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

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

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

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

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

67 «Быстрая сортировка» (Quick Sort) 67 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 <= R do begin while A[L] < X do L:= L + 1; while A[R] > X do R:= R - 1; if L <= R then begin c:= A[L]; A[L]:= A[R]; A[R]:= c; L:= L + 1; R:= R - 1; end; разделение обмен двигаемся дальше сортируем две части

68 «Быстрая сортировка» (Quick Sort) 68 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);... Сложность (в среднем) ! !

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

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