Задача Заполнить одномерный целочисленный массив, состоящий из 15 элементов, случайными числами (диапазон задайте сами). Вывести его на экран. Отсортировать. - презентация

1 Задача Заполнить одномерный целочисленный массив, состоящий из 15 элементов, случайными числами (диапазон задайте сами). Вывести его на экран. Отсортировать массив по возрастанию

2 Почему метод даёт отсортированный массив? Как долго работает алгоритм Сортировка "пузырьком" Если в воде находиться пузырёк с воздухом, то он постепенно поднимается наверх. Последовательно просматриваются все пары рядом стоящих элементов массива и, если они расположены в неправильном порядке, они меняются местами. Это правило действует до тех пор, пока все пары не будут стоять в правильном порядке (то есть, по возрастанию или убыванию).

3 ……. f: boolean; {Признак наличия неупорядоченных пар} c: integer; {Переменная для промежуточного хранения} repeat f:=false; {Пока неупорядоченных пар не было} for i:=1 to N-1 do {Просматриваем все пары рядом стоящих элементов} begin if a[i]>a[i+1] then {Если пара стоит в неправильном порядке} begin f:=true; {Есть неупорядоченная пара} c:=a[i]; a[i]:=a[i+1]; a[i+1]:=c; {Меняем местами элементы массива} end; until not f; {Ждём, пока не исчезнут все неупорядоченные пары}

4 Метод простого выбора Находится минимальный элемент массива и записывается в первую ячейку массива, содержимое которой записывается на место найденного минимального элемента. После чего находится минимальный элемент массива, начиная со второго элемента, он записывается во вторую ячейку массива, содержимое которой записывается на место найденного минимального элемента. Таким образом, постепенно выстраивается упорядоченный массив.

5 c: integer; {Переменная для промежуточного хранения} c2: integer; {Переменная для промежуточного хранения} for i:=1 to N-1 do begin {цикл по первому обрабатываемому элементу массива} c2:=i; {индекс предполагаемого минимального элемента} for j:=i+1 to N do {поиск минимального элемента} If a[c2]>a[j] then c2:=j; c:=a[i]; a[i]:=a[c2]; a[c2]:=c; {Меняем местами элемент массива} end;

6 Метод Шелла Недостаток метода сортировки "пузырьком" - работа с рядом стоящими элементами. В результате, элементы, которым надо "добраться" с одного конца массива до другого, делают это крайне долго. Метод Шелла аналогичен методу сортировки "пузырьком", однако работает с далеко отстоящими друг от друга элементами массива.

7 p: boolean; {флаг наличия перестановки} d:=N div 2; {Расстояние между обрабатываемыми элементами массива, на каждом этапе алгоритма уменьшается в 2 раза вплоть до 0, когда происходит останов алгоритма}

8 while d>0 do begin for j:=1 to N-d do {Перебор всех пар эл-в массива, расстояние м/у которыми равно d} begin l:=j {запоминаем индекс текущего элемента} repeat p:=false; {пока элементы не переставлялись} if a[l] < a[l+d] then begin {если порядок нарушен, то} c:=a[l];

9 a[l]:=a[l+d]; a[l+d]:=c; {меняем местами элементы массива} l:=l-d; { переходим к паре, в к-й меньший из переставленных эл-в} p:=true; {запомним, что была перестановка} end; until (l