Презентация на тему "Сортировка массива" 9 класс

Содержание

• 
  Слайд 1

  Вопросы

  Что такое массив? Что такое индекс элемента массива? Какие действия можно производить с массивами?

• 
  Слайд 2

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

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

• 
  Слайд 3

  Сортировка -

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

• 
  Слайд 4

  История

  Первые прототипы современных методов сортировки появились уже в XIX веке. К 1890 году для ускорения обработки данных переписи населения в США американец Герман Холлерит создал первый статистический табулятор — электромеханическую машину, предназначенную для автоматической обработки информации, записанной на перфокартах[1]. У машины Холлерита имелся специальный «сортировальный ящик» из 26 внутренних отделений. В дальнейшем история алгоритмов оказалась связана с развитием электронно-вычислительных машин. По некоторым источникам, именно программа сортировки стала первой программой для вычислительных машин.

• 
  Слайд 5

  Оценка алгоритма сортировки

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

• 
  Слайд 6

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

  Сортировка пузырьком Сортировка вставками Гномья сортировка Быстрая сортировка Сортировка Шелла

• 
  Слайд 7

  Сортировка простыми обменами илисортиро́вкапузырько́м

  (англ. bubblesort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяются более эффективные алгоритмы сортировки. В то же время метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как шейкерная сортировка, пирамидальная сортировка и быстрая сортировка.

• 
  Слайд 8
  

  for i := 1 to m-1 do for j := 1 to m-i do if arr[j] > arr[j+1] then begin k := arr[j]; arr[j] := arr[j+1]; arr[j+1] := k end;

• 
  Слайд 9

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

  (англ. Insertionsort) — алгоритм сортировки, в котором элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов

• 
  Слайд 10
  

  begin for i:=2 to N do begin buf:=x[i]; j:=i-1; while (j>=1) and (x[j]>buf) do begin x[j+1]:=x[j]; j:=j-1; end; x[j+1]:=buf; end; end;

• 
  Слайд 11

  Гномья сортировка

  Алгоритм сортировки, похожий на сортировку вставками, но в отличие от последней перед вставкой на нужное место происходит серия обменов, как в сортировке пузырьком. Название происходит от предполагаемого поведения садовых гномов при сортировке линии садовых горшков. « Гномьясортировка основана на технике, используемой обычным голландским садовым гномом (нидерл. tuinkabouter). Это метод, которым садовый гном сортирует линию цветочных горшков. По существу он смотрит на текущий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд; если нет следующего горшка, он закончил.» Дик Грун

• 
  Слайд 12
  

  begin i := 2; j := 3; while i

• 
  Слайд 13

  Быстрая сортировка

  Быстрая сортировка, сортировка Хоара (англ. quicksort), часто называемая qsort (по имени в стандартной библиотеке языка Си) — широко известный алгоритм сортировки, разработанный английским информатикомЧарльзом Хоаром во время его работы в МГУ в 1960 году. Общая идея алгоритма состоит в следующем: Выбрать из массива элемент, называемый опорным. Это может быть любой из элементов массива или же число, вычисленное на основе значений элементов. Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка, следующие друг за другом: «меньшие опорного», «равные» и «большие».[1] Для отрезков «меньших» и «больших» значений выполнить рекурсивно ту же последовательность операций, если длина отрезка больше единицы.

• 
  Слайд 14
  

  begin i:=l; j:=r; m:=round ((l+r)/2);{средний элемент} x1:=x[m]; repeat while x[i]>x1 do inc(i);{пока левый больше среднего, подвигоем левый край вправо } while x[j]j;{конец одной перестановки} if l

• 
  Слайд 15

  Сортировка Шелла

  (англ. Shellsort) — алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Дональда Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга; иными словами — это сортировка вставками, но с предварительными «грубыми» проходами.

• 
  Слайд 16
  

  procedure ShellSort( var A : mas ); const steps = 12; var i, j, l, k, p, n : Integer; x : itp; s : array [1..steps] of Integer; begin k := 1; { Формируем последовательность чисел - шаги, с которыми выбираем сортируемые подмассивы } for i := steps downto 1 do begin s[i] := k; k := k * 2 + 1; end;