МАССИВЫ. Сортировка Задачи, наиболее часто встающих перед программистами, это задачи сортировки и поиска. Данные задачи применяются как сами по себе, так и входят в состав более сложных задач. Например, дан массив N элементов, из которого надо удалить все дублирующиеся элементы. Решение сравнения каждойойого элемента с остальными потребует T(N 2 ) времени. Однако если предварительно отсортировать массив ( на что, как увидим позже, требуется T(N*log 2 (N)) времени ), то найти все дубли можно за T(N) времени, сравнивая только соседние элементы, так что общее время решения задачи T(N*log 2 (N)). Здесь задача сортировки вошла в другую задачу в качестве подзадачи. Задача сортировки формулируется следующим образом: На вход алгоритма подается последовательность из n элементов а 1,а 2,...,а n ; на выходе требуется получить некоторую перестановку входной последовательности a ' 1,a ' 2,...,а ' n такую, что a ' 1a ' 2…а ' n. Алгоритмы сортировки можно разделить на алгоритмы внутренней сортировки для сортировки данных, хранящихся во внутренней оперативной памяти компьютера, и внешней сортировки – для сортировки больших объемов данных, хранящихся в файлах внешней (например, дисковой) памяти. В данном учебном курсе будут рассматриваться только алгоритмы внутренней сортировки. ВМП 1

Пузырьковая сортировка по возрастанию – проходит по массиву снизу вверх (от последнего элемента к первому), сравнивая каждойойый элемент массива с расположенным выше, и если верхний больше, то меняет их местами. При этом проходе наименьший элемент – "всплывет" наверх. Операция продолжается пока наименьший элемент не станет первым. Затем операция повторяется над под множеством массива с номерами (индексами) элементов от 2 до N, затем над под множеством от 3 до N и так до под множества N-1, N. То есть, до тех пор пока массив не будет отсортирован по возрастанию элементов. (При формировании условия сравнения "наибольший наверх" будет происходить сортировка по убыванию элементов массива). Индекс Исходный массив 1 шаг 2 шаг 3 шаг На каждойойом шаге происходит три перестановки значений элементов. Нарисовать алгоритм пузырьковой сортировки 2 МАССИВЫ. Сортировка ВМП

Алгоритм пузырьковой сортировки Написать программу пузырьковой сортировки на Pascal и С.PascalС 3 МАССИВЫ. Сортировка buf = a[k-1] a[k-1] = a[k] a[k] = buf И Л size = 5 ДЛЯ ВСЁ Размерность массива Цикл сортировки под множеств массива И Л Цикл сортировки одного под множеств массива ЕСЛИ a[k-1] > a[k] ТО ИНАЧЕ ЕСЛИ ВСЁ Обмен значений элементов массива ДЛЯ ВСЁ ДЛЯ i=1 ДО size ДЛЯ k=size ДО i ВМП

CPascal Практическое занятие // Сортировка массива целых чисел методом пузырька #include #define sz 5 // размерность массива void main () { int a[sz]; /*массив целых чисел*/ int i; //счетчик циклов сортировки int buf; // буфер, исп. при обмене элементов массива int k; // текущий индекс элемента массива printf ("\n Введите в одной строке %i", sz); printf (" целых чисел и нажмите Enter\ n"); printf ("-> "); for (k = 0; k < sz; k++) scanf ("%i", &a[k]); // Сортировка for (i = 1; i < sz-1; i++) { for (k = sz-1; k > i; k--) { if (a[k-1] > a[k]) { // Меняем местами k-тый и k-1 элементы buf = a[k-1]; a[k-1] = a[k]; a[k] = buf; } // Цикл сортировки закончен // Вывод отсортированного массива printf (" Отсортированный массив\ n"); for (k = 0; k<sz; k++) printf ("%i ", a[k]); } Program bubble_sort; (* Сортировка массива целых чисел методом "пузырька" – по возрастанию *) const SIZE = 5 ; (* размерность массива *) var a : array[1..SIZE] of integer; i: integer; (* счетчик циклов сортировки*) buf: integer; (* буфер, исп. при обмене элем. массива *) k: integer; (* текущий индекс элемента массива *) begin writeln; write (' Введите в одной строке ', SIZE); writeln (' целых чисел и нажмите Enter '); write ('-> '); for k := 1 to SIZE do read (a[k]); (* Сортировка *) for i:= 2 to SIZE do begin for k := SIZE downto i do begin if a[k-1] > a[k] then begin (* Меняем местами k-1-й и k-й элементы *) buf := a[k-1]; a[k-1] := a[k]; a[k] := buf; end; (* Цикл сортировки закончен *) (* Вывод отсортированного массива *) writeln(' Отсортированный массив '); for k := 1 to SIZE do write (a[k],' '); end. 4 МАССИВЫ. Сортировка ВМП

Главный недостаток пузырьковой сортировки – большое количество перестановок элементов. Алгоритм выборочнымой сортировки устраняет этот недостаток, здесь элемент сразу занимает свою конечную позицию. Выборочная сортировка – происходит следующим образом: 1. Просматривается весь первичный массив, определяется наименьший (наибольший) элемент массива и затем осуществляется единственный обмен в текущем массиве. 2. Потом просматривается массив-под множество без наименьшего (наибольшего) элемента, определяется наименьший (наибольший) элемент под множества и снова осуществляется единственный обмен в текущем под множестве массива. 3. Шаг 2 повторяется пока весь массив не будет отсортирован. Нарисовать алгоритм выборочнымой сортировки 5 МАССИВЫ. Сортировка ВМП

6 Алгоритм выборочнымой сортировки Написать программу выборочнымой сортировки на Pascal и С.PascalС МАССИВЫ. Сортировка min = j buf = a[i] a[i] = a[min] a[min] = buf И Л size = 5 ДЛЯ ВСЁ Размерность массива Цикл сортировки массива И Л Цикл поиска мин. элем. в массиве от a[i] до a[SIZE] ЕСЛИ a[j] < a[min] ТО ИНАЧЕ ЕСЛИ ВСЁ Обмен значений элементов массива ДЛЯ ВСЁ min = i ДЛЯ i=1 ДО size-1 ДЛЯ j=i+1 ДО size ВМП

CPascal Практическое занятие Program direct_sort; (* Сортировка массива целых чисел выборочнымым методом - по возрастанию *) Const SIZE = 5; (* размерность массива *) Var a : array[1..SIZE] of integer; i: integer; (* элем., от которого идёт поиск мин. элем.*) min: integer; (* мин. элемента в части массива от i до конца массива *) j: integer; (* элемента сравниваемого с мин. *) buf: integer; (* буфер, исп. при обмене элем. массива *) k: integer; (* индекс для ввода и вывода *) begin writeln; write (' Введите в одной строке ', SIZE); writeln (' целых чисел и нажмите Enter '); write ('-> '); for k := 1 to SIZE do read (a[k]); (* Сортировка *) for i:= 1 to SIZE-1 do begin (*Поиск мин. элем. в массиве от a[i] до a[SIZE]*) min := i; for j := i+1 to SIZE do if a[j] < a[min] then min := j; (* Меняем местами a[min] и a[i] *) buf := a[i]; a[i] := a[min]; a[min] := buf; end; (* Цикл сортировки закончен *) (* Вывод отсортированного массива *) writeln(' Отсортированный массив '); for k := 1 to SIZE do write (a[k],' '); end. // Сортировка мас. целых чисел выборочным. методом #include #define sz 5 // размерность массива void main () { int a[sz]; // массив целых чисел int i; // элем., от которого ведется поиск мин. элем. int min; // мин. элем. в части мас. от i до конца мас. int j; // элемента сравниваемого с мин. int buf; // буфер, исп. при обмене элементов массива int k; // индекс для ввода и вывода printf ("\n Введите в одной строке %i", sz); printf (" целых чисел и нажмите Enter \n"); printf ("-> "); for (k=0; k<sz; k++) scanf ("%i", &a[k]); // Сортировка for (i = 0; i < sz-1; i++) { // Поиск мин. элем. в части мас. от a[i] до a[sz] min = i; for (j = i+1; j < sz; j++) if (a[j] < a[min]) min = j; // Меняем местами a[min] и a[i] buf = a[i]; a[i] = a[min]; a[min] = buf; } // Цикл сортировки закончен // Вывод отсортированного массива printf ("Отсортированный массив\n"); for (k = 0; k<sz; k++) printf ("%i ", a[k]); } 7 МАССИВЫ. Сортировка ВМП

Быстрая сортировка (автор Чарльз Хоар, в 1962 г.) – Quicksort – Метод сортировки разделением: Из массива выбирается опорный элемент P. Сравнивая элементы массива с P и разделяем (сортируем) массив на 2-а подмассива (под множества). Слева от P элементы меньшие и равные P, а справа – большие или равные. Для обоих под множеств, если в них больше 1-го элемента, проделывается та же процедура. Процесс повторяются для каждойойой части массива пока он не будет отсортирован. Опорный элемент выбирается или случайным образом, или как среднее некоторого количества значений массива (например, первого и последнего). Тем не менее оба метода и пузырьковая и выборочнымая сортировка сравнительно неэффективны. N 2 Среднее время работы этих алгоритмов пропорционально N 2. Существуют более быстрые методы сортировки: быстрая сортировка (Quicksort) и сортировка слиянием (метод Шелла). N*log 2 (N). Среднее время работы этих методов пропорционально N*log 2 (N). 8 МАССИВЫ. Сортировка ВМП

1) Берем массив M[N]. Назначаем индексы I и J. 2) Устанавливаем начальные значения индексов I=1 и J=N. 3) Выбираем опорный элемент P = M[K], где K = (I +J) / 2. 4) Сравниваем M[I] <= P, если ДА, то увеличиваем I (I=I+1). 5) Затем сравниваем M[J] >= P, если ДА, то уменьшаем J (J=J-1). 6) Если НЕТ и I<=J, то меняем местами M[I] и M[J]. 7) Повторяем шаги 4-6 пока I<=J. 8) В результате массив разделяется на 2-е части, слева от P элементы меньше или равны P, а справа – больше или равны. 9) Над каждойойой частью (под множеством) массива повторяем шаги 2-7. Получаем 4-е под множества. 10) Над каждойойым под множеством повторяем шаги 2-7. Выполняем эти операции пока массив не будет отсортирован. Быстрая сортировка (разделением): 9 Алгоритм быстрой сортировки МАССИВЫ. Сортировка ВМП

1. Массив M[N]. Назнач. I и J. 2. Уст. нач. знач. I=1 и J=N. 3. Выб. Опор.элем. P = M[(M[1]+M[N])/2]. 4. Сравн. M[I] <= P, если ДА, то I=I Сравн. M[J] >= P, если ДА, то J=J Если НЕТ и I<=J, то меняем местами M[I] и M[J]. 7. Повторяем шаги 2-6 пока I<=J. 8. Массив раздел. на 2-е части, слева от P элементы = P. 9. Над каждойой. под множ. мас. повт. шаги 2-7. Получ. 4 под множ. 10. Над каждойой. под множ. повт. шаги 2-7. Вып. эти операции пока массив не будет отсортирован. Пример: 1-2. { } 3. P= { } - меняем местами 13 и 8 = { } 8. Массив разделен на две части по Сортируем под множество { } 2-7. P=7 -> { } = { } – P=2 -> { } = { } – P=8 -> { } = { } Нарисовать алгоритм быстрой сортировки на Pascal и С.PascalС 10 Алгоритм быстрой сортировки МАССИВЫ. Сортировка ВМП

11 Алгоритм быстрой сортировки Написать программу быстрой сортировки на Pascal и С.PascalС МАССИВЫ. Сортировка ПОКА P<A[j] ПОКА A[i] < P ТО ИНАЧЕ ЕСЛИ L < j 2 Выполнить цикл ПОВТОРЯТЬ-ПОКА для сортировки элементов массива а, находящихся между a[L] и a[j] ЕСЛИ ВСЁ ТО ИНАЧЕ ЕСЛИ i < R Выполнить цикл ПОВТОРЯТЬ-ПОКА для сортировки элементов массива а, находящихся между a[i] и a[R] ЕСЛИ ВСЁ i = i + 1 Л И i = L j = R P = Целое((i +j) / 2) ПОВТОРЯТЬ Получить: Массив A[N] ПОКА ВСЁ j = j - 1 Л ПОКА ВСЁ 1 И buf = a[i] a[i] = a[j] a[j] = buf ТО ИНАЧЕ ЕСЛИ ВСЁ 1 ЕСЛИ i <= j i = i + 1 j = j - 1 И Л 2 ПОКА i <= j ВМП

12 Алгоритм быстрой сортировки (в виде рекурсивной функции) Написать программу быстрой сортировки на Pascal и С.PascalС МАССИВЫ. Сортировка ПОКА P<A[j] ТО ИНАЧЕ ЕСЛИ L < j 2 ЕСЛИ ВСЁ ТО ИНАЧЕ ЕСЛИ i < R ЕСЛИ ВСЁ Вызов функции quicksort (L,j) Вызов функции quicksort (i,R) Конец Заголовок функции quicksort (L,R) i = i + 1 И Л i = L j = R ПОВТОРЯТЬ ПОКА ВСЁ j = j - 1 Л ПОКА ВСЁ 1 Начало P = < Целое((i +j) / 2) И buf = a[i] a[i] = a[j] a[j] = buf ТО ИНАЧЕ ЕСЛИ ВСЁ 1 ЕСЛИ i <= j i = i + 1 j = j - 1 И Л 2 ПОКА i <= j ПОКА A[i] < P ВМП

procedure QuickSort( L, R : Integer ); { Процедура - быстрая сортировка массива A[] } var i,j,x,y : integer; begin i := L; j := R; x := a[(L+R) div 2]; repeat while (A[i] < x) do inc(i); while (x < A[j]) do dec(j); if ( i <= j ) then begin y:=A[i]; a[i]:=a[j]; a[j]:=y; inc(i); dec(j); end; until (i > j); if (L < j) then QuickSort(L,j); if (i < R) then QuickSort(i,R); end; Pascal Практическое занятие 13 Program qsort; {Быстрая сортировка} var a:array[1..10] of integer; { массив элементов } n:integer; procedure QuickSort(L, R : Integer); { Процедура - быстрая сортировка массива A[] } ….. End; begin writeln('введите 10 элементов массива:'); for n:=1 to 10 do readln(a[n]); QuickSort( 1, 10 ); { на входе: левая и правая граница сортировки } writeln('после сортировки:'); for n:=1 to 10 do write(a[n],' '); end. МАССИВЫ. Сортировка ВМП

procedure QuickSort( L, R : Integer ); { Процедура - быстрая сортировка массива A[] } var i,j,x,y : integer; begin i := L; j := R; x := a[(L+R) div 2]; repeat while (A[i] < x) do inc(i); while (x < A[j]) do dec(j); if ( i <= j ) then begin y:=A[i]; a[i]:=a[j]; a[j]:=y; inc(i); dec(j); end; until (i > j); if (L < j) then QuickSort(L,j); if (i < R) then QuickSort(i,R); end; void quicksort (long High, long Low) // Функция быстрой сортировки { long i, j; int p, temp; i = Low; // Инициализация нижней границы j = High; // Инициализация верхней границы p = array[(Low+High)/2]; // опорный элемент do { while (array[i] < p) i++; while (array[j] > p) j--; if (i<=j) // Если верно, то обмен { temp = array[i]; array[i] = array[j]; array[j] = temp; i++; j--; } } while (i<=j); // пока индексы не пересекутся if (j > Low) quicksort (j, Low); /* Если подмассив [Low, j] более одного элемента, он сортируется функцией quicksort */ if (High > i) quicksort (High, i); /* Если [i, High] более одного элемента, он сортируется функцией quicksort */ } CPascal Практическое занятие 14 МАССИВЫ. Сортировка ВМП

Program qsort; { Быстрая сортировка } var a:array[1..10] of integer; { массив элементов } n:integer; procedure QuickSort(L, R : Integer); { Процедура - быстрая сортировка массива A[] } ….. End; begin writeln('введите 10 элементов массива:'); for n:=1 to 10 do readln(a[n]); QuickSort( 1, 10 ); { на входе: левая и правая граница сортировки } writeln('после сортировки:'); for n:=1 to 10 do write(a[n],' '); end. #include int array[10000]; // Объявление массива /* Функция - Быстрая сортировка ………………………………………… */ main() // Главная функция { int i; int size; // количества элементов cout << "\n Введите количество элементов сортируемого массива size = "; cin >> size; for (i=0; i > array[i]; // Чтение очередного элемента массива for (i=0; i<size; i++) cout << array[i] << " "; quicksort (size-1, 0); // функция сортировки // Вывод отсортированного массива cout << "\n Отсортированный массив\n "; for (i=0; i<size; i++) cout << array[i] << " "; return 0; } CPascal Практическое занятие 15 МАССИВЫ. Сортировка ВМП

Сортировка методом Шелла Суть этого метода заключается в сравнении элементов массива, разделен- ных одинаковым расстоянием, таким образом, чтобы элементы были упорядочены по расстоянию. Затем это расстояние делится пополам и процесс повторяется. Алгоритм сортировки Шелла: В этом методе первоначально рассматриваются элементы отстоящие друг от друга на расстояние d=[n/2], где [ ] - операция взятия целой части, и n - количество элементов исходного массива. На следующих шагах d меняется по закону d=[d/2], при d=1 метод Шелла вырождается в метод стандартного обмена ("Метод Пузырка") 16 МАССИВЫ. Сортировка ВМП

Рассмотрим пример: Дано множество {6,3,4,8,2,9} -> d=[n/2]=[6/2]=3 -> {6,3,4,8,2,9} - сравниваем 6 и 8 -> {6,2,4,8,3,9} - сравниваем 3 и 2, переставляем -> {6,3,4,8,2,9} - сравниваем 4 и 9 -> далее d=[d/2]=[3/2]=1. И алгоритм выродился в метод "Пузырька" В этом примере не очень видна эффективность метода, но представьте, что вы сортируете 1000 элементов. Этот метод обеспечивает более быстрое перебрасывание больших элементов вправо и меньших влево, чем метод "Пузырька" и этим обеспечивает большее быстродействие. Сортировка методом Шелла Домашнее задание (для претендентов на "пятёрку") Написать блок-схему алгоритма и программы сортировки Шелла на Pascal и С с использованием функцийPascalС 17 МАССИВЫ. Сортировка ВМП

МАССИВЫ. Поиск МАССИВЫ. Поиск Поиск необходимой компоненты структуры данных – одна из важнейших задач обработки данных. Для решения задачи поиска необходимо, чтобы данные в памяти ЭВМ были организованы определенным образом. Основные способы организа- ции данных: массивы элементов одинакового типа, структуры данных, линейные списки, деревья, произвольные графы. Алгоритмы поиска существенно зависят от способа организации данных. Рассмотрим алгоритмы поиска в МАССИВАХ: а) последовательный (линейный) поиск -- простейший метод поиска элемента, находящегося в неупорядоченном массиве данных, это последовательный просмотр каждойойого элемента массива, продолжающийся до тех пор, пока не будет найден желаемый элемент. Если просмотрен весь массив, но элемент не найден – значит он отсутствует в массиве. Для последовательного поиска в среднем требуется (N+1)/2 сравнений, а в худшем N. Линейный поиск может применяться и для упорядоченных (отсортированных) массивов, НО эффективнее использовать: б) бинарный (двоичный, дихотомический, логарифмический) поиск – он состоит в разделении упорядоченного массива пополам, определении в какой половине находится искомый элемент, затем это половина снова разделяется пополам и так пока полученное под множество из одного элемента не станет равным искомому. Для бинарного поиска в худшем случае требуется log 2 (N) сравнений. 18 ВМП

МАССИВЫ. Поиск МАССИВЫ. Поиск Pascal Алгоритм функции Написать функцию последовательного поиска 19 ВМП ДЛЯ ВСЁ Заголовок функции LineSearch (mas,key,SIZE) И Л LinSearch = i Exit ИНАЧЕ ТО ЕСЛИ mas[i] = key ЕСЛИ ВСЁ Начало Конец LinSearch = 0 ДЛЯ i:=1 ДО Size Program SeqSearch; (* Последовательный поиск* ) const Size = 5; (* размер массива *) type ar=array[1..Size] of integer; var a:ar { массив элементов } n,k :integer; { к – значение искомого элемента массива } Function LinSearch( mas : ar; key : integer; Size : integer) : integer; (* Функция последовательного поиска *) var i : integer; begin for i:=1 to Size do { перебор элем. массива } if mas[i]=key then { элем. найден - возврат индекса } begin LinSearch:=i; Exit; { возврат номера (индекса) найденного элемента в массиве } end; LinSearch:=0; { просмотрен весь массив, но ключ не найден } end; Begin { Программа вызова функции линейного поиска } writeln('Введите ', Size, ' элемента(ов) массива, после каждойойого элемента -> Enter:'); for n:=1 to Size do readln(a[n]); writeln('Введите значение искомого элемента массива'); readln (k); write('Результат поиска – номер искомого элемента в массиве: '); writeln (LinSearch (a, k, Size)); end. Разобраться как в С передавать имя массива в функцию

МАССИВЫ. Поиск МАССИВЫ. Поиск Pascal Написать функцию бинарного поиска 20 Алгоритм функции Заголовок функции BinSearch (mas,key,Size) И Л BinSearch = i ИНАЧЕТО ЕСЛИ mas[i] = key ЕСЛИ ВСЁ Начало КонецBinSearch = 0 b = 1 e = Size Exit ЕСЛИ mas[i] < key ИНАЧЕ ТО b = i+1e = i-1 ПОКА ВСЁ ПОКА b <= e ВМП Program BSearch; (* Бинарный поиск *) const Size = 5; (* размер массива *) type ar:array[1..Size] of integer; var a : ar; { массив элементов } n,k :integer; { к – значение искомого элемента массива } Function BinSearch(mas : ar; key : integer; Size:integer):integer; {Функц. бинар. поиска } var b, e, i : integer; begin b:=1; e:=Size; { начальные значения границ } while b<=e do {цикл, пока интервал поиска не станет = 0} begin i:=(b+e) div 2; { середина интервала } if mas[i]=key then begin BinSearch:=i; Exit; { элем. найден - возврат индекса } end else if mas[i] < key then b:=i+1 { поиск в правом подинтервале } else e:=i-1; { поиск в левом подинтервале } end; BinSearch:=0; { элемент не найден } end; Begin { Программа вызова функции бинарного поиска } writeln ('Введите ', Size, ' элемента(ов) массива после каждойойого элемента -> Enter:'); for n:=1 to Size do readln(a[n]); writeln ('Введите значение искомого элемента массива'); readln (k); write ('Поcле поиска - номер искомого элемента в массиве: '); writeln (BinSearch (a, k, Size)); end.