Презентация, доклад по информатике на тему сортировка массива

для обучения программированию в старших классах и на первых курсах вузов, является базой для ряда других языков. Язык Паскаль был создан Никлаусом Виртом в 1968—1969 годах после его участия в работе комитета разработки стандарта языка Алгол-68. Язык назван в честь французского математика, физика, литератора и философа Блеза Паскаля, который создал первую в мире механическую машину, складывающую два числа.

Pascal

швейцарский учёный, специалист в области информатики, один из известнейших теоретиков в области разработки языков программирования, профессор компьютерных наук Швейцарской высшей технической школы Цюриха (ETHZ), лауреат премии Тьюринга 1984 года. Создатель и ведущий проектировщик языков программирования Паскаль, Модула-2, Оберон.

Никлаус Вирт

случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма. Задача сортировки в общем случае предполагает, что единственной обязательно наличествующей операцией для элементов является сравнение. Это делает невозможным реализацию алгоритма Хана, использующего арифметические действия. Рассмотрим схему алгоритма, когда единственным возможным действием над элементами является их сравнение.

Алгоритм сортировки

убыванию). Если не все элементы различны, то говорят о неубывающем (или невозрастающем) порядке.

"Даже если бы сортировка была почти бесполезна, нашлась бы масса
причин заняться ею! Изобретательные методы сортировки говорят о том,
что она и сама по себе интересна как объект исследования."
Д. Кнут

не отсортированной части поочередно выбираются и вставляются в отсортированную часть так, чтобы
не нарушить в ней упорядоченность элементов.
В начале работы алгоритма в качестве
отсортированной части массива принимают
только первый элемент, а в качестве не
отсортированной - все остальные элементы.

Сортировка методом вставки

из которых будет включать четыре действия:
взятие очередного i-го не отсортированного элемента и сохранение его в дополнительной переменной;
поиск позиции j в отсортированной части массива, в которой присутствие взятого элемента не нарушит упорядоченности элементов;
сдвиг элементов массива от i-го до j-1-го вправо, чтобы освободить найденную позицию вставки;
вставка взятого элемента в найденную i-ю позицию.

Алгоритм

for i:=1 to 6 do begin write ('a[' ,i, ']=');
readln (a[i]); end; for i:=2 to 6 do
begin
e:=A[i];
j:=1;
while (e>a[j]) do
Inc(j); for g:=i-1 downto j do
a[g+1]:=a[g];
a[j]:=e; end;
for i:=1 to 6 do write(a[i], ' ');
End.

Пример сортировки массива в порядке
возрастания (метод вставки).

1-го элемента до n-го (последнего) элемента и меняем его местами с первым элементом. На втором шаге находим элемент с минимальным значением на интервале от
2-го до n-го элемента и меняем его местами
со вторым элементом. И так далее
для всех элементов до
(n-1)-го.

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

begin
write ('a[' ,i, ']=');
readln (a[i]);
end;
for i:=1 to 6 do
begin
Min:=a[i];
MinI:=i;
for j:=i+1 to 6 do
if a[j] if a[j]a[MinI]:=a[i];
a[i]:=Min;
end;
for i:=1 to 6 do
write(a[i],' ');
End.

Пример сортировки массива в
порядке возрастания (метод выбора)

элементы постепенно
"всплывают" в начало массива, а более
тяжелые друг за другом опускаются на
дно (в конец массива).

Сортировка методом «пузырька»

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

Алгоритм

do
begin
write ('a[' ,i, ']=');
readln (a[i]);
end;
for i := 1 to 5 do
for j := 1 to 5 do
if a[j] > a[j+1] then begin
k := a[j];
a[j] := a[j+1];
a[j+1] := k
end;
for i := 1 to 6 do
write (a[i], ' ');
end.

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