СОРТИРОВКА МАССИВОВ Сортировка - это процесс размещения элементов заданного множества объекта в некотором определенном порядке, как правило, в порядке. - презентация

1

2 СОРТИРОВКА МАССИВОВ

3 Сортировка - это процесс размещения элементов заданного множества объекта в некотором определенном порядке, как правило, в порядке возрастания или убывания.

4 Способы сортировки Сортировка подсчетом Сортировка подсчетом Сортировка вставками Сортировка вставками Сортировка простым обменом Сортировка простым обменом (пузырьковая сортировка) (пузырьковая сортировка) Сортировка простым выбором Сортировка с разделением

5 Нажмите пробел

6 Метод. Каждый элемент массива сравнивается со всеми остальными. Место каждого элемента в отсортированном массиве зависит от числа элементов, меньших его. Если некоторый элемент превышает пять других, то его место в упорядоченной последовательности - 6. Следовательно, для сортировки необходимо сравнить попарно все элементы и подсчитать, сколько из них меньше каждого отдельного элемента. После этого все элементы исходного массива можно разместить на соответствующих им местах в новом, специально созданном массиве.

7 Используются следующие величины : i- Индекс рассматриваемого элемента j- k- Индекс элемента, с которым сравнивается рассматриваемый Число элементов, меньших рассматриваемого

8 Исходный массив А: Массив B: Задача : Расположить элементы массива в порядке возрастания в массиве B

9 Исходный массив А: Массив B:

10 Исходный массив А: A[1]:=5 если A[j]

11 Исходный массив А: K=1 Массив B: B[k+1]:=A[i] B[2]:=5

12 Исходный массив А: K=1 Массив B: B[k+1]:=A[i] B[2]:=5

13 Исходный массив А: Массив B:

14 Исходный массив А: Массив B: A[1]:=18 если A[j]

15 B[k+1]:=a[i] B[4]:=18 Исходный массив А: Массив B: K=3

16 B[k+1]:=a[i] B[4]:=18 Исходный массив А: Массив B: K=3

17 Исходный массив А: 18 5 Массив B:

18 Исходный массив А: 18 5 Массив B: A[1]:=3 если A[j]

19 Исходный массив А: 18 5 Массив B: B[k+1]:=a[i] B[1]:=3

20 Массив B: Исходный массив А: B[k+1]:=a[i] B[1]:=3

21 Массив B: Исходный массив А:

22 12 27 A[1]:=12 если A[j]

23 Исходный массив А: B[k+1]:= A[i] B[3]:=12 K=2 Массив B:

24 Исходный массив А: 27 B[k+1]:= A[i] B[3]:=12 K=2 Массив B:

25 Исходный массив А: 27 Массив B:

26 Исходный массив А: 27 A[1]:=27 если A[j]

27 Исходный массив А: 27 B[k+1]:=a[i] B[5]:=27 Массив B: K=4

28 Исходный массив А: B[k+1]:=a[i] B[5]:=27 Массив B: K=4

29 Программа на школьном алгоритмическом языке : алг cort (арг цел таб а [1:n], рез цел таб b [1:n]) нач цел i,j,k нц для i от 1 до n k:=0 нц для i от 1 до n если а[j]

30 Программа на Паскале : program inf1; uses crt; var i,n,j,k:integer; a,b:array[1..100] of integer; begin clrscr; randomize; write(Введите к-во элементов: ');readln(n); writeln(Исходный массив: '); for i:=1 to n do begin a[i]:=random(100); write(a[i]:4); end; writeln; for i:=1 to n do begin k:=0; for j:=1 to i-1 do if a[j]

31 Выполнение в Паскале PASCAL

32

33

34 При сортировке вставками из неупорядоченной последовательности элементов поочередно выбирается каждый элемент, сравнивается с предыдущим (уже упорядоченным) списком и помещается на соответствующее место в последнем.

35 Алгоритм сортировки массива методом вставок Нц для i от 2 до n Разместить элемент а [i] на соответствующем ему месте в предшествующей последовательности Кц

36 Размещение элемента массива на соответствующем ему месте в предшествующей, уже упорядоченной последовательности, может быть проведено двумя способами Можно последовательно сравнивать рассматриваемый элемент с элементом, расположенным слева от него, и обменивать из местами до тех пор, пока слева от перемещаемого элемента не окажется элемент, меньший или равный ему. Такой способ будем называть «сравнение и обмен». Можно сначала определить место, соответствующее рассматриваемому элементу в упорядоченной последовательности, а затем разместить его в этой ячейке, сместив соответствующие элементы на одну позицию вправо. Эту разновидность размещения назовем «поиск места и вставка».

37 Познакомься с тремя методами сортировки: «Поиск места и вставка» «Сравнение и обмен» «Бинарная вставка»

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

39 Сортировка этим методом производится последовательно, шаг за шагом 1) На К-м шаге считается, что часть массива, содержащая первые К-1 элементов, уже упорядочена, то есть А[1]

40 Рассмотрим этот процесс на примере. Пусть требуется отсортировать массив из 6 элементов по возрастанию:

41 Рассматриваем часть массива из одного элемента 13. Вставляем второй элемент массива 6 так, чтобы упорядоченность сохранилась. Так как 6

42 Возьмем третий элемент массива 8 и подберем для него место в упорядоченной части массива. 8 > 6 и 8 6 и 8

43 Следующий элемент Он записывается в упорядоченную часть массива на третье место, так как 11 >8, но 11 8, но 11 < 13 8

44 Далее, действуя аналогичным Далее, действуя аналогичным образом, определяем, что 3 необходимо записать образом, определяем, что 3 необходимо записать на первое место на первое место 3

45 Осталось подобрать подходящее место для последнего элемента Осталось подобрать подходящее место для последнего элемента 5 3

46 В процедуре, реализующей сортировку вставкой с таким вариантом размещения, целесообразно использовать две вспомогательные процедуры: 1) Find_Place - определяющую подходящее место элемента массива с индексом i в предшествующей ему упорядоченной части массива; 2) Insert- которая обеспечивает перемещение в массиве элемента с индексом i на j-ю позицию и смещение всех элементов с индексами от j до i-1 на одну позицию вправо.

47 program inf1; uses crt; var i,n,j,c:integer; a:array[1..100] of integer; procedure Swap(var a,b:integer); var c:integer; begin c:=a; a:=b;b:=c; end; begin clrscr; randomize; write( 'Введите количество элементов массива : ');readln(n); writeln( 'Исходный массив : '); for i:=1 to n do begin a[i]:=random(100); write(a[i]:4); end; writeln; {Выбираем последовательно элементы с индексами от 2 до n}

48 for i:=2 to n do if a[i]=a[j-1]) end; {Swap - процедура, выполняющая обмен значениями двух величин procedure Swap(var a,b:integer); var c:integer; begin c:=a; a:=b;b:=c; end;} writeln( 'Отсортированный массив : ' ); for i:=1 to n do write(a[i]:4); end. Запуск программы

49 Учитывая, что место для очередного размещаемого элемента с одинаковой вероятностью может находиться как во второй, так и в первой половине упорядоченной части, можно в процедуре Find_Place определять значение индекса j, идя от начала массива. Это позволит отказаться от использования «барьера» и всех связанных с ним уточнений программы. Приведем соответствующие процедуры. Find_Place (a:arrtype; i:integer); Procedure Find_Place (a:arrtype; i:integer);beginj:=1; while a[j]

50 Сравнительная характеристика вариантов метода вставок (продолжительность сортировки) Примечание 1,0 соответствует минимальному времени сортировки, остальные значения рассчитаны по отношению к минимальному в Количество элементов в массиве Вариант метода (способ размещения (способ размещения очередного элемента) N=1000N=2000N=4000 1,8 1,0 1,4 7,5 3,7 5,7 30,2 15,4 22,5 Cравнение и обмен Сравнение и обмен с «барьером» с «барьером» Поиск места и вставка

51 Размещение путем сравнения и обмена

52 Действия по размещению некоторого элемента, соответствующие этому варианту, могут быть оформлены в виде следующих команд: i - начальный индекс перемещаемого элемента; j - индекс, который этот элемент имеет в ходе перемещения;

53 если а[i]< а[i-1] { Если нужно перемещать элемент } то j:=i нцSwap (a[j],a[j-1]) { Смещаем его влево путем обмена } j:=j-1 { Новый индекс перемещаемого элемента } при j=1или а[j]>=а[j-1] кц всё

54 Swap - процедура, обеспечивающая обмен значениями двух величин: алг (арг рез цел a,b) нач цел с с:=а; а:=b; :b=с кон Примечание: Использование в условии окончания цикла дополнительного условия j=1 позволяем избежать сравнения j-го элемента с несуществующим j(-1)-м, что имеет место при j=1.

55 Можно также использовать цикл с предусловием: j:=i нц пока j>1и a[j],a[j-1] { Пока нужно перемещать i-й элемент} Swap(a[j],a[j-1]){ Смещаем его влево путем обмена} j:=j-1 { Новый индекс перемещаемого элемента} кц

56 Очевидно, что использование в процедурах дополнительного условия j=1 приводит к существенному увеличению времени выполнения программ ( для каждого элемента многократно проверяется дополнительное условие). Это недостаток можно устранить, если применить так называемый «барьер» : 4создать в сортируемом массиве элемент с индексом 0 ( расширив диапазон индексов в описании массива до 0…n) 4на каждом шаге сортировки присваивать ему значение, равное значению очередного размещаемого элемента

57 program inf2; uses crt; var i,n,j:integer; a:array[0..100] of integer; begin clrscr; randomize; write( 'Введите количество элементов массива : ');readln(n); writeln( 'Исходный массив : '); for i:=1 to n do begin a[i]:=random(100); write(a[i]:4); end; writeln; for i:=2 to n do if a[i]

=a[j-1];{ Место j, соответствующее элементу a[i], найдено } a[j]:=a[0] { На найденном месте размещаем элемент a[i]} e" title="a[0]:=a[i]; { Создадим "барьер "} j:=i; repeat begin a[j]:=a[j-1]; { Смещаем соседний слева элемент вправо } j:=j-1; end; until a[0]>=a[j-1];{ Место j, соответствующее элементу a[i], найдено } a[j]:=a[0] { На найденном месте размещаем элемент a[i]} e" class="link_thumb"> 58 a[0]:=a[i]; { Создадим "барьер "} j:=i; repeat begin a[j]:=a[j-1]; { Смещаем соседний слева элемент вправо } j:=j-1; end; until a[0]>=a[j-1];{ Место j, соответствующее элементу a[i], найдено } a[j]:=a[0] { На найденном месте размещаем элемент a[i]} end; writeln( 'Отсортированный массив : ' ); for i:=1 to n do write(a[i]:4); end. Запуск программы =a[j-1];{ Место j, соответствующее элементу a[i], найдено } a[j]:=a[0] { На найденном месте размещаем элемент a[i]} e"> =a[j-1];{ Место j, соответствующее элементу a[i], найдено } a[j]:=a[0] { На найденном месте размещаем элемент a[i]} end; writeln( 'Отсортированный массив : ' ); for i:=1 to n do write(a[i]:4); end. Запуск программы"> =a[j-1];{ Место j, соответствующее элементу a[i], найдено } a[j]:=a[0] { На найденном месте размещаем элемент a[i]} e" title="a[0]:=a[i]; { Создадим "барьер "} j:=i; repeat begin a[j]:=a[j-1]; { Смещаем соседний слева элемент вправо } j:=j-1; end; until a[0]>=a[j-1];{ Место j, соответствующее элементу a[i], найдено } a[j]:=a[0] { На найденном месте размещаем элемент a[i]} e">

59 Можно также ускорить работу, если в ходе размещения не проводить обмен значениями двух соседний элементов массива ( процедура Swap выполняет 3 операции присваивания!). Достаточно только смещать вправо на одну позицию элементы, меньшие рассматриваемого, а затем разместить последний на найденном для него месте. не проводить обмен значениями двух соседний элементов массива ( процедура Swap выполняет 3 операции присваивания!). Достаточно только смещать вправо на одну позицию элементы, меньшие рассматриваемого, а затем разместить последний на найденном для него месте. В случае, если элементы массива не отрицательные числа, механизм использования «барьера» упрощается. Достаточно только расширить нижнюю границу диапазона индексов массива до 0 и элементу а[0] присвоить нулевое значение. Он будет выполнять роль «барьера» для всех размещаемых элементов.

60 Сортировка методом бинарных вставок

61 Место, соответствующее некоторому элементу массива в предшествующей ему последовательности, можно найти значительно быстрее, пользуясь тем, что эта последовательность уже упорядочена. Для этого необходимо использовать так называемый бинарный поиск, который исследует средний элемент упорядоченной последовательности и продолжает деление пополам, пока не будет найдено место включения.

62 Разработаем функцию Binary_Search, определяющую индекс ячейки в упорядоченной части массива а, в которой должно размещаться некоторое число m. Упорядоченная часть массива имеет границы индексов 1..last. Обозначим i- индекс левого элемента исследуемого в ходе поиска отрезка массива, r - правого, mid - величину, равную (l+r)/2. В начале поиска принимаем l=1,r=last.

63 Определяем величину mid и сравниваем значения: a[mid] и m. Если a[mid]>m, то размещаемое число должно находиться в левой половине исследуемого диапазона, т.е. Можно принять r=mid-1, в противном случае - в правой половине - 1=mid+1. После этого процесс повторяется применительно к новому диапазону и заканчивается, когда r станет меньше 1. В этой ситуации искомый индекс равен значению 1.

64 Процедура Binary_Search на языке Паскаль имеет вид: Function Binary_Search (last:word;var a:arrtype;m:word):word; var l,r,mid:word;begin l:=1; r:=last; while lm then r:=mid-1 else l:=mid+1end; Binary_Search:=1 end;

65 Процедуры сортировки методом бинарных вставок, использующие приведенные функции, имеют вид: Procedure Binary_Insert_Sort(var a:arrtype); var i:integer; begin for i:=2 to n do if a[i]

66 Разновидность метода вставок, использующая бинарный поиск места размещения очередного элемента, называется сортировкой бинарными вставками. Сравним ее с методами сортировки простыми вставками.

67 Когда при сортировке простыми вставками на соответствующем месте размещается i-й элемент, то его значение сравнивается в среднем примерно с i/2 ранее отсортированными значениями, поэтому общее число сравнений при этом равно (1+2+…+n)/2=n*n/4, а это очень много, даже если n умеренно велико. При использовании же бинарного поиска места размещения очередного элемента число сравнений значительно меньше. Например, если очередной элемент - 64-й, то его значение сначала сравнивается с 37-м; затем с 16- м или 48-м и т.д., так что искомое место будет найдено максимум после всего лишь шести сравнений. Общее же число сравнений для n элементов равно приблизительно nlog2n,что существенно лучше, чем n*n/4.

68 Неприятность состоит в том, что бинарный поиск решает только половину задачи - после того, как мы нашли место очередного элемента, все равно нужно «вставить» этот элемент на найденное место и сместить некоторый отрезок упорядоченной последовательности на 1 позицию вправо. А поскольку в компьютере операция присваивания выполняется за значительно большее время, чем операция сравнения, то общая экономия времени будет незначительной, так что общее время работы при бинарном поиски, по существу, остается пропорциональным n*n/2.

69

70 CОРТИРОВКА ПРОСТЫМ ОБМЕНОМ - МЕТОД, ПРИ КОТОРОМ ВСЕ СОСЕДНИЕ ЭЛЕМЕНТЫ МАССИВА ПОПАРНО СРАВНИВАЮТСЯ ДРУГ С ДРУГОМ И МЕНЯЮТСЯ В ТОМ СЛУЧАЕ, ЕСЛИ ПРЕДШЕСТВУЮЩИЙ ЭЛЕМЕНТ БОЛЬШЕ ПРЕДЫДУЩЕГО. МЕТОД, ПРИ КОТОРОМ ВСЕ СОСЕДНИЕ ЭЛЕМЕНТЫ МАССИВА ПОПАРНО СРАВНИВАЮТСЯ ДРУГ С ДРУГОМ И МЕНЯЮТСЯ В ТОМ СЛУЧАЕ, ЕСЛИ ПРЕДШЕСТВУЮЩИЙ ЭЛЕМЕНТ БОЛЬШЕ ПРЕДЫДУЩЕГО.

71 В РЕЗУЛЬТАТЕ ЭТОГО МАКСИМАЛЬНЫЙ ЭЛЕМЕНТ ПОСТЕПЕННО СМЕЩАЕТСЯ ВПРАВО И В КОНЦЕ КОНЦОВ ЗАНИМАЕТ СВОЁ, КРАЙНЕ-ПРАВОЕ МЕСТО В МАССИВЕ, ПОСЛЕ ЧЕГО ОН ИСКЛЮЧАЕТСЯ ИЗ ДАЛЬНЕЙШЕЙ ОБРАБОТКИ. В РЕЗУЛЬТАТЕ ЭТОГО МАКСИМАЛЬНЫЙ ЭЛЕМЕНТ ПОСТЕПЕННО СМЕЩАЕТСЯ ВПРАВО И В КОНЦЕ КОНЦОВ ЗАНИМАЕТ СВОЁ, КРАЙНЕ-ПРАВОЕ МЕСТО В МАССИВЕ, ПОСЛЕ ЧЕГО ОН ИСКЛЮЧАЕТСЯ ИЗ ДАЛЬНЕЙШЕЙ ОБРАБОТКИ.

72 ЗАТЕМ ПРОЦЕСС ПОВТОРЯЕТСЯ, И СВОЁ МЕСТО ЗАНИМАЕТ ВТОРОЙ ПО ВЕЛИЧИНЕ ЭЛЕМЕНТ, КОТОРЫЙ ТАКЖЕ ИСКЛЮЧАЕТСЯ ИЗ ДАЛЬНЕЙШЕГО РАССМОТРЕНИЯ. Т АК ПРОДОЛЖАЕТСЯ ДО ТЕХ ПОР, ПОКА ВСЯ ПОСЛЕДОВАТЕЛЬНОСТЬ НЕ БУДЕТ УПОРЯДОЧЕНА. ЗАТЕМ ПРОЦЕСС ПОВТОРЯЕТСЯ, И СВОЁ МЕСТО ЗАНИМАЕТ ВТОРОЙ ПО ВЕЛИЧИНЕ ЭЛЕМЕНТ, КОТОРЫЙ ТАКЖЕ ИСКЛЮЧАЕТСЯ ИЗ ДАЛЬНЕЙШЕГО РАССМОТРЕНИЯ. Т АК ПРОДОЛЖАЕТСЯ ДО ТЕХ ПОР, ПОКА ВСЯ ПОСЛЕДОВАТЕЛЬНОСТЬ НЕ БУДЕТ УПОРЯДОЧЕНА.

73 Чтобы лучше разобраться в этом способе сортировки, рассмотрим идею метода на примере: Чтобы лучше разобраться в этом способе сортировки, рассмотрим идею метода на примере:

74 Отсортируем по возрастанию массив из 5 элементов: Длина текущей (неупорядоченной) части массива-(N-k+1), где k –номер просмотра, i-номер первого элемента проверяемой пары (в данном случае i=5), номер последней пары - N-k (например 4 и 9).

75 Первый просмотр: Первый просмотр: рассматривается весь массив. рассматривается весь массив. K=1 i i= >4-меняется i= меняется i=

76 Второй просмотр: рассматриваем часть массива с первого до последнего элемента. Второй просмотр: рассматриваем часть массива с первого до последнего элемента. K=2i= меняется i=

77 Третий просмотр: рассматриваемая часть массива содержит три первых элемента. Третий просмотр: рассматриваемая часть массива содержит три первых элемента. K=3i= ;4>2-меняется i=

78 Четвёртый просмотр: Четвёртый просмотр: Рассматриваем последнюю пару элементов. Рассматриваем последнюю пару элементов. K=4;i=

79 Наименьший элемент – 2 оказывается на первом месте. Количество просмотров элементов массива равно N-1 (в данном случае четырем). Наименьший элемент – 2 оказывается на первом месте. Количество просмотров элементов массива равно N-1 (в данном случае четырем). Этот метод также называют методом пузырька. Название это происходит от образной интерпретации, при которой в процессе выполнения сортировки более лёгкие элементы ( элементы с заданным свойством) мало- помалу всплывают наповерхность. Этот метод также называют методом пузырька. Название это происходит от образной интерпретации, при которой в процессе выполнения сортировки более лёгкие элементы ( элементы с заданным свойством) мало- помалу всплывают наповерхность.

80

81 program z1; var j,t,i,n:integer;a:array[1..100] of integer; begin randomize;readln(n);writeln(Исходный массив'); for i:=1 to n do begin a[i]:=random(100); write(a[i]:3);end;writeln; For i:= 1 to N-1 Do For j:= i+1 to N Do if A[i] > A[j] then Begin t:= A[i]; A[i]:= A[j]; A[j]:= t; End; for i:=1 to n do write(a[i]:3); readln; End. ПАСКАЛЬ

82 П РИ СОРТИРОВКЕ МЕТОДОМ ПУЗЫРЬКА ВЫПОЛНЯЕТСЯ П РИ СОРТИРОВКЕ МЕТОДОМ ПУЗЫРЬКА ВЫПОЛНЯЕТСЯ N – 1 ПРОСМОТРОВ, НА КАЖДОМ i-М ПРОСМОТРЕ ПРОИЗВОДИТСЯ N-i СРАВНЕНИЙ. О БЩЕЕ КОЛИЧЕСТВО ( С) РАВНО N*(N-1)/2, ИЛИ С =O(N^2). N – 1 ПРОСМОТРОВ, НА КАЖДОМ i-М ПРОСМОТРЕ ПРОИЗВОДИТСЯ N-i СРАВНЕНИЙ. О БЩЕЕ КОЛИЧЕСТВО ( С) РАВНО N*(N-1)/2, ИЛИ С =O(N^2).

83

84 Сортировка выбором. Сортировка выбором состоит в том, что сначала в неупорядоченной последовательности выбирается минимальный элемент. Этот элемент исключается из дальнейшей обработки, а оставшаяся последовательность элементов принимается за исходную, и процесс повторяется до тех пор, пока все элементы не будут выбраны. Выбранный в исходной последовательности минимальный элемент размещается на предназначенном ему месте упорядоченной последовательности несколькими способами:

85 Минимальный элемент после i-го просмотра перемещается на i-е место (i=1,2,3,…) другого массива, а в старом, исходном, на месте выбранного размещается какое-то очень большое число, превосходящее по величине любой элемент сортируемого массива. Изменённый таким образом массив принимается за исходный, и осуществляется следующий просмотр. Очевидно, что при этом размер обрабатываемого массива остается постоянным.

86 Минимальный элемент после i-го просмотра перемещается на i-е место (i=1,2,3,…) заданного массива, а элемент с i-го места – на место выбранного. После каждого просмотра упорядоченные элементы (от первого до элемента с индексом i) исключаются из дальнейшей обработки, т.е. размер каждого последующего обрабатываемого массива на 1 меньше размера предыдущего. Приведём процедуры, соответствующие обоим способам.

87 В процедуре сортировка выбором будем использовать две вспомогательные функции: 1)IndMin, определяющую индекс минимального элемента массива а. 2)Max, определяющую индекс максимального элемента массива а. Эти функции на школьном алгоритмическом языке имеют вид: алг цел IndMin (арг цел таб а[1:n] ) нач цел imin, i (imin-текущее значение искомой величины) imin:=1 imin:=1 нц для i от 2 до n нц для i от 2 до n если а[i]m то то m:=а[i] m:=а[i] всё всё кц кц знач:=m(значение функции) знач:=m(значение функции)кон Первый способ.

88 алг Choice_Sortl (арг рез цел таб а[1:n],рез цел таб b[1:n]) нач цел maximum,i,j (maximum-максимальный элемент сортируемого массива ) нач цел maximum,i,j (maximum-максимальный элемент сортируемого массива ) maximum:=Max(а) (определяем максимальный элемент) maximum:=Max(а) (определяем максимальный элемент) нц для i от 1 до n (n раз выполняем следующие действия) нц для i от 1 до n (n раз выполняем следующие действия) (в i-ю ячейку массива b записываем минимальный элемент массива а) (в i-ю ячейку массива b записываем минимальный элемент массива а) j:=IndMin(а); b[i]:=а[i] j:=IndMin(а); b[i]:=а[i] (а на месте последнего размещаем число, превосходящее любой (а на месте последнего размещаем число, превосходящее любой элемент исходного массива) элемент исходного массива) а[j]:=maximum+1 а[j]:=maximum+1 кц кц кон кон С использованием этих функций процедура заполнения массива b элементами из массива а в порядке их не убывания на школьном алгоритмическом языке оформляется следующим образом:

89 Процедура сортировки в Паскале procedure Choice Sortl(a:arrtype;var b:arrtype); var maximum,i,j:integer;(maximum – максимальный элемент сортируемого массива) begin maximum:=Max(a);(определяем максимальный элемент массива) for i:=1 to n do (n раз выполняем следующие действия) begin (в i-ю ячейку массива b записываем минимальный элемент массива а) j:=IndMin (a); b[i]:=a[i]; (а на месте последнего размещаем число,превосходящее любой элемент исходного массива) a[ j ]:=maximum +1; end; end.

90 В данной программе функции IndMin и Max имеют вид: (функция,определяющая индекс минимального элемента массива а) function IndMin (a:arrtype):integer; var i,imin:integer;(imin – текущее значение искомой величины) begin imin:=1; for i:=2 to n do if a[i]m then m:=a[i]; Max:=m; end;

91 Второй способ алг цел IndMin (арг цел таб а[1:n], цел start) нач цел i,imin (imin-текущее значение искомой величины) imin:=start нц для i от start+1 до n если а[i]

92 Таблица 1.Сравнительная характеристика способов сортировки выбором Как и следовало ожидать, второй способ сортировки выбором гораздо эффективнее первого: Способ Количество элементов в массиве n=1000n=2000n= ,77,028,4 1,04,0 15,7

93 Если же при сортировке первым методом не тратить время на определение значения максимального элемента массива (а считать его известным), то соотношения времени сортировки несколько изменится: Способ Количество элементов в массиве n=1000n=2000n= ,35,019,7 1,04,0 15,7 Таблица 1.Сравнительная характеристика способов сортировки выбором

94 Приведем алгоритм сортировки простым выбором:

95 Рассмотрим идею данного метода на примере. Пусть исходный массив состоит из 10 элементов: После сортировки массив должен выглядеть так:

96 ? максимальный элемент текущей части массива ? элемент с которым происходит обмен рассматриваемая часть массива, т.е. ещё не упорядоченная ОБОЗНАЧЕНИЯ: Процесс сортировки будет состоять из 9-ти шагов.

97

98

99

100

101

102

103

104

105

106 Фрагмент программной реализации: procedure Sort; var i,j,k:integer; m:integer; (значение максимального элемента рассматриваемой части массива) begin for i:=N downto 2 do begin (цикл по длине рассматриваемой части массива) (поиск максимального элемента и его номера в текущей части массива) k:=i; m:=A[i]; (начальные значения максимального элемента и его индекса в рассматриваемой части массива) for j:=1 to i-1 do if A[j]>m then begin k:=j; m:=a[k]; end; if ki then ( перестановка элементов) begin A[k]:=A[i]; a[i]:= m; end; end; PROGRAM

107 Анохин Александр

108 Данный метод был предложен Ч.Э.Р. Хоаром в 1962 году. Этот метод обладает столь блестящими характеристиками с точки зрения времени выполнения, что Хоар назвал его БЫСТРАЯ СОРТИРОВКА

109 Идея метода: Допустим, исходный массив состоит из восьми элементов: В качестве барьерного элемента «X» возьмем средний элемент массива 7 Нашей целью является запись барьерного элемента « на своё место » в массиве, такое, чтобы слева от X были элементы, меньшие или равные X, а справа - большие X.

110 Наш массив : Сравнивая каждый элемент массива с барьерным элементом и производя необходимые перестановки, получаем: Теперь элемент 7 находится на своём месте

111 Производим необходимые перестановки. Наш массив: Продолжаем сортировку. Теперь перебираем следующие элементы массива, делая каждый из них барьерным Получаем:

112 Мы преобразовали исходный массив методом быстрой сортировки или, как её ещё называют, сортировки с разделением. Посмотрите как выглядит процедура быстрой сортировки на школьном алгоритмическом языке и на языке программирования Turbo Pascal.

113 нач цел i, j, x, w i: =m; j:=t; x:=a[(m+t) div 2] Алг QuickSort (арг цел m, t ) нц нц пока a[i]x Dec( j ) | уменьшаем указатель j | кц если ij если m

114 Язык программирования Pascal: Procedure QuickSort ( m, t : Integer ); Var i, j, x, w : Integer; Begin i:=m; j:=t; x:=a[ ( m+t ) div 2 ]; Repeat While A[ i ]x do Dec( j ); If ij; If m