Sorting Algorithms Flashcards
В чём идея сортировки слиянием
Основной принцип сортировки слиянием такой: делим массив пополам, каждый из них сортируем слиянием и потом соединяем оба массива. Каждый разделённый массив тоже нарезаем на два подмассива до тех пор, пока в каждом не окажется по одному элементу.
Сколько времени занимает сортировка слиянием?
Главное преимущество сортировки слиянием — она работает всегда с одной и той же скоростью на любых массивах O(n log n). Тк в этой сортировке используется рекурсия, то можно запомнить ее с помощью формулы T(n) = n/2 + O(n), где n - размер массива
Реализуйте просто пример сортировки слиянием на JavaScript
// слияние массивов с одновременной сортировкой
// на вход подаются уже отсортированные левая и правая части
function merge(left, right) {
// сюда будем складывать результат
let arr = []
// пока в каждой части есть хотя бы один элемент — выполняем цикл
while (left.length && right.length) {
// смотрим на наименьший элемент из тех, что стоят в начале обоих массивов
if (left[0] < right[0]) {
// если слева был элемент меньше —
// забираем его оттуда и отправляем в массив с результатом
arr.push(left.shift())
} else {
// в противном случае забираем элемент из правой части
arr.push(right.shift())
}
}
// выводим результат слияния отсортированных массивов
console.log(‘Результат: ‘ + arr);
// возвращаем отсортированный массив и добавляем к нему в конец отсортированный остаток от какой-либо части, если её так и не обработали в цикле return [ ...arr, ...left, ...right ] }
// делим массивы пополам до тех пор, пока в них не останется элементов
function mergeSort(array) {
// находим середину
const half = array.length / 2
// если в нашем массиве и так меньше двух элементов — возвращаем его
if(array.length < 2){
return array
}
// делим массив на две части и левую отправляем в новый массив
const left = array.splice(0, half)
// выводим промежуточный результат
console.log(‘Слева:’ + left);
console.log(‘Справа:’ + array);
// запускаем рекурсию и отдаём ей правую и левую части массива
return merge(mergeSort(left),mergeSort(array))
}
// исходный массив
array = [3, 5, 1, 6, 9, 8, 2];
console.log(mergeSort(array));
Какие плюсы есть у быстрой сортировки? (Quick Sort)
- это один из самых быстрых алгоритмов, когда мы заранее ничего не знаем про массивы, с которыми придётся работать;
- алгоритм настолько прост, что его легко написать на любом языке программирования
- быструю сортировку легко распараллелить и разбить на отдельные процессы;
- алгоритм работает на данных с последовательным доступом, когда мы не можем в любой момент вернуться в начало, а должны работать с данными только в одном порядке.
Какова скорость быстрой сортировки (QuickSort)
Best and Average: Ω(n log(n)) иногда можно встретить лучшее время, как O(n)
Worst O(n^2)
Реализуйте пример быстрой сортировки (QuickSort)
// исходный массив
var arr = [3,14,1,7,9,8,11,6,4,2]
// рекурсивная функция быстрой сортировки
// на вход получает массив, который нужно отсортировать
function quickSort(arr) {
// если длина массива меньше двух (в нём один элемент или нет их вообще)
// то возвращаем массив как есть, без обработки
if (arr.length < 2) return arr;
// берём первый элемент массива как опорный
let pivot = arr[0];
// будущие левые и правые части массива
const left = [];
const right = [];
// перебираем весь массив по порядку
for (let i = 1; i < arr.length; i++) {
// если опорный элемент больше текущего
if (pivot > arr[i]) {
// то добавляем текущий элемент в левую часть
left.push(arr[i]);
// в противном случае
} else {
// добавляем текущий элемент в правую часть
right.push(arr[i]);
}
// выводим текущее состояние массива в консоль // это необязательный шаг, он здесь для наглядности console.log(arr); } // отправляем на рекурсивную обработку левую и правую части массива // и возвращаем результат в виде двух склеенных массивов return quickSort(left).concat(pivot, quickSort(right)); }
// запускаем сортировку
quickSort(arr);
Какова скорость у Пузырьковой сортировки? Bubble Sort
В программировании эффективность работы алгоритма в зависимости от количества элементов n обозначают так: O (n). В среднем и худшем O (n^2). Этот алгоритм считается учебным и в чистом виде на практике почти не применяется. Дело в том, что среднее количество проверок и перестановок в массиве — это количество элементов в квадрате. Например, для массива из 10 элементов потребуется 100 проверок, а для массива из 100 элементов — уже в сто раз больше, 10 000 проверок.
Принцип работы Пузырьковой сортировки? Bubble Sort
- Берём самый первый элемент массива и сравниваем его со вторым. Если первый больше второго — меняем их местами с первым, если нет — ничего не делаем.
- Затем берём второй элемент массива и сравниваем его со следующим — третьим. Если второй больше третьего — меняем их местами, если нет — ничего не делаем.
- Проходим так до предпоследнего элемента, сравниваем его с последним и ставим наибольший из них в конец массива. Всё, мы нашли самое большое число в массиве и поставили его на своё место.
- Возвращаемся в начало алгоритма и делаем всё снова точно так же, начиная с первого и второго элемента. Только теперь даём себе задание не проверять последний элемент — мы знаем, что теперь в конце массива самый большой элемент.
- Когда закончим очередной проход — уменьшаем значение финальной позиции, до которой проверяем, и снова начинаем сначала.
- Так делаем до тех пор, пока у нас не останется один элемент.
Покажите простую реализацию пузырьковой сортировки
// исходный массив
var arr = [3,1,9,8,11,6]
// определяем количество прогонов
// перебирать будем всё до предпоследнего элемента, каждый раз сдвигая его ближе к началу
for (let j = arr.length - 1; j > 0; j–) {
// основной цикл внутри каждого прогона
// перебираем все элементы от первого до последнего в прогоне, который мы определили выше
for (let i = 0; i < j; i++) {
// если текущий элемент больше следующего
if (arr[i] > arr[i + 1]) {
// запоминаем значение текущего элемента
let temp = arr[i];
// записываем на его место значение следующего
arr[i] = arr[i + 1];
// а на место следующего ставим значение текущего, тем самым меняем их местами
arr[i + 1] = temp;
}
// выводим текущее состояние массива в консоль
// это необязательный шаг, он здесь для наглядности
console.log(arr);
}
}
Как работает алгоритм сортировки расчёской
На первом шаге мы находим длину массива (например, 10 элементов) и делим её на 1,247. Допустим, после округления у нас получилось число 8. Теперь мы проходим первый цикл пузырьковой сортировки, только сравнивая не 1 и 2, 2 и 3, а сразу 1 и 8, 2 и 9, 3 и 10. Это отправит самые большие числа, если они есть в начале, в самый конец. Всего на первом шаге будет три сравнения.
На втором шаге мы берём число 8 из предыдущего этапа и снова делим его на 1,247, получая число 6. Теперь мы снова проходим весь массив и сравниваем так:
1 и 6
2 и 7
3 и 8
4 и 9
5 и 10
Уже получилось 5 перестановок и снова крупные числа улетели поближе к концу массива.
Так мы уменьшаем размер шага до тех пор, пока он не станет меньше единицы — к этому моменту массив будет полностью отсортирован.
🤔 Сортировка расчёской называется так из-за того, что мы как бы расчёсываем массив сначала широким гребнем (большой шаг), потом гребнем поменьше (шаг поменьше). В конце шаг равен единице, как в пузырьковой сортировке.
Какова скорость сортировки расчёской (Comb sort)
Time Complexity: Average case time complexity of the algorithm is ?(N2/2p), where p is the number of increments. The worst-case complexity of this algorithm is O(n2) and the Best Case complexity is O(nlogn).
Сортировка расчёской на JavaScript
// исходный массив
var arr = [3,14,1,7,9,8,11,6,4,2]
// получаем длину массива
const l = arr.length;
// оптимальное число для вычисления шага сравнения
const factor = 1.247;
// получаем точный шаг сравнения
let gapFactor = l / factor;
// пока шаг больше единицы
while (gapFactor > 1) {
// округляем шаг до целого
const gap = Math.round(gapFactor);
// и организуем цикл как в пузырьковой сортировке
for (let i = 0, j = gap; j < l; i++, j++) {
// если сначала идёт большое число
if (arr[i] > arr[j]) {
// меняем их местами
[arr[i], arr[j]] = [arr[j], arr[i]];
}
// выводим текущее состояние массива в консоль
// это необязательный шаг, он здесь для наглядности
console.log(arr);
}
// в конце цикла рассчитываем новый шаг
gapFactor = gapFactor / factor;
}
Когда лучше всего работает сортировка подсчетом? Counting sort
Сортировка подсчётом лучше всего работает при таких условиях:
массив очень большой — значений много;
эти значения лежат в известном нам диапазоне (например, это диапазон работы какого-то датчика);
диапазон намного меньше, чем размер массива, то есть единицы данных могут повторяться.
Принцип работы сортировки подсчетом
Главная идея алгоритма — посчитать, сколько раз встречается каждый элемент в массиве, а потом заполнить исходный массив результатами этого подсчёта. Для этого нам нужен вспомогательный массив, где мы будем хранить результаты подсчёта. Даже если нам надо отсортировать миллион чисел, мы всё равно знаем диапазон этих чисел заранее, например, от 1 до 100. Это значит, что во вспомогательном массиве будет не миллион элементов, а сто.
В общем виде всё работает так:
Мы создаём вспомогательный массив и на старте заполняем его нулями.
Проходим по всему исходному массиву и смотрим очередное значение в ячейке.
Берём содержимое этой ячейки и увеличиваем на единицу значение вспомогательного массива под этим номером. Например, если мы встретили число 5, то увеличиваем на единицу пятый элемент вспомогательного массива. Если встретили 13 — тринадцатый.
После цикла во вспомогательном массиве у нас хранятся данные, сколько раз встречается каждый элемент.
Теперь мы проходим по вспомогательному массиву, и если в очередной ячейке лежит что-то больше нуля, то мы в исходный массив столько же раз отправляем номер этой ячейки. Например, в первой ячейке вспомогательного массива лежит число 7. Это значит, что в исходный массив мы отправляем единицу 7 раз подряд.
Реализуйте сортировку подсчетом
// сортировка подсчётом
let countingSort = (arr, min, max) => {
// начинаем с минимального значения диапазона
let i = min,
// вспомогательная переменная для цикла
j = 0,
// получаем длину массива
len = arr.length,
// вспомогательный массив, где будем хранить результаты подсчёта
count = [];
// сначала заполняем нулями массив с результатом подсчёта
for (i; i <= max; i++) {
count[i] = 0;
}
// потом проходим по всему исходному массиву
for (i = 0; i < len; i++) {
// и увеличиваем на единичку ячейки под тем же номером в массиве с результатом подсчёта
count[arr[i]] += 1;
}
// а затем проходим по массиву с результатом
for (i = min; i <= max; i++) {
// пока в очередной ячейке значение больше нуля
while (count[i] > 0) {
// добавляем номер ячейки в исходный массив
arr[j] = i;
// переходим к следующему элементу в исходном массиве
j++;
// уменьшаем на единицу содержимое ячейки в массиве с подсчётом
count[i]--;
}
}
// как всё сделали — возвращаем отсортированный массив
return arr; };
// исходный массив
let arr = [0,3,5,2,4,5,2,3];
// сортируем его
countingSort(arr,0,5);
// и выводим результат
console.log(arr)
