Россия, Копейск
СДЕЛАЙТЕ СВОИ УРОКИ ЕЩЁ ЭФФЕКТИВНЕЕ, А ЖИЗНЬ СВОБОДНЕЕ
Благодаря готовым учебным материалам для работы в классе и дистанционно
Скидки до 50 % на комплекты
только до
Готовые ключевые этапы урока всегда будут у вас под рукой
Организационный момент
Проверка знаний
Объяснение материала
Закрепление изученного
Итоги урока
Был в сети 28.06.2022 20:08
Митрофанов Сергей Сергеевич
Учитель информатики и английского языка
37 лет
8 079
6 665 
Местоположение
Сортировка массива
Категория:
Информатика
19.04.2017 18:09
Просмотр содержимого документа
«Сортировка массива»
Методы сортировки массива
Определение
Сортировкой или упорядочением массива называется расположение его элементов по возрастанию (или убыванию). Если не все элементы различны, то говорят о неубывающем (или невозрастающем ) порядке.
Цитаты великих людей
"Даже если бы сортировка была почти бесполезна, нашлась бы масса причин заняться ею! Изобретательные методы сортировки говорят о том, что она и сама по себе интересна как объект исследования."
/Д. Кнут/
"Создается впечатление, что можно построить целый курс программирования, выбирая примеры только из задач сортировки."
/Н. Вирт/
Методы сортировки массива
- сортировка вставкой (включением);
2. сортировка выбором (выделением);
3. сортировка обменом ("пузырьковая" сортировка).
Сортировка выбором
Принцип метода:
Находим (выбираем) в массиве элемент с минимальным значением на интервале от 1-го элемента до n-го (последнего) элемента и меняем его местами с первым элементом. На втором шаге находим элемент с минимальным значением на интервале от 2-го до n-го элемента и меняем его местами со вторым элементом. И так далее для всех элементов до (n-1)-го.
![Отсортировать массив в порядке возрастания (метод выбора) var a:array [1..6] of integer; i,j,Min,MinI:integer; Begin for i:=1 to 6 do 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] a[MinI]:=a[i]; a[i]:=Min; end; for i:=1 to 6 do write(a[i],' '); End.](https://fsd.multiurok.ru/html/2017/04/19/s_58f77d7634613/img5.jpg)
Отсортировать массив в порядке возрастания (метод выбора)
var a:array [1..6] of integer; i,j,Min,MinI:integer;
Begin
for i:=1 to 6 do
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]
a[MinI]:=a[i];
a[i]:=Min;
end;
for i:=1 to 6 do
write(a[i],' ');
End.
Сортировка методом вставки
Принцип метода:
Массив разделяется на две части: отсортированную и не отсортированную. Элементы из не отсортированной части поочередно выбираются и вставляются в отсортированную часть так, чтобы не нарушить в ней упорядоченность элементов. В начале работы алгоритма в качестве отсортированной части массива принимают только первый элемент, а в качестве не отсортированной - все остальные элементы.
Алгоритм:
Алгоритм будет состоять из (n-1)-го прохода (n - размерность массива), каждый из которых будет включать четыре действия:
1) взятие очередного i-го не отсортированного элемента и сохранение его в дополнительной переменной;
2) поиск позиции j в отсортированной части массива, в которой присутствие взятого элемента не нарушит упорядоченности элементов;
3) сдвиг элементов массива от i-го до j-1-го вправо, чтобы освободить найденную позицию вставки;
4) вставка взятого элемента в найденную i-ю позицию.
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. " width="640"
Отсортировать массив в порядке возрастания (метод вставки).
Var i,j,e,g:integer; a:array [1..6] of integer;
Begin
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 (ea[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.
Сортировка методом «пузырька»
Принцип метода:
В сортировке методом пузырька по возрастанию более легкие (с меньшим значением) элементы постепенно "всплывают" в начало массива, а более тяжелые друг за другом опускаются на дно (в конец массива).
Алгоритм:
Элементы попарно сравниваются между собой: первый со вторым, затем второй с третьим, следом третий с четвертым и т.д. Если предшествующий элемент оказывается больше последующего, то их меняют местами. Постепенно самое большое число оказывается последним.
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. " width="640"
Отсортировать массив в порядке возрастания (метод «пузырька»)
var a: array[1..6] of integer;i,j,k: integer;
begin
for i:=1 to 6 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.
Вебинар для учителей
Свидетельство об участии БЕСПЛАТНО!
