Тема: «Сортировка элементов одномерного массива» Автор: Андрюшина А.В. Школа 616 г. Зеленоград 2009 г. - презентация

1 Тема: «Сортировка элементов одномерного массива» Автор: Андрюшина А.В. Школа 616 г. Зеленоград 2009 г.

2 Ряд однотипных данных, имеющих имя, порядковый номер и численное значение называются массивами А Понятие массива

3 Пример: Сформировать одномерный массив из 9 элементов и распечатать его.

4 Сортировка элементов в массиве Сортировка представляет собой процесс упорядочения элементов в массиве по возрастанию или убыванию их значений. Например: Массив Х из n элементов будет отсортирован в порядке возрастания значений его элементов, если X[1] = X [n]

5 Способы сортировки массива: Сортировка «перестановкой»«перестановкой Сортировка «вставкой»вставкой Сортировка «выбором»выборомСортировка «пузырька»пузырька Быстрая сортировкасортировка

6 Сортировка массива методом «пузырька» Сортировка методом пузырька использует метод обменной сортировки и основана на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов.

7 Принцип сортировки массива по возрастанию методом «пузырька» Сравним первый элемент массива со вторым. Если первый окажется больше второго, то поменяем их местами. Те же действия выполним для второго и третьего, третьего и четвёртого, I-го и (I + 1)-го, (n – 1)-го и n-го элементов. В результате этих действий самый большой элемент станет на последнее (n-е) место. Теперь повторим данный алгоритм сначала, но последний (n-й) элемент, рассматривать не будем, так как он уже занял своё место. После проведения данной операции самый большой элемент оставшегося массива встанет на (n - 1) место. Так повторяем до тех пор, пока не упорядочим весь массив.

8 Сортировка массива А состоящего из 5 элементов, по возрастанию методом «пузырька» Номер элемента Исходный массив Первый просмотр Второй просмотр Третий просмотр Четвертый просмотр Таблица сортировки массива по возрастанию

9 Блок-схема сортировки массива методом «пузырька» j:=1 i:=1 a[i]>a[i+1] Pr:=a[i+1]; A[i+1]=a[i]; A[i]:=pr; да j:=j+1 да нет j < n i:=i+1 i< n-j да j=j+1j=n-1 да нет

10 Сформировать массив из n элементов и упорядочить элементы в массиве по возрастанию их значений (метод «пузырька»)

11 Сортировка массива методом «перестановки»

12 Таблица сортировки массива по убыванию методом «перестановки» перестановки элеме нтов Значения элементов массива ПерваяВтораяТретьяЧетвертая Если n элементов, то количество перестановок n 2

13 Таблица сортировка массива по возрастанию методом «перестановки» перестановки элеме нтов Значения элементов массива ПерваяВтораяТретьяЧетвертая Если n элементов, то количество перестановок n 2

14 Блок-схема сортировки массива методом «перестановки» i:=1 J:=i+1 a[i]>a[j] Pr:=a[j] A[j:]=a[i] A[i]:=pr да j:=j+1 да нет j < n i:=i+1 i< n-1 да

15 Сформировать массив А размерностью 10. Задать значения элементов массива с помощью ГСЧ. Расположить элементы массива по возрастанию (метод перестановки).

16 Сформировать массив А размерностью 10. Задать значения элементов массива с помощью ГСЧ. Расположить элементы массива по убыванию (метод перестановки).

17 Сортировка массива методом «вставки» Сначала упорядочиваются два элемента массива. Затем делается вставка третьего элемента в соответствующее место по отношению к первым двум. Четвёртый элемент помещают в список из уже упорядоченных трёх элементов. Этот процесс повторяется до тех пор, пока все элементы не будут упорядочены.

18 ПРИМЕР : Дан массив из восьми элементов. Первые шесть уже упорядочены, а седьмой нужно вставить между вторым и четвёртым. Сохраним его во вспомогательной переменной Х. Пятый элемент переместим на место шестого, четвёртый – на место пятого, а третий на место четвёртого. То есть выполнили сдвиг элементов массива на одну позицию вправо. Запишем содержимое вспомогательной переменной в третью позицию. Y1Y1 Y2Y2 Y6Y6 Y5Y5 Y4Y4 Y3Y3 Y8Y8 Y7Y7 X

19 Начало Ввод n i=1,n Yi i=2,n X=Yi j=i -1 Yj+1=X i=1,n Yj Конец 1 Блок-схема сортировки массива методом «вставки» 1 Yj+1=Yj J=j -1 J>0 and x

20 Фрагмент программы, реализующей сортировку массива методом вставки. For i:=1 to n do Begin x:=y[i];{Сохраним текущий элемент массива.} {В переменной j будем хранить номера элементов, предшествующих текущему.} J:=i-1; {Сдвиг массива на одну позицию в право до тех пор, пока} While (x 0) do Begin y[j+1] :=y[j]: j:=j-1; End; {Запись текущего элемента на соответствующую позицию,} {то есть перед элементами, превышающими его.} y[j+1]:=x; end;

21 Сортировка массива по возрастанию методом «выбора» Найдем в массиве самый большой элемент и поменяем его местами с последним элементом. Повторим алгоритм поиска максимального элемента, уменьшив количество просматриваемых элементов на единицу и поменяем его местами с предпоследним элементом. Описанную выше операцию поиска проводим до полного упорядочивания элементов в массиве.. Для упорядочивания массива по убыванию необходимо перемещать минимальный элемент.

22 Блок – схема сортировки массива методом «выбора» i=2,n K=n j=1,n max=y[1] nom=1 y[i]>max max=y[i] nom=i n=n-1 b=y[nom] y[nom]=y[n] y[n]=b

23 Быстрая сортировка. Один из самых быстрых алгоритмов, позволяющих достигать производительности ~ O(n*log n). 1. В исходной последовательности выбирается некоторый опорный элемент a[i]. 2. Пробегаемся по всей последовательности и элементы, меньшие, либо равные a[i] располагаем слева от него, большие - справа. 3.Эту же самую процедуру рекурсивно запускаем для 2-х полученных половинок. =a[i] Т.е. в 2-х полученных последовательностях слева и справа от выбранного на первом шаге элемента - также выбираем некоторый опорный ключ и перебрасываем соответствующие большие и меньшие чем он элементы. 4. В уже 4-х полученных последовательностях - тоже самое. Пока не получим последовательности, состоящие лишь из одного элемента. После выполнения всех рекурсий в результате получаем отсортированную исходную последовательность. Принцип работы

24 Выбор опорного элемента При быстрой сортировке выбор опорного элемента на каждом шаге играет очень значительную роль, т.к. от этого зависит суммарная скорость выполнения всего алгоритма при различных условиях сортировки. Варианты выбора опорного элемента. 1.Частичная упорядоченность элементов. 2.Наиболее хаотичное расположение элементов. 3.Самые распространенные варианты: выбор середины отрезка выбор случайного элемента последовательности выбор первого элемента последовательности.

25 Алгоритм выбора опорного элемента последовательности Этот алгоритм был впервые описан К. А. Р. Хоаром в его классической статье «Быстрая сортировка»

26 положение первого обмена Чтобы отсортировать массив, мы разделяем его на два под массива и сортируем каждый из них рекурсивно. Например, для сортировки массива из семи элементов: Разделение массива ij Исходное положение i Положение второго обмена Положение третьего обмена j i j ij

27 program Quitsort; uses crt; Const N=10; Type Mas=array[1..n] of integer; var a: mas; k: integer; function Part(l, r: integer):integer; var v, i, j, b: integer; begin V:=a[r]; I:=l-1; j:=r; repeat dec(j) until (a[j]=v) or (i=j-1); b:=a[i]; a[i]:=a[j]; a[j]:=b; until i>=j; a[j]:=a[i]; a[i]:= a[r]; a[r]:=b; part:=i; end; procedure QuickSort(l, t: integer); var i: integer; begin if l

28 Результат работы программы 60,79, 82, 58, 39, 9, 54, 92, 44, 32 9,79, 82, 58, 39, 60, 54, 92, 44, 32 9, 32, 82, 58, 39, 60, 54, 92, 44, 79 9, 32, 44, 58, 39, 60, 54, 92, 82, 79 9, 32, 44, 58, 39, 54, 60, 92, 82, 79 9, 32, 44, 58, 39, 92, 60, 54, 82, 79 9, 32, 44, 58, 39, 54, 60, 79, 82, 92 9, 32, 44, 58, 54, 39, 60, 79, 82, 92 9, 32, 44, 58, 60, 39, 54, 79, 82, 92 9, 32, 44, 58, 54, 39, 60, 79, 82, 92 9, 32, 39, 58, 54, 44, 60, 79, 82, 92 9, 32, 39, 44, 54, 58, 60, 79, 82, 92 9, 32, 39, 44, 58, 54, 60, 79, 82, 92 9, 32, 39, 44, 54, 58, 60, 79, 82, 92 9, 32, 39, 44, 54, 58, 60, 79, 92, 82 9, 32, 39, 44, 54, 58, 60, 79, 82, 92

29 Заключение Метод быстрой сортировки позволяет существенно сократить количество операций. Например: Все предыдущие методы требовали N 2 операций, где N – количество элементов. Метод быстрой сортировки требует в среднем N*Log 2 N операций. В случае N=100, выигрыш составляет порядка 100 раз.