Рубрики
Алгоритмы Массивы "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);
Рубрики
Массивы Структуры данных

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

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

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

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

Плюсы

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

Минусы

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

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

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

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