Сортировка массива
презентация к уроку по информатике и икт (9 класс) на тему
Презентация по теме: "Сортировка массивов". В презентации расссмотрены определение сортировки, краткая история развития, несколько способов сорттировки, в частности следующие алгоритмы
Скачать:
Вложение | Размер |
---|---|
![]() | 1.73 МБ |
Предварительный просмотр:
Подписи к слайдам:
Сортировка массива Алгоритмы сортировки
Сортировка - ( англ. sorting — классификация , упорядочение ) — последовательное расположение или разбиение на группы чего-либо в зависимости от выбранного критерия . Алгоритм сортировки — это алгоритм для упорядочивания элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.
История Первые прототипы современных методов сортировки появились уже в XIX веке. К 1890 году для ускорения обработки данных переписи населения в США американец Герман Холлерит создал первый статистический табулятор — электромеханическую машину, предназначенную для автоматической обработки информации, записанной на перфокартах [1] . У машины Холлерита имелся специальный «сортировальный ящик» из 26 внутренних отделений . В дальнейшем история алгоритмов оказалась связана с развитием электронно-вычислительных машин . По некоторым источникам, именно программа сортировки стала первой программой для вычислительных машин.
Оценка алгоритма сортировки Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью . Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных.
Алгоритмы сортировки Сортировка пузырьком Сортировка вставками Гномья сортировка Быстрая сортировка Сортировка Шелла
Сортировка простыми обменами или сортиро́вка пузырько́м ( англ. bubble sort ) — простой алгоритм сортировки . Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяются более эффективные алгоритмы сортировки. В то же время метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как шейкерная сортировка , пирамидальная сортировка и быстрая сортировка .
Сортировка простыми обменами или сортиро́вка пузырько́м 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 ;
Сортировка вставками ( англ. Insertion sort ) — алгоритм сортировки , в котором элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов
Сортировка вставками 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;
Гномья сортировка Алгоритм сортировки, похожий на сортировку вставками, но в отличие от последней перед вставкой на нужное место происходит серия обменов, как в сортировке пузырьком. Название происходит от предполагаемого поведения садовых гномов при сортировке линии садовых горшков. « Гномья сортировка основана на технике, используемой обычным голландским садовым гномом ( нидерл . tuinkabouter ). Это метод, которым садовый гном сортирует линию цветочных горшков. По существу он смотрит на текущий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд; если нет следующего горшка, он закончил .» Дик Грун
Гномья сортировка 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 ;
Быстрая сортировка Быстрая сортировка , сортировка Хоара ( англ. quicksort ), часто называемая qsort (по имени в стандартной библиотеке языка Си ) — широко известный алгоритм сортировки , разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году . Общая идея алгоритма состоит в следующем: Выбрать из массива элемент, называемый опорным. Это может быть любой из элементов массива или же число, вычисленное на основе значений элементов. Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка, следующие друг за другом: «меньшие опорного», «равные» и «большие». [1] Для отрезков «меньших» и «больших» значений выполнить рекурсивно ту же последовательность операций, если длина отрезка больше единицы.
begin i:=l; j:=r; m:=round (( l+r )/2); { средний элемент} x1:=x[m]; repeat while x[i]>x1 do inc (i); { пока левый больше среднего, подвигоем левый край вправо } while x[j] Сортировка Шелла ( англ. Shell sort ) — алгоритм сортировки , являющийся усовершенствованным вариантом сортировки вставками . Идея метода Дональда Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга; иными словами — это сортировка вставками, но с предварительными «грубыми» проходами. Сортировка Шелла 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;
По теме: методические разработки, презентации и конспекты
Сортировка массивов
Конспект урока по теме "Сортировка массивов"...
![](/sites/default/files/pictures/2013/06/26/picture-270255-1372190548.jpg)
Одномерные массива. Сортировка методом прямого выбора.
Рассматривается данный алгоритм и обсуждается вопрос оценки сложности данного алгоритма....
Сортировка массива. Метод пузырька.
Презентация к учебнику "Информатика 10 класс" авторы Поляков К.Ю., Еремин Е.А. Глава 8 "Алгоритмизация и программирование", §64 "Сортировка".Демонстрация презентации дает наглядное представление выпол...
![](/sites/default/files/pictures/2016/11/03/picture-842710-1478191539.jpg)
Сортировки массивов.
Три сортировка массивов на языке программирования Паскаль, задачи на сортировки...
Сортировка массивов.
Описаны алгоритмы сортировки, приведены примеры подпрограмм на Паскале....
![](/sites/default/files/pictures/2020/04/06/picture-386619-1586154221.jpg)
Дистанционный урок информатики в 9 классе по теме "Решение задач на сортировку массива"
Данная разработка может быть использована для проведения дистанционного урока информатики....