Алгоритм линейного поиска в массиве(Linear Search):
constarray=[1,4,5,8,5,1,2,7,5,2,11];letcount=0;functionlinearSearch(array,item){for(leti=0;i<array.length;i++){// count - количество итерацийcount+=1;if(array[i]===item){// Возвращаем индекс элемента при нахожденииreturni;}}// Возвращаем null если элемент не найденreturnnull;}
Бинарный поиск (Binary Search):
constarray=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];letcount=0;// Реализация с помощью цикла.// Суть: Находим средний элемент массива, если он равен искомогу, то возращаем его индекс.// Если больше, то орезаем правую часть, а если меньше, то левую.functionbinarySearch(array,item){// Позиция первого элементаletstart=0;// Позиция последнего элементаletend=array.length;// Позиция среднего элемента в массивеletmiddle;// Флаг, который показывает найден ли элемент в массивеletfound=false;// Позиция найденого элемента. Если элемент не найден, то возвращаем -1letposition=-1;// Цикл работатет до тех пор либо пока не найден элемент, либо пока стартовая и конечная позиция не поровнялись.while(found===false&&start<=end){// Кол-во итерацийcount+=1;// Внутри цикла высчитываем позицию центрального элементаmiddle=Math.floor((start+end)/2);// Если он равен искомому элементу, то возвращаем позицию элементаif(array[middle]===item){found=true;position=middle;returnposition;}// Если нужный элемент меньше центрального, то тогда нужна левая часть массива, поэтму отсекаем правую.if(item<array[middle]){end=middle-1;}else{// Если больше, то обрезаем всю левую часть массиваstart=middle+1;}}returnposition;}
// Реализация с помощью рукурсии.// item - сам элемент, который ищем// стартовую и конечную позицию передаем через параметрыfunctionrecursiveBinarySearch(array,item,start,end){letmiddle=Math.floor((start+end)/2);count+=1;if(item===array[middle]){returnmiddle;}if(item<array[middle]){// отсеиваем всю правую частьreturnrecursiveBinarySearch(array,item,start,middle-1);}else{// отсеиваем всю левую частьreturnrecursiveBinarySearch(array,item,middle+1,end);}}
Сортировка выбором(Selection Sort):
constarr=[0,3,2,5,6,8,1,9,4,2,1,2,9,6,4,1,7,-1,-5,23,6,2,35,6,3,32,];letcount=0;// Суть: Есть массив неупорядоченных элементов. Находим в цикле минимальный элемент,// затем меняем местами с первым элементом, затем опять пробегаемся по массиву и находим минимальное значение,// но меняем его уже со вторым элементом, затем с 3,4 итд пока не будет отсортирован весь массив.functionselectionSort(array){// Этот цикл просто идет по всем элементамfor(leti=0;i<array.length;i++){letindexMin=i;// Во вложенном цикле ищется минимальный элемент на данную итерациюfor(letj=i+1;j<array.length;j++){if(array[j]<array[indexMin]){indexMin=j;}count+=1;}// Меняем местами элементыlettmp=array[i];array[i]=array[indexMin];array[indexMin]=tmp;}// Возвращаем отсортированный массивreturnarray;}// Кол-во итераций 325. Длина массива 26. Таким образом O(1/2*n*n),// но коэффициенты в оценке сложности алгоритма не учавствуют. Поэтому будет O(n*n)console.log(selectionSort(arr));console.log(arr.length);console.log("count = ",count);
Пузыкрьковая сортировка(Bubble Sort):
constarr=[0,3,2,5,6,8,23,9,4,2,1,2,9,6,4,1,7,-1,-5,23,6,2,35,6,3,32,9,4,2,1,2,9,6,4,1,7,-1,-5,23,9,4,2,1,2,9,6,4,1,7,-1,-5,23,];letcount=0;// Суть: в двойном цикле пробегаемся по всему массиву и сравниваем попарно лежащие элементы.// Если следующий элемент массива меньше чем предыдуший, то мы меняем их местами.// Получается "всплытие" самый большой элемент с каждой итерацией потихоньку всплывает наверх.functionbubbleSort(array){for(leti=0;i<array.length;i++){for(letj=0;j<array.length;j++){if(array[j+1]<array[j]){lettmp=array[j];array[j]=array[j+1];array[j+1]=tmp;}count+=1;}}returnarray;}console.log("length",arr.length);console.log(bubbleSort(arr));// O(n*n)console.log("count = ",count);
Рекурсия(Recursion):
// Рекурсия - это функция, которая вызывает сама себя.// Рекурсия должна всегда иметь условие, при котором вызов функции прекращается,// иначе будет переполнение стека вызова.// Факториал - это n * (n-1) * (n-2) * (n-3) ...constfactorial=(n)=>{if(n===1){return1;}returnn*factorial(n-1);};// Числа фибоначчи - 1,1,2,3,5,8,13,21constfibonachi=(n)=>{if(n===1||n===2){return1;}returnfibonachi(n-1)+fibonachi(n-2);};
Быстрая сортировка(Quick Sort):
// Быстрая сортировка(Quick Sort)constarr=[0,3,2,5,6,8,23,9,4,2,1,2,9,6,4,1,7,-1,-5,23,6,2,35,6,3,32,9,4,2,1,2,9,6,4,1,7,-1,-5,23,9,4,2,1,2,9,6,4,1,7,-1,-5,23,];letcount=0;// Суть: Работает по принципу "Разделяй и властвуй". Мы делим массив на подмассивы и каждый раз рекурсивно.// Выбираем опорный элемент у каждого массива(его можно выбрать случайно, но чаще всего берут центральный).// Пробегаемся по массиву и все элементы, которые по значению меньше опорного - добавляем в один массив,// а все которые больше - в другой. И для каждого из этих массивов выполняется такая же операция.// Так делается до тех пор, пока длина массива не станет равна 1.functionquickSort(array){if(array.length<=1){returnarray;}// pivotIndex - опорный индекс элемента, в нашем случае берем центральный (array.length / 2)letpivotIndex=Math.floor(array.length/2);// pivot - сам опорный элемент, в нашем случае берем центральныйletpivot=array[pivotIndex];// массив с числами, которые меньше чем опорныеletless=[];// массив с числами, которые больше чем опорныеletgreater=[];// Проходимся по всему массиву и наполняем массивы less и greaterfor(leti=0;i<array.length;i++){count+=1;if(i===pivotIndex)continue;if(array[i]<pivot){less.push(array[i]);}else{greater.push(array[i]);}}// Проделывем ту же самую операцию с двумя след. массивамиreturn[...quickSort(less),pivot, ...quickSort(greater)];}
Поиск в ширину в графе(Breadth First Search):
// Граф - это некая абстрактная структура данных, предствляющая собой множество// вершин и набор ребер(т.е соединений между парами вершин).// Ребра бывают однонаправленными и двунаправленными, то есть если из "A" можно попасть только в "B" - это однонаправленность.// А если можно из "A" в "B" и из "B" в "A" - - это двунаправленность.constgraph={};graph.a=["b","c"];graph.b=["f"];graph.c=["d","e"];graph.d=["f"];graph.e=["f"];graph.f=["g"];// Задача: Найти существует ли путь из точки "A" в точку "B" за минималльное кол-во шагов.functionbreadthSearch(graph,start,end){// Очередь(queue) - структура данных состоящая из каких-то элементов.// Основной принцип заключается в том, что элементы всегда добавляются в конец структуры, а// извлекаются из ее начала. Принцип как в очереди в жизни: кто первым пришел на кассу, тот из// нее первый и уходит. Такой принцип называется FIFO - first in first out.letqueue=[];// В очередь сразу добавляем стартовую вершину(start, в данном случае "a")queue.push(start);// Крутим цикл while пока в очереди есть хотя бы один элементwhile(queue.length>0){// Из начала очереди достаем текущую вершинуconstcurrent=queue.shift();// Если по текущей вершине в графе ничего не находится, то присваиваем этой вершине пустой массивif(!graph[current]){graph[current]=[];}// Если в графе по текущей вершине массив содержит конечную точку, то мы завершаем выполнение// программы и возвращаем true. То есть на данном этапе мы обошли весь граф и пришли// к пункту назначения.if(graph[current].includes(end)){returntrue;}else{// Если это условие не отработало, то мы должны добавить в очередь новые вершины.// Поэтому разворачиваем то, что уже находится в очереди в массив и в конец разворачиваем массив// который лежит в графе по текущей вершине.queue=[...queue, ...graph[current]];}}returnfalse;}