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

• 1 слайд

  Выполнила ученица 9 «А» класса
  Агапова Алёна
  Учитель: Малеев С.И.
  Методы сортировки
  массива
  

• 2 слайд

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

• 3 слайд

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

• 4 слайд

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

• 5 слайд

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

• 6 слайд

  сортировка вставкой (включением);
  сортировка выбором (выделением);
  сортировка обменом («пузырьковая» сортировка).
  Методы сортировки массива
  

• 7 слайд

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

• 8 слайд

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

• 9 слайд

  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 (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.
  Пример сортировки массива в порядке
  возрастания (метод вставки).
  

• 10 слайд

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

• 11 слайд

  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] if a[j]<Min then begin Min:=a[j]; MinI:=j;end;
  a[MinI]:=a[i];
  a[i]:=Min;
  end;
  for i:=1 to 6 do
  write(a[i],' ');
  End.
  
  Пример сортировки массива в
  порядке возрастания (метод выбора)
  

• 12 слайд

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

• 13 слайд

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

• 14 слайд

  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.
  Пример сортировки массива в порядке возрастания (метод «пузырька»)
  

• 15 слайд

  Спасибо за внимание