Рубрика: Основы Программирования

O(log₂n*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)

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

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

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)