КАЗАНСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСТИТЕ
ЦЕНТР ОЛИМПИАДНОЙ ПОДГОТОВКИ
Хадиев Р.М.
Сортировки
Казань – 2018 г.
Оглавление
1. Генерация последовательности. 3
2. Работа с экстремумами. 4
3. Сортировка. 7
3.1. Упорядочить последовательность в порядке возрастания. 7
3.2. Сортировка «пузырком». 8
3.3. Сортировка по счетчику. 9
3.4. Сортировка по ключу. 10
3.5. Сортировка слиянием.. 11
3.6. Разрядная сортировка. 12
3.7. Сортировка подсчетом.. 14
3.8. Использование сортировки. 15
АСМР. №340 коробки. 15
АСМР. №41 Сортировка подсчетом.. 15
Генерация последовательности
Const N=10;
var k,i,res:integer;
a: array [1..N] of integer;
begin
for i:=1 to n do read (a[i]);
write('A=(');
for i:=1 to n do write (' ',a[i]*a[i]);
writeln(')')
end.
Для облегчения отладки программы последовательность можно генерировать с помощью датчика случайных чисел
Const N=10;
var k,i,res:integer;
a: array [1..N] of integer;
begin
for i:=1 to n do a[i]:=random(10);
write('A=(');
for i:=1 to n do write (' ',a[i]);
writeln(')')
end.
Const N=10;
var k,i,res:integer;
a: array [1..N] of integer;
begin
write('A=(');
for i:=1 to n do
begin
a[i]:=random(10);
write (' ',a[i])
end;
writeln(')');
end.
Работа с экстремумами
1) Найти максимальное значение в заданной последовательности.
Const N=10;
var k,i,max:integer;
a: array [1..N] of integer;
begin
write('A=(');
for i:=1 to n do
begin
a[i]:=random(10);
write (' ',a[i])
end;
writeln(')');
max:=a[1]; // без альтернативный кандидат на решение
for i:=2 to n do
if max<a[i] then
max:=a[i];
writeln('max=',max)
end.
2) Найти число максимальных значений в заданной последовательности.
| Const N=10; var c,k,i,max:integer; a: array [1..N] of integer; begin write('A=('); for i:=1 to n do begin a[i]:=random(6); write (' ',a[i]) end; writeln(')'); max:=a[1]; for i:=2 to n do if a[i]>max then max:=a[i]; c:=0; for i:=1 to n do c+=ord(a[i]=max); writeln('max=',max); writeln('kol-vo max chisel=',c) end. | Const N=10; var c,k,i,max:integer; a: array [1..N] of integer; begin write('A=('); for i:=1 to n do begin a[i]:=random(6); write (' ',a[i]) end; writeln(')'); max:=a[1]; c:=1; for i:=2 to n do if a[i]>max then begin max:=a[i]; c:=1 end else c+= ord(a[i]=max); write('max=',max,#13, 'kol-vo max chisel=',c) end. |
3) Найти номера элементов с максимальным значением в заданной последовательности.
Const N=10;
var p,c,k,i,max:integer;
a: array [1..N] of integer;
begin
write('A=(');
for i:=1 to n do
begin
a[i]:=random(6);
write (' ',a[i])
end;
writeln(')');
max:=a[1];
for i:=2 to n do
if a[i]>max then
max:=a[i];
writeln('max=',max);
c:=0;
for i:=1 to n do
if a[i]=max then
c:=c+1;
writeln('kol-vo max chisel=',c);
write('pozicii max elementov=');
for i:=1 to n do
if a[i]=max then
write(' ',i);
end.
4) Записать 3 максимальных элемента в конец последовательности элементов с максимальным значением в заданной последовательности.
Const N=10;
var p,c,k,i,max,nmax:integer;
a: array [1..N] of integer;
procedure print;
var i:integer;
begin
write('A=(');
for i:=1 to n do
write (' ',a[i]);
writeln(')');
end;
begin
for i:=1 to n do
a[i]:=random(6);
print;
max:=a[1];nmax:=1;
for i:=2 to n do
if a[i]>max then
begin
max:=a[i];
nmax:=i
end;
writeln('max=',max,' nommax=',nmax);
p:=a[n];a[n]:=a[nmax];a[nmax]:=p;
print;
max:=a[1];nmax:=1;
for i:=2 to n-1 do
if a[i]>max then
begin
max:=a[i];
nmax:=i
end;
writeln('max=',max,' nommax=',nmax);
p:=a[n-1];a[n-1]:=a[nmax];a[nmax]:=p;
print;
max:=a[1];nmax:=1;
for i:=2 to n-2 do
if a[i]>max then
begin
max:=a[i];
nmax:=i
end;
writeln('max=',max,' nommax=',nmax);
p:=a[n-2];a[n-2]:=a[nmax];a[nmax]:=p;
print;
end.
Сортировка
Упорядочить последовательность в порядке возрастания.
Const N=10;
var p,c,k,i,max,nmax,j:integer;
a: array [1..N] of integer;
procedure print;
var i:integer;
begin
write('A=(');
for i:=1 to n do
if i>=j then write ('_',a[i])
else write (' ',a[i]);
writeln(')');
end;
begin
for i:=1 to n do
a[i]:=random(6);
print;
for j:=n downto 2 do
begin
max:=a[1];nmax:=1;
for i:=2 to j do
if a[i]>max then
begin
max:=a[i];
nmax:=i
end;
writeln('max=',max,' nommax=',nmax);
p:=a[j];a[j]:=a[nmax];a[nmax]:=p;
end;
end.
Сортировка «вставкой»
Const N=10;
var p,c,k,i,max,nmax,j:integer;
a: array [1..N] of integer;
procedure print;
var i:integer;
begin
write('A=(');
for i:=1 to j do
write ('_',a[i]);
writeln(')');
end;
begin
j:=1
a[1]:=random(6);
print;
for j:=2 to т do begin
r:=random(1);
i:=j-1;
while a[i]>r and j>0 do begin
a[i+1]:=a[i];
i-=1
end;
a[i]:=r;
end;
end.
Сортировка «пузырком»
Const N=10;
var p,c,k,i,max,nmax,j:integer;
a: array [1..N] of integer;
procedure print;
var i:integer;
begin
write('A=(');
for i:=1 to n do
if i>=j then
write ('_',a[i])
else
write (' ',a[i]);
writeln(')');
end;
begin
for i:=1 to n do
a[i]:=random(6);
print;
for j:=n downto 2 do begin
for i:=2 to j do
if a[i]<a[i-1] then begin
p:=a[i];a[i]:=a[i-1];a[i-1]:=p;
end;
end;
end.
Сортировка по счетчику
Задана последовательность целых чисел с абсолютным значением меньше 100. Упорядочить в порядке возрастания.
var
i,j,n:integer;
a:array[-100..100] of int64;
begin
read(n);
for i:=1 to n do
begin
read(j);
inc(a[j])
end;
for i:=-100 to 100 do
for j:=1 to a[i] do
write(i:8)
end.
Сортировка по ключу
Задана последовательность n (n< 1000000) вещественных чисел из интервала (0,100). Упорядочить в порядке возрастания целых частей.
Var
A,b:array[0..1000000] of real;
R,kl: array[0..99] of integer;
i,j,n:integer;
Begin
For i:=0 to 9 do r[i]:=0;
Read(n);
For i:=1 to n do
Begin
Read(a[i]);
R[trunc(a[i])]+=1
End.
Kl[0]:=1;
For i:=1 to 99 do kl[i]:=kl[i-1]+r[i-1];
For i:=1 to n do
Begin
B[kl[trunc(a[i])]]:=a[i];
Kl[trunc(a[i])]+=1
End;
For i:=1 to n do write(b[i],’ ‘)
End.
Сортировка слиянием
Заданы 2 упорядоченные последовательности. Объединить в одну упорядоченную последовательность.
Var a,b:array[1..100] of integer;
C:array[1..200] of integer;
ia,ib,ic:integer;
Begin
// формируется случайная возрастающая последовательность А
A[1]:=random(3);
For i:=2 to 10 do a[i]:=a[i-1] + random(3);
// формируется случайная возрастающая последовательность B
B[1]:=random(3);
For i:=2 to 10 do b[i]:=b[i-1] + random(3);
// объединение
For ic:=1 to 200 do
If ia>100 then Begin // А переписано в С и дописывается В
C[ic]:=b[ib];
ib+=1
End
Else
If ib>100 then Begin // B переписано в С и дописывается A
C[ic]:=a[ia];
ia+=1
End
Else // эелементы в А и В еще есть
If a[ia]>b[ib] then Begin // переписывается элемент из В
C[ic]:=b[ib];
ib+=1
End
Else begin
C[ic]:=a[ia];
ia+=1
End;
// вывод результата
For ic:=1 to 200 do Write(c[ic],’ ‘)
End.
Разрядная сортировка
Задана случайная последовательность
А: 12 4 54 3 1 0 432 59 1024 2421 16 642 392 82 1000
| К: | R: | |||
| 0 1000 | ||||
| 1 2421 | ||||
| 12432 642 392 82 | ||||
| 4 54 1024 | ||||
| 16 | ||||
| 59 |
А: 0 1000 1 2421 12 432 642 392 82 3 16 59
| К: | R: | |||
| 00 1000 01 03 | ||||
| 12 16 | ||||
| 2421 | ||||
| 432 | ||||
| 642 | ||||
| 59 | ||||
| 82 | ||||
| 392 |
А: 0 1000 1 3 12 16 2421 432 642 59 82 392
| К: | R: | |||
| 000 1000 001 003 012 016 059 082 | ||||
| 392 | ||||
| 2421 432 | ||||
| 642 | ||||
А: 0 1000 1 3 12 16 59 82 392 2421 432 642
| К: | R: | |||
| 0000 0003 0012 0016 0059 0082 0392 0432 0642 | ||||
| 1000 | ||||
| 2421 | ||||
A: 0 3 12 16 59 82 392 432 642 1000 2421
Программа:
Var
St,n,i,j,m,q:integer;
a:array]1..10000] of word;
k:array[0..9] of integer;
r:array[0..9,1..10000] of integer;
begin
read(n);
for i:=1 to n do read(a[i];
st:=1;
for q:=1 to 5 do // число значащих разрядов 5
begin
for i:=0 to 9 do k[i]:=0;
for i:=1 to n do begin
m:=a[i] div st mod 10;
k[m]+=1;
r[k[m]]:=a[i];
end;
m:=1;
for i:=0 to 9 do
for j:=1 to k[i] do begin
a[m]:=r[i,j];
m+=1
end;
st*=10
end;
end.
Сортировка подсчетом
Задана последовательность не повторяющихся N чисел. Упорядочить в порядке возрастания.
Для данного числа его позиция определятся числом элементов меньше данного
Var i,j,k,n:integer;
X,y:array[1..10000] of integer;
Begin
Read(n)
For i:=1 to n do begin
K:=1;
For j:=1 to n do
If x[i]>x[j] then k+=1
Y[k]:=x[i]
End;
For i:= to n do write(y[i],’ ‘)
End.
End.
Использование сортировки
АСМР. №340 коробки
На столе лежат 2 коробки размера A1 × B1 × C1 и A2 × B2 × C2. Выяснить можно ли одну из этих коробок положить в другую, если разрешены повороты коробок вокруг любого ребра на угол 90 градусов.
Если коробки одинаковы, вывести "Boxes are equal". Если первая коробка может быть положена во вторую, вывести "The first box is smaller than the second one". Если вторая коробка может быть положена в первую, вывести "The first box is larger than the second one". Иначе, "Boxes are incomparable".
Решение:
#include <bits/stdc++.h>
#define f for(i=0;i<3;i++)
#define s(a) sort(a,a+3);
using namespace std;
main()
{
int a[3],b[3],c=0,v=0,i;
f cin>>a[i];
f cin>>b[i];
sort(a,a+3);
sort(b,b+3);
f {
c+=a[i]==b[i];
v+=a[i]>b[i];
}
cout<<(c>2? "Boxes are equal":
v>0&c+v>2? "The first box is larger than the second one":
v<1? "The first box is smaller than the second one":
"Boxes are incomparable");
}