ВАЖНО
- элементы всегда добавляются в конец структуры
- элементы всегда извлекаются из конца структуры
ПРИМЕР
стопка бумаги
- добавляем сверху
- забираем сверху
структура данных (тип, класс, даже лучше сказать интерфейс), которая создана, чтобы содержать в себе некоторое количество объектов (в зависимости от языка и терминологии они должны быть одного типа или могут быть разных типов).
Различные типы коллекций могут быть статическими или динамическими, т.е. изменять свой размер или оставаться постоянными, могут быть упорядоченными (точнее учитывающими порядок элементов) и неупорядоченными (соответственно не учитывающими).
стопка бумаги
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);
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)
O(k*n*n)=>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 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);