Учитель информатики
Сайт учителя информатики. Технологические карты уроков, Подготовка к ОГЭ и ЕГЭ, полезный материал и многое другое.
Сколько проходов с перестановками элементов потребуется при сортировке массива из 100 чисел?
§ 21 Сортировка массива
2. Сколько проходов с перестановками элементов потребуется при сортировке массива из 100 чисел?
Ответ
В простом выборе — ровно 99, в пузырьке — от 1 до 99. В сортировке слиянием — log2(100) = 7 проходов, в сортировке подсчётом — 1 проход.
Считать проходы — мартышкин труд. В анализе алгоритмов определяют не кол-во проходов, а кол-во операций с данными.
ГДЗ по Информатика 9 класс Семакин, Залогова, Русакова § 21. Сортировка массива
1. Как пояснить название метода сортировки массива — «метод пузырька»?
2. Сколько проходов с перестановками элементов потребуется при сортировке массива из 100 чисел?
3. Введите в компьютер программу Premier_liga_2.
а) Выполните ее, получите результаты. Сравните с результатами, приведенными в параграфе.
б) Внесите изменения в программу для того, чтобы получить список в обратном порядке (по возрастанию очков). Выполните программу.
в) Возможно, что массив окажется отсортированным до завершения всех проходов. В таком случае число повторений внешнего цикла можно сократить, и программа будет выполняться быстрее. Попробуйте усовершенствовать приведенную программу с учетом этого факта. Проверьте результат на тестах.
4. Если несколько команд набрали одинаковое количество очков, то места между ними распределяются по разнице забитых и пропущенных мячей: чем разница больше, тем место выше. Попробуйте усовершенствовать программу, учитывая это правило. Для этого в программу надо добавить массив с разницами мячей. Придумайте тест, на котором можно проверить работу программы.
5. Условие то же, что и в предыдущем задании. Но в качестве исходных данных вводится еще два массива: с числом забитых и пропущенных мячей каждой командой.
1. По-видимому, самым простым методом сортировки является так называемый метод "пузырька". Чтобы уяснить его идею, представьте , что массив (таблица) расположен вертикально. Элементы с большим значением всплывают вверх наподобие больших пузырьков. При первом проходе вдоль массива, начиная проход "снизу", берется первый элемент и поочередно сравнивается с последующими. При этом:
если встречается более "легкий" (с меньшим значением) элемент, то они меняются местами;
при встрече с более "тяжелым" элементом, последний становится "эталоном" для сравнения, и все следующие сравниваются с ним .
В результате наибольший элемент оказывается в самом верху массива.
2. В простом выборе — ровно 99, в пузырьке — от 1 до 99. В сортировке слиянием — log2(100) = 7 проходов, в сортировке подсчётом — 1 проход.
Считать проходы — мартышкин труд. В анализе алгоритмов определяют не кол-во проходов, а кол-во операций с данными.
program teams;
var i, x, k, c: integer; a: string;
B: array [1..5] of integer;
Team: array [1..5] of string;
zabit: array [0..10] of integer;
propyshen: array [0..10] of integer;
f: array [0..10] of integer;
begin
writeln(' Введите название команды и количество полученной ею очков : ');
for i:=1 to 5 do
begin
write(i,') ');
read(Team[i]);
write(' Очки : ');
readln(B[i]);
write(' Количество забитых мячей : ');
readln(zabit[i]);
write(' Количество пропущенных мячей : ');
readln(propyshen[i]);
f[i]:=zabit[i]-propyshen[i];
writeln(' Забитые минус пропущенные : ',f[i]);
end;
for k:=1 to 5 do
for i:=1 to 5-k do
begin
if (B[i]<=B[i+1]) and (f[i]<=f[i+1]) then
begin
x:=B[i];
B[i]:=B[i+1];
B[i+1]:=x;
a:=Team[i];
Team[i]:=Team[i+1];
Team[i+1]:=a;
c:=f[i];
f[i]:=f[i+1];
f[i+1]:=c;
end;
end;
writeln(' Вывод : ');
for i:=1 to 5 do
begin
for k:=1 to 18-length(Team[i]) do
Team[i]:=Team[i]+' ';
writeln(i,') ',Team[i]:18,B[i]:2,' ','- Разница в забитых и пропущенных голах :',
f[i]);
end;
end.
В конце будет выводить номер команды, название команды, количество очков и разницу между забитыми и пропущенными голами.
4. Program Premier_liga_2;
Var B: array [1..16] of integer;
BallDiff: array [1..16] of integer;
Team: array [1..16] of string;
I, K, X, Z, P: integer;
St: string;
BEGIN
writeln (' Введите названия команд и полученные ими очки ');
for I:=1 to 16 do begin
write (I, ' — Название : '); Readln(Team[I]);
write (' Очки : '); Readln(B[I]);
write (' Забитые мячи : '); Readln(Z);
write (' Пропущенные мячи : '); Readln(P);
BallDiff[I]:=Z — P;
writeln('———-')
end;
for K:=1 to 15 do
for I:=1 to 16-K do
if (B[I] < B[I+1]) or ((B[I] = B[I+1]) and (BallDiff[I] < BallDiff[I+1])) then
begin
X:=B[I]; B[I]:=B[I+1]; B[I+1]:=X;
St:=Team[I]; Team[I]:=Team[I+1];
Team[I+1]:=St;
X:=BallDiff[I]; BallDiff[I]:=BallDiff[I+1]; BallDiff[I+1]:=X;
end;
for I:=1 to 16 do
begin
for K:=1 to 18-length(Team[I]) do
Team[I]:=Team[I]+' ';
writeln(I:2, ' ', Team[I]:18, B[I]:2, ' Разница мячей : ', BallDiff[I]:2)
end;
END.
Уроки 58 — 61
Сортировка массива
(§ 21. Сортировка массива)
Составление программы на Паскале сортировки массива
Тест по теме «Программное управление работой компьютера»
Теперь запишем программу на Паскале. Но мы ее немного усложним по сравнению с построенным алгоритмом. По условию исходной задачи нам нужно получить список команд в порядке занятых ими мест и число очков, полученных каждой командой. Следовательно, сортировать нужно не только массив В, но и массив Team. Делается это очень просто: в массиве Team параллельно с массивом В производятся те же самые перестановки. В конце работы программы на экран выводятся одновременно элементы обоих отсортированных массивов.
Поясним новые средства Паскаля, которые применены в этой программе. Обмен значениями между элементами строкового массива Team должен происходить через переменную строкового типа. Для этого в программе используется переменная St.
Вывод результатов на экран организован так, чтобы на экране номера мест, занятых командами, названия команд и набранные очки выводились в три ровных столбца. Названия разных команд имеют разную длину. Самое длинное название у команды ТОРПЕДО-МЕТАЛЛУРГ состоит из 17 символов. Для выравнивания длин строк каждое название дополняется пробелами до 18 символов. Число добавляемых пробелов вычисляется так:
Здесь length ( ) — это стандартная функция, вычисляющая длину строки (число символов), указанной в скобках. Например, для ЦСКА длина строки равна 4, а для ТОРПЕДО-МЕТАЛЛУРГ длина равна 17. Значит, к ЦСКА добавится 14 пробелов, а к ТОРПЕДО-МЕТАЛЛУРГ — 1 пробел.
В операторе Team [I] : = Team [I] + ‘ ‘; используется операция «+» присоединения символов. В данном случае присоединяется пробел. К строке Team [l] добавится столько пробелов, сколько раз повторится присоединение. После этого по команде
Writeln(1:2,’ ‘,Team[I]:18, B[I]:2)
в ровные колонки выведутся места, названия команд и очки. Результаты будут иметь на экране следующий вид:
Демонстрации к уроку
Коротко о главном
Метод пузырька — алгоритм сортировки числового массива.
Структура алгоритма метода пузырька — два вложенных цикла с переменной длиной внутреннего цикла.
length() — функция определения длины строковой переменной.
В Паскале существует операция присоединения строк. Ее знак — «+».
Вопросы и задания
1. Как пояснить название метода сортировки массива — «метод пузырька»?
2. Сколько проходов с перестановками элементов потребуется при сортировке массива из 100 чисел?
3. Введите в компьютер программу Premier_liga_2.
а) Выполните ее, получите результаты. Сравните с результатами, приведенными в параграфе.
б) Внесите изменения в программу для того, чтобы получить список в обратном порядке (по возрастанию очков). Выполните программу.
в) Возможно, что массив окажется отсортированным до завершения всех проходов. В таком случае число повторений внешнего цикла можно сократить, и программа будет выполняться быстрее. Попробуйте усовершенствовать приведенную программу с учетом этого факта. Проверьте результат на тестах.
4. Если несколько команд набрали одинаковое количество очков, то места между ними распределяются по разнице забитых и пропущенных мячей: чем разница больше, тем место выше. Попробуйте усовершенствовать программу, учитывая это правило. Для этого в программу надо добавить массив с разницами мячей. Придумайте тест, на котором можно проверить работу программы.
5. Условие то же, что и в предыдущем задании. Но в качестве исходных данных вводится еще два массива: с числом забитых и пропущенных мячей каждой командой.
Следующая страница 
Компьютерный практикум ЦОР. Сортировка массива (Задание 1 — 4)