Рубрики
JavaScript основы JavaScript Поиск Массивы

Найти в массиве

Найти в массиве — представлены различные методы по поиску элементов в массиве в языке JavaScript, особенно с использованием лямда-выражений.

Найти в Массиве на языке JavaScript
Поиск в Массиве
Рубрики
C# Массивы С# структуры данных "Массивы" Структуры данных

Array

Array или массив — абстрактный базовый тип (класс) для всех типов массивов

  • можно использовать свойства и другие члены класса, входящие в Array
С# C и C++
реальные объект адресуемые области непрерывной памяти
массивы в языках представляют
Array в С#
Array в С#
Рубрики
Массивы Структуры Данных "Списки"

Структура Данных «связный список»

ВАЖНО

каждый отдельный элемент связного списка занимает отдельное место в памяти

каждый предыдущий элемент хранит ссылку на следующий элемент, который лежит в списке.

Плюсы

является то, что мы можем мгновенно добавлять в конец или в начало списка

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

Минусы

Чтобы получить какой-то элемент — нам с самого начала списка надо итерироваться и сравнивать

ОТЛИЧИЕ МАССИВ и СПИСКИ

Массивы используем там, где

  • часто обращаемся к каким то данным
  • не часто нужно изменять размер массива.

Списки используем там, где

  • если редко обращаемся к каким-то данным
  • часто его дополняем
Рубрики
Алгоритмы Массивы "cортировка"

Массивы «Быстрая сортировка» (Хоара)

O(log2n*n)
самый быстрый

разделяй и властвуй

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

Для каждого из этих массивов выполняется точно такая же операция. В каждой из этих массивов выбирается опорный элемент и происходит сортировка и так происходит до тех пор, пока длина массива становится равна единице (именно это условие и будет базовым случаем выхода из рекурсии).

И после этих операций эти маленькие массивы склеиваются в один большой.

const arr=[1,4,5,8,51,2,7,5,5,2,11]//[0,1,1,2,3....]
let cnt=0;

function quickSort(arr){
 if (arr.length<=1){
  return arr
}
let pivotIndex = Math.floor(arr.length/2);
let pivot=arr[pivotIndex]
let less=[]
let greater=[]

for(let i=0;i<arr.length;i++){
 cnt+=1
 if(i===pivotIndex)
  continue;
 if(arr[i]<pivot){
  less.push(arr[i])
} else {
 greater.push(arr[i])
}
return [...quickSort(less),pivot,...quickSort(greater)]
}

console.log(quickSort(arr))
console.log(cnt);
Рубрики
Алгоритмы Массивы "cортировка"

Массивы «пузырьковая сортировка»

O(n*n)
Не эффективная сортировка

  • пробегаемся по всему массиву и сравниваем попарно лежащие элементы.
  • Если следующий элемент массива меньше чем предыдущий, то мы меняем их местами и получается в своего рода всплытие — самый большой элемент потихоньку всплывает наверх
const arr=[1,4,5,8,51,2,7,5,5,2,11]//[0,1,1,2,3....]
let cnt=0;

function bubleSort(arr){
for (let i = 0; i< arr.length;i++){
 for (let j = 0; j < arr.length; j++){
  if(arr[j+1] < arr[j]){
   let tmp = arr[j]
   arr[j] = arr[j+1]
   arr[j+1] = tmp
}
cnt+=1
}
}
return arr;
}
console.log('length',arr.length);
console.log(bubbleSort(arr))
console.log('count=',cnt)
  
Рубрики
Алгоритмы Массивы "cортировка"

Массивы «cортировка выбора»

O(k*n*n)=>O(n*n)

Процесс выполнения

есть массив не упорядоченных элементов

  1. мы в цикле находим минимальный элемент
  2. меняем местами найденный минимальный элемент с первым элементом
  3. опять ищем минимальный элемент и меняем уже со вторым элементом и так далее пока не будет отсортирован массив
const arr=[1,4,5,8,51,2,7,5,5,2,11]//[0,1,1,2,3....]
let cnt=0;

function selectionSort(arr){
 for (let i = 0; i < arr.length; i++) {
  let indexMin = i
  for (let j=i+1; j < arr.length; j++){
   if (arr[i] < arr[indexMin]){
 indexMin=j
}
}
let tmp = arr[i];
arr[i]=arr[indexMin]
arr[indexMin]=tmp
}
}
console.log(selectionSort(arr))
console.log(arr.length)//))O(k*n*n)
console.log('count = ', count)
Рубрики
Алгоритмы Массивы "поиск"

Массивы «Бинарный поиск»

O(log2n)
для массива из 1000 элементов
O(log21000)

время сортировки массива более длительнее чем работа линейного поиска

требование
массив отсортирован по порядку

Процесс выполнения

смотрим по середине символ
— если символ идет раньше, которую мы открыли, то будем
рассматривать левую часть
— если символ идет позже, которую мы открыли, то будем
рассматривать правую часть
таким образом каждый раз мы отсеиваем ровно половину в массиве пока не найдем элемент

количество итераций — счетчик выполнения оператора for

const arr=[1,4,5,8,51,2,7,5,5,2,11]
let cnt = 0;

function binarySearch(arr, item){
 let start = 0
 let end = arr.length;
 let middle;
 let found = false;
 let position = -1;
 while (found === false && start <= end){
  cnt+=1
  middle = Math.floor((start+end)/2);
  if (arr[middle] === item){
   found = true
   position = middle
   return position;
  }
  if (item < arr[middle]){
   end = middle-1
  } else {
   start = middle+1
  }
  return position;
}
console.log(binarySearch(arr,0))
console.log(cnt);

  • рекурсивный код более локаничный
cnt=0;
function recursiveBinarySearch(arr,item,start,end){
  let middle = Math.floor((start+end)/2);
  cnt+=1
  if (item == arr[middle]){
   return middle;
  }
  if (item < arr[middle]){
   return recursiveBinarySearch(arr,item,start,middle-1)
} else {
  return recursiveBinarySearch(arr,item,middle+1,end)
 }
}
console.log(recursiveBinarySearch(arr,12,0,arr.length))
console.log(cnt);
Рубрики
Алгоритмы Массивы "поиск"

Массивы «линейный поиск»

последовательно сравниваем с тем элементом, который ищем

массив из n элементов
O(n)
n — количество итераций в массиве

для массива из 1000 элементов
O(1000)

лучший случай
элемент находим в начале списка за одну операцию

худший случай
элемент находим в конце списка

сложность
нам необходимо пройтись по каждому элементу, который в этом списке находится

const arr=[1,4,5,8,51,2,7,5,5,2,11]
let cnt = 0;//количество итераций
function linearSearch(arr, item){
 for (let i =0; i< arr.length; i++){
  cnt+=1;
  if (arr[i] === item) {
   return i;
  }
 }
 return null;
}
console.log(linearSearch(arr, 11));
console.log('count = ', count);
Рубрики
Массивы Структуры данных

Структуры Данных «Массивы»

Последовательный набор каких-то объектов

Отличительная особенность

  • занимает конкретный участок в памяти
  • изначально определено, какое количество элементов в нём будет находится (это как плюс, так и минус одновременно)

Плюсы

Мы знаем позицию каждого элемента и можем получить его за константное время т.е. мгновенно

Минусы

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

Поиск в Массиве

  • линейный поиск
  • бинарный поиск

Сортировка в Массиве