Сортировка методом простого обмена (метод пузырька) Рекурсивная сортировка. - презентация

1 Сортировка методом простого обмена (метод пузырька) Рекурсивная сортировка

2 Сортировка простыми обменами, сортировка пузырьком Для понимания и реализации этот алгоритм простейший, но эффективен он лишь для небольших массивов. Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяется сортировка вставками. Пример сортировки пузырьком списка случайных чисел.

3 Принцип метода пузырька Весь массив просматривается несколько раз, причем при каждом просмотре сравниваются значения двух соседних элементов. Если эти значения следуют не в порядке возрастания, то производится их перестановка. Так происходит до тех пор, пока не будет сделано ни одной перестановки.

4 Пример процедуры сортировки, использующей метод пузырька Procedure Float (n:integer; var t:mass); Var i,j,h: integer; BEGIN For i:=2 to n do For j:=n downto i do If t[j]

5 Принцип метода простых обменов Весь массив просматривается несколько раз и при каждом просмотре ищется минимальный по значению элемент, который меняется местами с первым, вторым, третьим, …, предпоследним элементов массива и исключается из дальнейшего рассмотрения.

6 Пример процедуры сортировки, использующей метод простых обменов Procedure Obmen (n:integer; var t: mass); Var i, j, min, ind, h: integer; BEGIN For i:=1 to n-1 do Begin min:=t[i]; ind:=i; For j:=i+1 to n do If t[j] < min then Begin min:=t[j]; ind:=j; End; h:=t[i]; t[i]:=t[ind]; t[ind]:=h; End; END;

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

8 Процедура, упорядочивающая по возрастанию значения из массива Massiv в диапазоне индексов Left..Right Procedure QuickSort (Left, Right : integer; Var Massiv : Array1); Var i, j, x, y : integer; BEGIN i := Left; j := Right; x := Massiv[(Left+Right) div 2]; Repeat While Massiv[i] x do Dec(j); If i j; If Left

9 Решение задач Отсортировать массив по возрастанию, используя процедуру Swap, которая меняет местами 2 элемента. Составьте алгоритм, упорядочивающий элементы массива, стоящие на нечетных местах, в возрастающем порядке, а на четных - в убывающем. Дана вещественная матрица размером 7x4. Переставляя ее строки и столбцы, добиться того, чтобы наибольший элемент (один из них) оказался в левом верхнем углу. Дан упорядоченный целочисленный массив. Сформировать второй массив всех таких различных значений, которые в первом массиве встречаются по два и более раза.