Обменная сортировка методом «пузырька»

Свое название этот алгоритм получил из-за схожести с физическим явлением всплытия пузырька воздуха в воде. Точно также в массиве как бы «всплывают» наверх (к началу массива) меньшие элементы.

Сначала мы сравниваем последний и предпоследний элементы массива. Если они стоят неправильно (нижний элемент меньше верхнего), то меняем их местами. Далее сравниваем следующую пару элементов и т. д.

В итоге самый «легкий» элемент поднимается на самый верх.

Теперь спускаемся вниз и начинаем аналогичные сравнения, но при этом остановимся на втором сверху элементе, потому что, как мы уже выяснили, верхний — наименьший.

На каждом проходе число сравнений будет уменьшаться на 1. Число проходов будет на единицу меньше числа элементов в массиве, ведь в самом конце последний элемент уже окажется наибольшим и сравнивать его смысла нет.

Сортировка выбором

Еще один простой метод сортировки — метод выбора. Его идея заключается в том, что на каждом этапе среди неотсортированных элементов выбирается минимальный и меняется местами с первым среди неотсортированных:

Рассмотренные алгоритмы сортировки являются достаточно простыми для понимания и запоминания, но на практике применяются редко. Дело в том, что они обладают квадратичной сложностью, т. е. в общем случае число сравнений и обменов сопоставимо с n², где n — число элементов в массиве.

С примером более эффективного алгоритма сортировки — «быстрой сортировкой» — вы сможете познакомиться в дополнительном материале.

 

Задания к параграфу:

1. Что такое индекс в одномерном массиве?

А. порядковый номер элемента массива

Б. наибольший номер элемента массива

В. размерность массива

Г. имя массива

2. Какие описания массивов записаны верно, а какие — нет?

А. a: array [1..10] real

Б. вa: array [10..1] of byte

В. a: array [1..10] of integer

Г. a: array [1..10] of real and integer

Д. a: aray [1..10] of integer

Е. a: array [10..10] of real

Верно:

Не верно:

3. Значения двух массивов A[1..100] и B[1..100] задаются с помощью следующего фрагмента программы:

for n:=1 to 100 do

A[n]:= n – 10;

for n:=1 to 100 do

B[n]:= A[n]*n;

Сколько элементов массива B будут иметь положительные значения?

Ответ:

4. Расставьте строки программы в правильном порядке.

А. for i:=1 to n do

Б. end

В. i,n:integer

Г. var a:array[1..100] of integer

Д. begin

Е. readln(a[i])

Ж. end

З. begin

И. for i:=1 to n do

К. write(‘a[’,i,’]=’)

Л. readln(n)

М. write(a[i],’ ‘)

1	2	3	4	5	6	7	8	9	10	11	12

 

5. В массиве Dat хранятся данные измерений среднесуточной температуры за 10 дней в градусах (Dat[1] — данные за первый день, Dat[2] — за второй и т. д.). Определите, какое число будет напечатано в результате работы следующей программы.

Var k, m: integer;

Dat: array[1..10] of integer;

Begin

Dat[1]:= 2; Dat[2]:= 5;

Dat[3]:= 7; Dat[4]:= 5;

Dat[5]:= 4; Dat[6]:= 2;

Dat[7]:= 0; Dat[8]:= 2;

Dat[9]:= 4; Dat[10]:= 5;

m:= 0;

for k:= 1 to 10 do

if Dat[k] > 3 then m:= m+1;

Writeln(m);

End.

Ответ:

6. В программе описан одномерный целочисленный массив с индексами от 0 до n. Известно, что в массиве есть несколько элементов с максимальным значением. Дан фрагмент программы:

j:=0;

for i:=1 to n do

if A[i] > A[j] then j:= i;

s:=j;

Чему будет равно значение переменной s после выполнения этого фрагмента программы?

А. значению максимального элемента

Б. количеству элементов в массиве A, имеющих максимальное значение

В. индексу первого элемента в массиве A, имеющего максимальное значение

Г. индексу последнего элемента в массиве A, имеющего максимальное значение

7. В программе описан одномерный целочисленный массив с индексами от 1 до 10, элементы которого вычисляются по формуле:

A[i]=2k – 1, k=1, …10.

Ниже представлен фрагмент программы, обрабатывающей данный массив:

n:= 10;

for i:= 1 to n do begin

A[n+1–i]:= 2*A[i];

end;

Какие (одно или несколько) из представленных ниже чисел будут встречаться в массиве после выполнения программы два и более раз?

2, 4, 8, 16, 32, 64, 128, 256

Ответ: