Skip to content

Instantly share code, notes, and snippets.

@chekit
Last active November 2, 2023 00:58
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save chekit/d2cc00b4cb12eb2a33843f2035775403 to your computer and use it in GitHub Desktop.
Save chekit/d2cc00b4cb12eb2a33843f2035775403 to your computer and use it in GitHub Desktop.
Some code from the book via JavaScript
/*
* Алгоритм сортировки выбором
* Сортировка массива по возрастанию
*/
// Функция поиска индекса наименьшего элемента массива
let smallestIndex = function (arr) {
let ind = 0;
arr.reduce((init, item, index) => {
if (init >= item) {
init = item;
ind = index;
}
return init;
}, arr[0]);
return ind;
}
// Функция сортировки выбором на основе предыдущей функции
let selectionSort = function (arr) {
let newArr = [];
while(arr.length) {
let si = smallestIndex(arr);
newArr.push(arr.splice(si, 1)[0]);
}
return newArr;
};
// Пример с простым массивом: http://jsbin.com/vosube/edit?js,console
// Пример с массивом объектов: http://jsbin.com/wayudum/edit?js,console
/**
* Быстрая сортировка
*/
function quickSort(list) {
if (list.length < 2) return list;
const less = [];
const more = [];
const pivot = list[Math.round(list.length / 2)];
for (let i = 0; i < list.length; i++) {
if (list[i] < pivot) {
less.push(list[i]);
} else if (list[i] > pivot) {
more.push(list[i]);
}
}
return [...quickSort(less), pivot, ...quickSort(more)];
}
// Пример: http://jsbin.com/majafew/edit?js,console
/**
* Поиск в ширину
* - поиск в ширину позволяет определить существует ли путь из A в B
*/
// Пример: http://jsbin.com/zusiqo/edit?js,console
// Пример с рекурсией: http://jsbin.com/qisuviv/edit?js,console
// Бинарный поиск
// https://hackernoon.com/programming-with-js-binary-search-aaf86cef9cb3
// Пример: http://jsbin.com/lufatay/edit?js,console
function binarySearch (list, value) {
// initial values for start, middle and end
let start = 0
let stop = list.length - 1
let middle = Math.floor((start + stop) / 2)
// While the middle is not what we're looking for and the list does not have a single item
while (list[middle] !== value && start < stop) {
if (value < list[middle]) {
stop = middle - 1
} else {
start = middle + 1
}
// recalculate middle on every iteration
middle = Math.floor((start + stop) / 2)
}
// if the current middle item is what we're looking for return it's index, else return -1
return (list[middle] !== value) ? -1 : middle
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment