Рубрика: Структуры данных

Рубрики
Алгоритмы Массивы "cортировка"

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

  • Автор записи Автор: bo52
  • Дата записи 05.01.2020

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ортировка выбора»

  • Автор записи Автор: bo52
  • Дата записи 05.01.2020

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

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

  • Автор записи Автор: bo52
  • Дата записи 04.01.2020

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

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

  • Автор записи Автор: bo52
  • Дата записи 03.01.2020

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

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

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

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

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

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

Плюсы

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

Минусы

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

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

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

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