Алгоритм и структура данных. 1 Базовый процедурноориентированный алгоритмический язык
 Скачать 1.16 Mb.
|
Минусы:Рекурсивные функции занимают много места. Рекурсивные функции занимают значительный объём памяти во время своего выполнения. Это означает, что при каждом вызове функции в стек будет добавляться новый элемент, который будет занимать место до тех пор, пока функция не завершит работу, найдя ответ, либо пока не дойдёт до выполнения базового условия функции. Рекурсивные функции замедляют программу. Несмотря на то, что уже было сказано про мемоизацию, наш код можно ускорить, если применить циклы for или while. Помимо того, что функция может быть попросту плохо написана, мы также рискуем переполнить стек, что в конечном итоге приведёт к снижению скорости и программным ошибкам. Алгоритмы сортировки и поиска Алгоритмы поиска:Линейный поиск С++ Двоичный (бинарный) поиск С++ Интерполирующий поиск С++ Решето Эратосфена С++ (видео) Поиск подстроки в строке С++ Алгоритмы сортировки:Сортировка выбором С++ (видео) Пузырьковая сортировка С++ (видео) Шейкер сортировка С++ Сортировка вставками С++ (видео) Бинарное дерево в C++ (видео) Линейный поиск Линейный, последовательный поиск — алгоритм нахождения заданного значения произвольной функции на некотором отрезке. Данный алгоритм является простейшим алгоритмом поиска и, в отличие, например, от двоичного поиска, не накладывает никаких ограничений на функцию и имеет простейшую реализацию. Поиск значения функции осуществляется простым сравнением очередного рассматриваемого значения (как правило, поиск происходит слева направо, то есть от меньших значений аргумента к большим) и, если значения совпадают (с той или иной точностью), то поиск считается завершённым. Для нахождения некоторого элемента (ключа) в заданном неупорядоченном массиве используется алгоритм линейного (последовательного) поиска. Он работает как с неотсортированными массивами, так и отсортированными, но для вторых существуют алгоритмы эффективнее линейного поиска. Эту неэффективность компенсируют простая реализация алгоритма и сама возможность применять его к неупорядоченным последовательностям. Здесь, а также при рассмотрении всех других алгоритмов поиска, будем полагать, что в качестве ключа выступает некоторая величина, по мере выполнения алгоритма, сравниваемая именно со значениями элементов массива. Слово «последовательный» содержит в себе основную идею метода. Начиная с первого, все элементы массива последовательно просматриваются и сравниваются с искомым. Если на каком-то шаге текущий элемент окажется равным искомому, тогда элемент считается найденным, и в качестве результата возвращается номер этого элемента, либо другая информация о нем. (Далее, в качестве выходных данных будет выступать номер элемента). Иначе, следуют возвратить что-то, что может оповестить о его отсутствии в пройденной последовательности. #include "stdafx.h" #include #include using namespace std; int i, N; //линейный поиск int LineSearch(int A[], int key) { for (i=0; i if (A[i]==key) return i; return -1; } //главная функция void main() { setlocale(LC_ALL,"Rus"); int key, A[1000]; srand(time(NULL)); cout<<"Размер массива > "; cin>>N; cout<<"Искомый элемент > "; cin>>key; cout<<"Исходный массив: "; for (i=0; i { A[i]=rand()%10; cout< } if (LineSearch(A, key)==-1) cout<<"\nЭлемент не найден"; else cout<<"\nНомер элемента: "< system("pause>>void"); } Двоичный поиск Двоичный (бинарный) поиск (также известен как метод деления пополам или дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в информатике, вычислительной математике и математическом программировании. Двоичный (бинарный) поиск является более эффективным (проверяется асимптотическим анализом алгоритмов) решением в случае, если массив заранее отсортирован. Предположим, что массив из 12-ти элементов отсортирован по возрастанию:  Пользователь задает искомое значение (ключ поиска). Допустим 4. На первой итерации массив делится на две части (ищем средний элемент – midd): (0 + 11) / 2 = 5 (0.5 отбрасываются). Сначала, проверяется значение среднего элемента массива. Если оно совпадает с ключом – алгоритм прекратит работу и программа выведет сообщение, что значение найдено. В нашем случае, ключ не совпадает со значением среднего элемента.  Если ключ меньше значения среднего элемента, алгоритм не будет проводить поиск в той половине массива, которая содержит значения больше ключа (т.е. от среднего элемента до конца массива). Правая граница поиска сместится (midd – 1). Далее снова деление массива на 2.  Ключ снова не равен среднему элементу. Он больше него. Теперь левая граница поиска сместится (midd + 1).  На третьей итерации средний элемент – это ячейка с индексом 3: (3 + 4) / 2 = 3. Он равен ключу. Алгоритм завершает работу. Пузырьковая сортировка Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется перестановка элементов. Проходы по массиву повторяются {\displaystyle N-1}  раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции, как пузырёк в воде — отсюда и название алгоритма).Пузырьковая сортировка — наверно самая простая сортировка, которую я встречал. Обычно она встречается в книгах по программированию и не выходит за ее пределы. Так как она работает намного медленнее, чем другие алгоритмы сортировки. Но благодаря ей появились алгоритмы, которые более эффективнее чем она сама. Из таких сортировок можно отметить шейкерную или как еще ее называют сортировка перемешиванием. Принцип работы пузырьковой сортировки можно описать в три пункта: Прохождение по всему массиву; Сравнивание между собой пар соседних ячеек; Если при сравнении оказывается, что значение ячейки i больше, чем значение ячейки i + 1, то мы меняем значения этих ячеек местами; #include using namespace std; int main() { setlocale(LC_ALL, "rus"); int digitals[10]; // объявили массив на 10 ячеек cout << "Введите 10 чисел для заполнения массива: " << endl; for (int i = 0; i < 10; i++) { cin >> digitals[i]; // "читаем" элементы в массив } for (int i = 0; i < 10; i++) { for (int j = 0; j < 9; j++) { if (digitals[j] > digitals[j + 1]) { int b = digitals[j]; // создали дополнительную переменную digitals[j] = digitals[j + 1]; // меняем местами digitals[j + 1] = b; // значения элементов } } } cout << "Массив в отсортированном виде: "; for (int i = 0; i < 10; i++) { cout << digitals[i] << " "; // выводим элементы массива } system("pause"); return 0; } Сортировка вставкой Сортировка вставками (Insertion Sort) — это простой алгоритм сортировки. Суть его заключается в том что, на каждом шаге алгоритма мы берем один из элементов массива, находим позицию для вставки и вставляем. Стоит отметить что массив из 1-го элемента считается отсортированным. Словесное описание алгоритма звучит довольно сложно, но на деле это самая простая в реализации сортировка. Каждый из нас, не зависимо от рода деятельности, применял алгоритм сортировки, просто не осознавал это:) Например когда сортировали купюры в кошельке — берем 100 рублей и смотрим — идут 10, 50 и 500 рублёвые купюры. Вот как раз между 50 и 500 и вставляем нашу сотню:) Или приведу пример из всех книжек — игра в карточного «Дурака». Когда мы тянем карту из колоды, смотрим на наши разложенные по возрастанию карты и в зависимости от достоинства вытянутой карты помещаем карту в соответствующее место. Для большей наглядности приведу анимацию из википедии. Сортировка вставками (Insertion Sort). Этот алгоритм (как и другие, рассматриваемые на нашем сайте) достаточно прост. Он состоит из двух циклов (один вложен в другой). Первый цикл производит проход по массиву, а второй – перемещение обрабатываемых элементов. Давайте сразу посмотрим, как может выглядеть код такой сортировки, а уже ниже разберем, как он работает. #include using namespace std; int main() { const int N = 10; int a[N] = { 12, 5, 3, 2, 45, 96, 6, 8, 11, 24 }; int buff = 0; // для хранения перемещаемого значения int i, j; // для циклов /************* Начало сортировки *******************/ for (i = 1; i < N; i++) { buff = a[i]; // запомним обрабатываемый элемент // и начнем перемещение элементов слева от него // пока запомненный не окажется меньше чем перемещаемый for (j = i - 1; j >= 0 && a[j] > buff; j--) a[j + 1] = a[j]; a[j + 1] = buff; // и поставим запомненный на его новое место } /************* Конец сортировки *******************/ for (int i = 0; i < N; i++) // вывод отсортированного массива cout << a[i] << '\t'; cout << endl; } Алгоритм Сортировка вставками можно описать следующими позициями: Запомнить во временную переменную ( buff в примере) значение текущего элемента массива; Пока элементы слева от запомненного значения больше чем запомненное – перемещаем их на позицию вправо. Получается, что предыдущий элемент займет ячейку запомненного. А тот, что стоит перед предыдущим – переместится в свою очередь на место предыдущего. И так элементы будут двигаться друг за дружкой. Движение элементов заканчивается, если очередной элемент, который нужно сдвинуть, оказывается по значению меньше, чем тот, что запомнили во временную переменную в начале цикла. Цикл берет следующий элемент, и опять сдвигает все, которые расположены перед ним и большие по значению. Сортировка выбором Шаги алгоритма: находим номер минимального значения в текущем списке производим обмен этого значения со значением первой неотсортированной позиции (обмен не нужен, если минимальный элемент уже находится на данной позиции) теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы Просто и незатейливо — проходим по массиву в поисках максимального элемента. Найденный максимум меняем местами с последним элементом. Неотсортированная часть массива уменьшилась на один элемент (не включает последний элемент, куда мы переставили найденный максимум). К этой неотсортированной части применяем те же действия — находим максимум и ставим его на последнее место в неотсортированной части массива. И так продолжаем до тех пор, пока неотсортированная часть массива не уменьшится до одного элемента. Смысл Сортировки выбором (Selection Sort)состоит в поиске минимального значения элемента в массиве, и перемещения этого значения в начало массива. Нужно сразу оговориться, что в данном случае можно назвать “началом” массива (куда перемещается найденное минимальное значение). “Начало” в алгоритме Сортировка выбором с каждым шагом цикла смещается в сторону хвоста массива. Поэтому на первой итерации цикла, найденное минимальное значение меняется местами со значением в нулевой ячейке массива. На второй итерации “начало” уже будет указывать на следующую (первую) ячейку и так далее. По факту получается простой обмен местами значений ячеек массива. При таком обмене значениями не нужен сдвиг (перезапись) всех элементов массива, чтобы записать минимальное значение в соответствующую ячейку. То есть алгоритм Сортировка выбором не требует использования дополнительной памяти. Перезапись значений происходит сразу после нахождения минимального значения в массиве. #include using namespace std; int main() { const int N = 10; int a[N] = { 1, 25, 6, 32, 43, 5, 96, 23, 4, 55 }; int min = 0; // для записи минимального значения int buf = 0; // для обмена значениями /*********** Начало сортировки **************/ for (int i = 0; i < N; i++) { min = i; // запомним номер текущей ячейки, как ячейки с минимальным значением // в цикле найдем реальный номер ячейки с минимальным значением for (int j = i + 1; j < N; j++) min = ( a[j] < a[min] ) ? j : min; // cделаем перестановку этого элемента, поменяв его местами с текущим if (i != min) { buf = a[i]; a[i] = a[min]; a[min] = buf; } } /*********** Конец сортировки **************/ for (int i = 0; i < N; i++) //Вывод отсортированного массива cout << a[i] << '\t'; cout << endl; } Сортировка подсчётом Сортировка подсчетом — простейший способ упорядочить массив за линейное время. Применять его можно только для целых чисел, небольшого диапазона, т.к. он требует O(M) дополнительной памяти, где M — ширина диапазона сортируемых чисел. Алгоритм особо эффективен когда мы сортируем большое количество чисел, значения которых имеют небольшой разброс — например: массив из 1000000 целых чисел, которые принимают значения от 0 до 1000 . Напомню, что в прошлый раз мы рассматривали алгоритм поразрядной сортировки, также работающий за линейное время, но требующий O(N) дополнительной памяти, где N — количество сортируемых чисел. В сортировке подсчетом элементы массива не сравниваются друг с другом. Эксплуатируется следующая идея: пусть, нам дан массив Array из N чисел в диапазоне от 1 до 1000 ; подсчитаем сколько раз встречается каждый элемент массива — для этого: создадим вспомогательный массив Counts из 1000 счетчиков, заполним его нулями; обойдем Array, при этом для каждого его элемента увеличим счетчик: Counts[Value] = Counts[Value] + 1; Обойдем массив Counts , при этом для каждого его i-того элемента выведем значение i столько раз, сколько он встретился в исходном массиве. Индекс i при этом соответствует значению числа исходного массива. Поразрядная сортировка ПрименениеCортируемые числа имеют диапазон возможных целых положительных значений, который достаточно мал по сравнению с сортируемым множеством. Алгоритм1) Пусть есть массив А из N элементов, включающий числа в диапазонее от 0 до k-1 (то есть всего максимум k различных значений). 2) Создать вспомогательный массм C[0..k-1], состоящий из нулей (его можно назвать массивом счетчиков). 3) Последовательно прочитать элементы массива A и для каждого A[i] увеличить С[A[i]] на единицу. В итоге мы получим массив C, в котором каждый элемент C[i] равен числу встречаемости значения i в исходном массиве A, индекс i равен значению элемента массива A. 4) Проходясь по массиву С и для каждого j от 0 до k-1 в новый массив (или тот же массив A) последовательно записать число j C[j] раз. ПримерПусть имеет массив А = {2, 5, 6, 9, 4, 1, 8, 2, 9, 8, 4, 1, 4, 1} Диапазон чисел - от 0 до 9, то есть всего 10 различных значений 1. Создаем массив С из 10 нулевых элементов 2. Проходим по массиву А и увеличиваем на 1 элемент C[A[i]] 3. Полученный массив С = {0, 3, 2, 0, 3, 1, 1, 0, 2, 2} Данный метод можно применять и при наличии отрицательных значений, в этом случае для подсчета количества элементов равных самому минимальному (Amin) будем использовать элемент С[0], подсчет i-го элемента массива A будет производиться следующим образом C[A[i] - Amin]. Пример реализации алгоритмаПусть все n чисeл массива А натуральные и лежат в промежутке от 1 до 100. 1) Создадим массив размера 100, в котором будем хранить на k-ом месте, сколько раз число k встретилось в этом массиве. 2) Пройдемся по всем числам исходного массива и увеличим соответствующее значение массива на 1. 3) После того, как мы посчитали, сколько раз каждое число встретилось, можно просто пройтись по этому массиву и вывести 1 столько раз, сколько встретилась 1, вывести 2 столько раз, сколько встретилась 2, и так далее. Алгоритм сортировки слиянием Сортировка слиянием (англ. mergesort) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи. Для решения задачи сортировки эти три этапа выглядят так: Сортируемый массив разбивается на две части примерно одинакового размера; Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом; Два упорядоченных массива половинного размера соединяются в один. 1.1. — 2.1. Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы (любой массив длины 1 можно считать упорядоченным). 3.1. Соединение двух упорядоченных массивов в один. Основную идею слияния двух отсортированных массивов можно объяснить на следующем примере. Пусть мы имеем два уже отсортированных по возрастанию подмассива. Тогда: 3.2. Слияние двух подмассивов в третий результирующий массив. На каждом шаге мы берём меньший из двух первых элементов подмассивов и записываем его в результирующий массив. Счётчики номеров элементов результирующего массива и подмассива, из которого был взят элемент, увеличиваем на 1. 3.3. «Прицепление» остатка. Когда один из подмассивов закончился, мы добавляем все оставшиеся элементы второго подмассива в результирующий массив. Быстрая сортировка Быстрая сортировка относится к алгоритмам «разделяй и властвуй». Алгоритм состоит из трёх шагов: Выбрать элемент из массива. Назовём его опорным. Разбиение: перераспределение элементов в массиве таким образом, что элементы, меньшие опорного, помещаются перед ним, а большие или равные - после. Рекурсивно применить первые два шага к двум подмассивам слева и справа от опорного элемента. Рекурсия не применяется к массиву, в котором только один элемент или отсутствуют элементы.
Сортировка кучей Сортировка кучей - популярный и эффективный алгоритм сортировки в компьютерном программировании. Чтобы научиться писать алгоритм сортировки кучей, требуется знание двух типов структур данных - массивов и деревьев. Необходимо отсортировать массив AA, размером nn. Построим на базе этого массива за O(n)O(n) кучу для максимума. Так как максимальный элемент находится в корне, то если поменять его местами с A[n−1]A[n−1], он встанет на своё место. Далее вызовем процедуру siftDown(0)siftDown(0), предварительно уменьшив heapSizeheapSize на 11. Она за O(logn)O(logn) просеет A[0]A[0] на нужное место и сформирует новую кучу (так как мы уменьшили её размер, то куча располагается с A[0]A[0] по A[n−2]A[n−2], а элемент A[n−1]A[n−1] находится на своём месте). Повторим эту процедуру для новой кучи, только корень будет менять местами не с A[n−1]A[n−1], а с A[n−2]A[n−2]. Делая аналогичные действия, пока heapSizeheapSize не станет равен 11, мы будем ставить наибольшее из оставшихся чисел в конец не отсортированной части. Очевидно, что таким образом, мы получим отсортированный массив. |
