Basic search and sort algorithms

Question 1

Алгоритмы поиска

Answer 1

1. Алгоритм линейного поиска
2. Алгоритм бинарного поиска

Question 2

Алгоритм линейного поиска

Answer 2

Сложность данного алгоритма: линейное время или O(n).
Простой алгоритм перебора элементов до момента совпадения выбранного элемента с искомым.

const array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

function linearSearch(array, item) {
for (let i = 0; i < array.length; i++) {
if (array[i] === item) {
return i;
}
}
return -1;
}

Question 3

Алгоритм бинарного поиска

Answer 3

Бинарный (или двоичный) поиск — это алгоритм, при котором массив данных будет последовательно делиться пополам до тех пор, пока не будет обнаружен искомый элемент.

Важное замечание: данный алгоритм будет работать только для отсортированного массива.

Бинарный поиск может быть реализован следующим образом:
0. Берём исходный массив отсортированных данных (например, по возрастанию).
1. Делим его на две части и находим середину.
2. Сравниваем элемент в середине с искомым элементом.
3. Если искомое число меньше этого центрального элемента — продолжаем искать элемент в левой части массива. Для этого мы делим левую часть массива на 2 части. Если искомый элемент больше центрального элемента, то мы отбрасываем левую часть массива и продолжаем поиск в правой.
И повторяем данную процедуру до тех пор, пока не найдем искомый элемент. Как только мы его нашли, то возвращаем индекс в массиве, по которому он находится. Если же данный элемент не будет найден, то возвращаем -1.

Сложность данного алгоритма О(log n).

const arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

const binarySearch = (arr, value) => {
let start = 0;
let end = arr.length - 1;
while (start <= end) {
let middle = Math.floor((start + end) / 2);
if (value === arr[middle] ) return middle;
if (value < arr[middle]) {
end = middle - 1;
} else {
start = middle + 1;
}
}
return -1;
};

Question 4

Алгоритмы сортировки

Answer 4

1. Сортировка пузырьком Bubble Sort
2. Быстрая сортировка Хоара Quick sort
3. Сортировка выбором Selection sort
4. Сортировка вставками Insertion sort
5. Сортировка слиянием Merge sort

Question 5

Сортировка пузырьком Bubble Sort

Answer 5

При сортировке элементы с большими значениями оказываются в конце списка, а с меньшими остаются в начале. То есть элементы массива как бы «всплывают» до нужной позиции.

function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
if (arr[j] > arr[j + 1]) {
let tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
return arr;
}
Сложность в наилучшем случае — O(n), в наихудшем — O(n^2).

Question 6

Быстрая сортировка Хоара Quick sort

Answer 6

Алгоритм будет сводиться к следующим шагам:
1. Выбираем элемент из массива и считаем его опорным (в англоязычной литературе его называют pivot).
2. Сортируем элементы в массиве таким образом, чтобы элементы меньше опорного размещались в подмассиве перед ним, а большие или равные — в подмассиве после.
3. Рекурсивно применяем первые два шага к двум подмассивам слева и справа от опорного элемента. Т.е. дробим наш массив на подмассивы и сортируем их относительно опорного элемента, пока в этих подмассивах не останется по одному элементу или меньше. Рекурсия не применяется к массиву, в котором только один элемент или отсутствуют элементы. Это как раз и будет базовым условием, при котором мы прервем рекурсию.

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++) {
if (i === pivotIndex) continue;
if (arr[i] < pivot) {
less.push(arr[i]);
} else {
greater.push(arr[i]);
}
}
return […quickSort(less), pivot, …quickSort(greater)];
}

Быстрая сортировка в среднем и лучшем случае выполняется за Θ(n * log(n)) и Ω(n * log(n)) соответственно.

Question 7

Сортировка выбором Selection sort

Answer 7

Временная сложность в наилучшем и наихудшем случае — O(n^2).

Основывается на делении массива на 2 части: отсортированную и не отсортированную.

Шаги алгоритма:

1. Находим номер минимального значения в текущем списке;
2. Производим обмен этого значения со значением первой неотсортированной позиции (обмен не нужен, если минимальный элемент уже находится на данной позиции);
3. Теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы.

function selectionSort(arr, compare = defaultCompare) {
const { length } = arr;
let minIndex;
for (let i = 0; i < length - 1; i++) {
minIndex = i;
for (let j = i; j < length; j++) {
if (compare(arr[minIndex], arr[j]) === Compare.BIGGER_THAN) {
minIndex = j;
}
}
if (i !== minIndex) {
swap(arr, i, minIndex);
}
}
return arr;
}

Question 8

Сортировка вставками Insertion sort

Answer 8

Алгоритм строит финальный отсортированный массив по одному значению за раз. Основывается на делении массива на 2 части: отсортированную и не отсортированную.

Эффективность: O(n^2).

Процесс выглядит следующим образом:

1. Предполагаем, что первый элемент уже отсортирован.
2. Сравниваем первый элемент со вторым: должно ли второе значение остаться на месте или же оно должно быть вставлено перед первым значением?
3. Далее аналогичное сравнение делается для третьего значения: должно ли оно быть вставлено на первую, вторую или третью позицию? И так далее.

function insertionSort(arr, compare = defaultCompare) {
const { length } = arr;
let temp;
for (let i = 1; i < length; i++) {
let j = i;
temp = arr[i];
while (j > 0 && compare(arr[j - 1], temp) === Compare.BIGGER_THAN) {
arr[j] = arr[j - 1];
j–;
}
arr[j] = temp;
}
return arr;
}

Question 9

Сортировка слиянием Merge sort

Answer 9

Временная сложность в наилучшем и наихудшем случае — O(n log n).
Для списков более 10 элементов выполняется быстрее алгоритмов сортировки пузырьком, вставками и выбором, но требует больше оперативной памяти, т.к. память под не отсортированные списки не освобождается.

Один из алгоритмов «разделяй и властвуй»). Делит исходный массив на более мелкие массивы, пока каждый маленький массив не будет содержать всего одну позицию, а затем сливает маленькие массивы в более крупный и отсортированный.

Для решения задачи сортировки эти три этапа выглядят так:
1. Сортируемый массив разбивается на две части примерно одинакового размера;
2. Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом;
3. Два упорядоченных массива половинного размера соединяются в один.

function mergeSort(arr, compare = defaultCompare) {
if (arr.length > 1) {
const { length } = arr;
const middle = Math.floor(length / 2);
const left = mergeSort(arr.slice(0, middle), compare);
const right = mergeSort(arr.slice(middle, length), compare);
arr = merge(left, right, compare);
}
return arr;
}
function merge(left, right, compare) {
let i = 0;
let j = 0;
const result = [];
while (i < left.length && j < right.length) {
result.push(compare(left[i], right[j]) === Compare.LESS_THAN ? left[i++] : right[j++]);
}
return result.concat(i < left.length ? left.slice(i) : right.slice(j));
}

Question 10

Решето Эратосфена (поиск простых чисел)

Answer 10

Простые числа делятся только на 1 и на себя.
Простые числа начинаются с 2х. Отрицательные числа не являются простыми.
Цикл-решето от 2 до num:

function isPrime(num) {
let primes = [];
let restNums = [];

for (let i = 2; i <= num; i++) {
if (!restNums[i]) {
primes.push(i);
for (let k = i * 2; k <= num; k += i)
restNums[k] = true;
}
}
return primes;
}

Самый эффективный алгоритм проверки числа на простоту (за счет поиска не до num, а до его квадратного корня):

function isPrime(num) {
if (num < 2) {
return false;
}

let sqrtNum = Math.sqrt(num);

for (i = 2; i <= sqrtNum; i++) {
if (num % i === 0) {
return false;
}
}
return true;
}