Сортировка массива
презентация к уроку по информатике и икт (9 класс) на тему

Слайд 1

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

Слайд 2

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

Слайд 3

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

Слайд 4

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

Слайд 5

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

Слайд 6

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

Слайд 7

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

Слайд 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

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

Слайд 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 <= size do begin if arr [i-1] <= arr [i] then begin i := j; j := j + 1 end else begin t := arr [i-1]; arr [i-1] := arr [i]; arr [i] := t; i := i - 1; if i = 1 then begin i := j; j := j + 1 end end end; end ;

Слайд 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

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

Слайд 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;