В программировании существует множество алгоритмов сортировки, каждый из которых имеет свои особенности, преимущества и недостатки. Вот некоторые из наиболее известных видов сортировок:
Сортировка пузырьком (Bubble Sort)
Простой алгоритм, который многократно проходит по массиву, сравнивая соседние элементы и меняя их местами, если они находятся в неправильном порядке. Процесс повторяется, пока массив не будет отсортирован.
Вот пример реализации сортировки пузырьком (Bubble Sort) на JavaScript.
function bubbleSort(arr) {
const n = arr.length;
let swapped;
// Проходим по всему массиву
for (let i = 0; i < n - 1; i++) {
swapped = false; // Флаг для отслеживания, были ли произведены обмены
// Последние i элементов уже отсортированы
for (let j = 0; j < n - 1 - i; j++) {
// Сравниваем соседние элементы
if (arr[j] > arr[j + 1]) {
// Меняем местами, если они в неправильном порядке
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
swapped = true; // Устанавливаем флаг, что обмен произошел
}
}
// Если не было обменов, массив уже отсортирован
if (!swapped) {
break;
}
}
return arr;
}
// Пример использования
const numbers = [64, 34, 25, 12, 22, 11, 90];
const sortedNumbers = bubbleSort(numbers);
console.log(sortedNumbers); // [11, 12, 22, 25, 34, 64, 90]
Объяснение кода:
- Функция bubbleSort(arr): принимает массив arr в качестве аргумента.
- Переменная n: хранит длину массива.
- Цикл for: проходит по массиву, выполняя сортировку.
- Вложенный цикл for: сравнивает соседние элементы и меняет их местами, если они находятся в неправильном порядке.
- Флаг swapped: используется для отслеживания, были ли произведены обмены. Если за проход не было обменов, это означает, что массив уже отсортирован, и можно завершить выполнение.
- Возвращает отсортированный массив.
Этот алгоритм имеет временную сложность O(n²) в худшем и среднем случае, что делает его неэффективным для больших массивов, но он прост в реализации и понимании.
Сортировка выбором (Selection Sort)
Алгоритм, который делит массив на отсортированную и неотсортированную части. На каждой итерации он находит минимальный элемент из неотсортированной части и перемещает его в конец отсортированной части.
Вот пример реализации сортировки выбором (Selection Sort) на JavaScript.
Пример кода:
function selectionSort(arr) {
const n = arr.length;
// Проходим по всему массиву
for (let i = 0; i < n - 1; i++) {
// Предполагаем, что текущий элемент - минимальный
let minIndex = i;
// Находим индекс минимального элемента в оставшейся части массива
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j; // Обновляем индекс минимального элемента
}
}
// Меняем местами текущий элемент с найденным минимальным
if (minIndex !== i) {
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
}
return arr;
}
// Пример использования
const numbers = [64, 25, 12, 22, 11];
const sortedNumbers = selectionSort(numbers);
console.log(sortedNumbers); // [11, 12, 22, 25, 64]
Объяснение кода:
- Функция selectionSort(arr): принимает массив arr в качестве аргумента.
- Переменная n: хранит длину массива.
- Цикл for: проходит по массиву, выбирая текущий элемент для сравнения.
- Переменная minIndex: используется для хранения индекса минимального элемента, начиная с текущего элемента.
- Вложенный цикл for: ищет минимальный элемент в оставшейся части массива.
- Сравнение и обмен: если найденный минимальный элемент не равен текущему, они меняются местами.
- Возвращает отсортированный массив.
Временная сложность:
Сортировка выбором имеет временную сложность O(n²) в худшем и среднем случае, что делает её менее эффективной для больших массивов по сравнению с более сложными алгоритмами, такими как быстрая сортировка или сортировка слиянием. Однако она проста в реализации и понимании.
Сортировка вставками (Insertion Sort)
Алгоритм, который строит отсортированную последовательность, вставляя каждый новый элемент в правильное место. Он работает хорошо на небольших массивах и почти отсортированных данных.
Вот пример реализации сортировки вставками (Insertion Sort) на JavaScript. а.
Пример кода:
function insertionSort(arr) {
const n = arr.length;
// Проходим по массиву, начиная со второго элемента
for (let i = 1; i < n; i++) {
const key = arr[i]; // Текущий элемент для вставки
let j = i - 1;
// Сдвигаем элементы, которые больше ключа, на одну позицию вправо
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
// Вставляем ключ на его правильное место
arr[j + 1] = key;
}
return arr;
}
// Пример использования
const numbers = [64, 25, 12, 22, 11];
const sortedNumbers = insertionSort(numbers);
console.log(sortedNumbers); // [11, 12, 22, 25, 64]
Объяснение кода:
- Функция insertionSort(arr): принимает массив arr в качестве аргумента.
- Переменная n: хранит длину массива.
- Цикл for: проходит по массиву, начиная со второго элемента (индекс 1), так как первый элемент считается уже отсортированным.
- Переменная key: хранит текущий элемент, который нужно вставить в отсортированную часть массива.
- Вложенный цикл while: сдвигает элементы, которые больше key, на одну позицию вправо, чтобы освободить место для вставки.
- Вставка: после завершения внутреннего цикла while элемент key вставляется на его правильное место.
- Возвращает отсортированный массив.
Временная сложность:
Сортировка вставками имеет временную сложность O(n²) в худшем и среднем случае, но она работает быстрее на почти отсортированных данных и имеет временную сложность O(n) в лучшем случае. Этот алгоритм прост в реализации и понимании, что делает его популярным для небольших массивов.
Сортировка слиянием (Merge Sort)
Алгоритм, который использует метод "разделяй и властвуй". Этот алгоритм использует метод "разделяй и властвуй". Он делит массив на две половины, рекурсивно сортирует каждую половину и затем объединяет отсортированные половины.
Вот пример реализации сортировки слиянием (Merge Sort) на JavaScript.
Пример кода:
function mergeSort(arr) {
// Базовый случай: если массив состоит из одного элемента или пустой, он уже отсортирован
if (arr.length <= 1) {
return arr;
}
// Находим середину массива
const mid = Math.floor(arr.length / 2);
// Рекурсивно сортируем левую и правую половины
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
// Объединяем отсортированные половины
return merge(left, right);
}
function merge(left, right) {
const result = [];
let i = 0;
let j = 0;
// Сравниваем элементы из левой и правой половин и добавляем меньший в результат
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result.push(left[i]);
i++;
} else {
result.push(right[j]);
j++;
}
}
// Добавляем оставшиеся элементы из левой половины, если есть
while (i < left.length) {
result.push(left[i]);
i++;
}
// Добавляем оставшиеся элементы из правой половины, если есть
while (j < right.length) {
result.push(right[j]);
j++;
}
return result;
}
// Пример использования
const numbers = [64, 25, 12, 22, 11];
const sortedNumbers = mergeSort(numbers);
console.log(sortedNumbers); // [11, 12, 22, 25, 64]
Объяснение кода:
- Функция mergeSort(arr): принимает массив arr в качестве аргумента.
- Базовый случай: если массив состоит из одного элемента или пустой, он уже отсортирован, и функция возвращает его.
- Находим середину массива: с помощью Math.floor(arr.length / 2).
- Рекурсивные вызовы: сортируем левую и правую половины массива.
- Функция merge(left, right): объединяет два отсортированных массива left и right в один отсортированный массив.
- Цикл while: сравнивает элементы из левой и правой половин и добавляет меньший элемент в результирующий массив.
- Добавление оставшихся элементов: если в одной из половин остались элементы, они добавляются в результирующий массив.
- Возвращает отсортированный массив.
Временная сложность:
Сортировка слиянием имеет временную сложность O(n log n) в худшем, среднем и лучшем случае, что делает её эффективной для сортировки больших массивов. Однако она требует дополнительной памяти для хранения временных массивов, что может быть недостатком в некоторых ситуациях.
Быстрая сортировка (Quick Sort)
Также использует метод "разделяй и властвуй". Алгоритм выбирает опорный элемент и разделяет массив на элементы, меньшие и большие опорного, а затем рекурсивно сортирует подмассивы.
Вот пример реализации быстрой сортировки (Quick Sort) на JavaScript.
Пример кода:
function quickSort(arr) {
// Базовый случай: если массив пустой или состоит из одного элемента, он уже отсортирован
if (arr.length <= 1) {
return arr;
}
// Выбираем опорный элемент (в данном случае последний элемент массива)
const pivot = arr[arr.length - 1];
const left = []; // Массив для элементов меньше опорного
const right = []; // Массив для элементов больше опорного
// Проходим по всем элементам, кроме опорного
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] < pivot) {
left.push(arr[i]); // Добавляем в левый массив, если элемент меньше опорного
} else {
right.push(arr[i]); // Добавляем в правый массив, если элемент больше или равен опорному
}
}
// Рекурсивно сортируем левую и правую части и объединяем их с опорным элементом
return [...quickSort(left), pivot, ...quickSort(right)];
}
// Пример использования
const numbers = [64, 25, 12, 22, 11];
const sortedNumbers = quickSort(numbers);
console.log(sortedNumbers); // [11, 12, 22, 25, 64]
Объяснение кода:
- Функция quickSort(arr): принимает массив arr в качестве аргумента.
- Базовый случай: если массив пустой или состоит из одного элемента, он уже отсортирован, и функция возвращает его.
- Выбор опорного элемента: в данном случае мы выбираем последний элемент массива как опорный.
- Создание массивов left и right: для хранения элементов, меньших и больших опорного соответственно.
- Цикл for: проходит по всем элементам массива, кроме опорного, и распределяет их по массивам left и right.
- Рекурсивные вызовы: сортируем левую и правую части и объединяем их с опорным элементом.
- Возвращает отсортированный массив.
Временная сложность:
Быстрая сортировка имеет среднюю временную сложность O(n log n), но в худшем случае (например, если массив уже отсортирован и опорный элемент всегда выбирается как крайний) может достигать O(n²). Однако, при правильном выборе опорного элемента (например, с использованием метода "случайного выбора" или "медианы трех") быстрая сортировка обычно работает очень эффективно и является одним из самых популярных алгоритмов сортировки.
Сортировка Шелла (Shell Sort)
Обобщение сортировки вставками, которое позволяет обменивать элементы, находящиеся на большом расстоянии друг от друга. Сначала сортируются элементы, находящиеся на определённом расстоянии, а затем расстояние уменьшается.
Вот пример реализации сортировки Шелла (Shell Sort) на JavaScript.
Пример кода:
function shellSort(arr) {
const n = arr.length;
let gap = Math.floor(n / 2); // Начальный интервал
// Уменьшаем интервал до 1
while (gap > 0) {
// Проходим по массиву с текущим интервалом
for (let i = gap; i < n; i++) {
const temp = arr[i]; // Сохраняем текущий элемент
let j = i;
// Сравниваем и перемещаем элементы, находящиеся на расстоянии gap
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap]; // Сдвигаем элемент
j -= gap; // Переходим к следующему элементу с учетом интервала
}
arr[j] = temp; // Вставляем текущий элемент на его правильное место
}
gap = Math.floor(gap / 2); // Уменьшаем интервал
}
return arr;
}
// Пример использования
const numbers = [64, 25, 12, 22, 11];
const sortedNumbers = shellSort(numbers);
console.log(sortedNumbers); // [11, 12, 22, 25, 64]
Объяснение кода:
- Функция shellSort(arr): принимает массив arr в качестве аргумента.
- Переменная n: хранит длину массива.
- Переменная gap: устанавливает начальный интервал, равный половине длины массива.
- Цикл while: продолжается, пока интервал больше 0.
- Вложенный цикл for: проходит по массиву, начиная с индекса gap.
- Переменная temp: сохраняет текущий элемент для вставки.
- Вложенный цикл while: сравнивает и перемещает элементы, находящиеся на расстоянии gap, если они больше текущего элемента.
- Вставка: текущий элемент вставляется на его правильное место.
- Уменьшение интервала: интервал делится на 2 для следующей итерации.
- Возвращает отсортированный массив.
Временная сложность:
Сортировка Шелла имеет временную сложность O(n log n) в среднем случае, но может варьироваться в зависимости от выбора интервалов. Этот алгоритм эффективен для сортировки больших массивов и является улучшенной версией сортировки вставками.
7. Сортировка подсчетом (Counting Sort)
Алгоритм, который работает только с целыми числами и использует дополнительный массив для подсчета количества вхождений каждого элемента. Он эффективен для сортировки небольших диапазонов чисел.
Cортировка подсчетом (Counting Sort), пример на js.
Пример кода:
function countingSort(arr) {
const n = arr.length;
if (n === 0) return arr;
// Находим максимальное значение в массиве
const max = Math.max(...arr);
const count = new Array(max + 1).fill(0); // Массив для подсчета вхождений
const output = new Array(n); // Массив для отсортированных элементов
// Подсчитываем количество вхождений каждого элемента
for (let i = 0; i < n; i++) {
count[arr[i]]++;
}
// Изменяем count[i] так, чтобы count[i] содержал фактическую позицию элемента в output
for (let i = 1; i <= max; i++) {
count[i] += count[i - 1];
}
// Строим отсортированный массив
for (let i = n - 1; i >= 0; i--) {
output[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
return output;
}
// Пример использования
const numbers = [4, 2, 2, 8, 3, 3, 1];
const sortedNumbers = countingSort(numbers);
console.log(sortedNumbers); // [1, 2, 2, 3, 3, 4, 8]
Объяснение кода:
- Функция countingSort(arr): принимает массив arr в качестве аргумента.
- Переменная n: хранит длину массива.
- Проверка на пустой массив: если массив пустой, возвращаем его.
- Находим максимальное значение: используем Math.max(...arr) для определения максимального элемента в массиве.
- Создаем массив count: размером max + 1, инициализируем его нулями. Этот массив будет использоваться для подсчета вхождений.
- Подсчет вхождений: проходим по исходному массиву и увеличиваем соответствующий индекс в массиве count.
- Изменение массива count: преобразуем его так, чтобы каждый элемент содержал фактическую позицию элемента в выходном массиве.
- Строим отсортированный массив: проходим по исходному массиву в обратном порядке, чтобы сохранить стабильность сортировки, и заполняем выходной массив.
- Возвращаем отсортированный массив.
Временная сложность:
Сортировка подсчетом имеет временную сложность O(n + k), где n — количество элементов в массиве, а k — диапазон значений (максимальное значение). Этот алгоритм эффективен, когда диапазон значений не слишком велик по сравнению с количеством элементов. Однако он не подходит для сортировки данных с плавающей запятой или строк.
Радиксная сортировка (Radix Sort)
Радиксная сортировка (Radix Sort) — это алгоритм сортировки, который сортирует числа по разрядам, начиная с младших разрядов к старшим. Этот алгоритм обычно использует сортировку подсчетом (Counting Sort) в качестве вспомогательного алгоритма для сортировки по каждому разряду.
Пример кода:
function countingSortForRadix(arr, exp) {
const n = arr.length;
const output = new Array(n); // Массив для отсортированных элементов
const count = new Array(10).fill(0); // Массив для подсчета вхождений (для цифр от 0 до 9)
// Подсчитываем количество вхождений для текущего разряда
for (let i = 0; i < n; i++) {
const index = Math.floor(arr[i] / exp) % 10; // Получаем цифру по текущему разряду
count[index]++;
}
// Изменяем count[i] так, чтобы count[i] содержал фактическую позицию элемента в output
for (let i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// Строим отсортированный массив
for (let i = n - 1; i >= 0; i--) {
const index = Math.floor(arr[i] / exp) % 10; // Получаем цифру по текущему разряду
output[count[index] - 1] = arr[i];
count[index]--;
}
// Копируем отсортированные элементы обратно в оригинальный массив
for (let i = 0; i < n; i++) {
arr[i] = output[i];
}
}
function radixSort(arr) {
// Находим максимальное число, чтобы определить количество разрядов
const max = Math.max(...arr);
// Применяем сортировку по каждому разряду
for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
countingSortForRadix(arr, exp);
}
return arr;
}
// Пример использования
const numbers = [170, 45, 75, 90, 802, 24, 2, 66];
const sortedNumbers = radixSort(numbers);
console.log(sortedNumbers); // [2, 24, 45, 66, 75, 90, 170, 802]
Объяснение кода:
- Функция countingSortForRadix(arr, exp): выполняет сортировку подсчетом для текущего разряда, определяемого exp.Массив count: используется для подсчета вхождений цифр от 0 до 9.
Цикл для подсчета: проходит по массиву и подсчитывает количество вхождений каждой цифры для текущего разряда.
Изменение массива count: преобразует его так, чтобы каждый элемент содержал фактическую позицию элемента в выходном массиве.
Строим отсортированный массив: проходим по исходному массиву в обратном порядке, чтобы сохранить стабильность сортировки, и заполняем выходной массив.
Копируем отсортированные элементы обратно: в оригинальный массив. - Функция radixSort(arr): основная функция, которая находит максимальное число в массиве и применяет сортировку по каждому разряду, начиная с младшего. Цикл по разрядам: увеличивает exp (разряд) на порядок, пока не достигнет максимального числа.
Временная сложность:
Радиксная сортировка имеет временную сложность O(d * (n + k)), где n — количество элементов, d — количество разрядов, а k — диапазон значений (в данном случае 10 для десятичной системы). Этот алгоритм эффективен для сортировки целых чисел и может быть быстрее, чем сравнивающие алгоритмы сортировки, когда d и k относительно малы.
Пирамидальная сортировка (Heap Sort)
Пирамидальная сортировка (Heap Sort) — это алгоритм сортировки, который использует структуру данных "куча" (heap). Он строит кучу из массива и затем извлекает элементы из кучи, чтобы получить отсортированный массив. Пирамидальная сортировка имеет временную сложность O(n log n) в худшем, среднем и лучшем случае.
Пример кода на js:
function heapify(arr, n, i) {
let largest = i; // Инициализируем наибольший элемент как корень
const left = 2 * i + 1; // Левый дочерний элемент
const right = 2 * i + 2; // Правый дочерний элемент
// Если левый дочерний элемент больше корня
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// Если правый дочерний элемент больше наибольшего элемента
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// Если наибольший элемент не корень
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]]; // Меняем местами
// Рекурсивно преобразуем затронутое поддерево в кучу
heapify(arr, n, largest);
}
}
function heapSort(arr) {
const n = arr.length;
// Строим кучу (перегруппируем массив)
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// Один за другим извлекаем элементы из кучи
for (let i = n - 1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]]; // Меняем местами
heapify(arr, i, 0); // Применяем heapify к уменьшенной куче
}
return arr;
}
// Пример использования
const numbers = [64, 25, 12, 22, 11];
const sortedNumbers = heapSort(numbers);
console.log(sortedNumbers); // [11, 12, 22, 25, 64]
Объяснение кода:
- Функция heapify(arr, n, i): преобразует поддерево с корнем в i в кучу. Переменная largest: инициализирует наибольший элемент как корень.
Переменные left и right: определяют индексы левого и правого дочерних элементов.
Сравнение: проверяет, является ли левый или правый дочерний элемент больше наибольшего элемента.
Обмен: если наибольший элемент не корень, меняет их местами и рекурсивно вызывает heapify для затронутого поддерева. - Функция heapSort(arr): основная функция, которая сортирует массив.Строит кучу: проходит по массиву и вызывает heapify для каждого элемента, начиная с последнего не листового узла.
Извлечение элементов: один за другим извлекает элементы из кучи, меняя местами корень (наибольший элемент) с последним элементом массива и применяя heapify к уменьшенной куче.
Временная сложность:
Пирамидальная сортировка имеет временную сложность O(n log n) в худшем, среднем и лучшем случае. Она не требует дополнительной памяти, как сортировка слиянием, и является неустойчивым алгоритмом сортировки.
Топологическая сортировка
Топологическая сортировка — это алгоритм, который используется для упорядочивания вершин в ориентированном ациклическом графе (DAG) так, чтобы для каждого ребра (u, v) вершина u предшествовала вершине v. Топологическая сортировка может быть выполнена с использованием алгоритма поиска в глубину (DFS) или с использованием метода Кана (Kahn's algorithm).
Вот пример реализации топологической сортировки с использованием алгоритма поиска в глубину (DFS) на JavaScript:
Пример кода:
function topologicalSortUtil(v, visited, stack, graph) {
// Помечаем текущую вершину как посещенную
visited[v] = true;
// Рекурсивно посещаем все соседние вершины
for (let i of graph[v]) {
if (!visited[i]) {
topologicalSortUtil(i, visited, stack, graph);
}
}
// Добавляем текущую вершину в стек
stack.push(v);
}
function topologicalSort(graph) {
const n = graph.length; // Количество вершин
const visited = new Array(n).fill(false); // Массив для отслеживания посещенных вершин
const stack = []; // Стек для хранения топологически отсортированных вершин
// Вызываем вспомогательную функцию для каждой вершины
for (let i = 0; i < n; i++) {
if (!visited[i]) {
topologicalSortUtil(i, visited, stack, graph);
}
}
// Печатаем элементы в обратном порядке, чтобы получить топологическую сортировку
return stack.reverse();
}
// Пример использования
const graph = [
[1, 2], // Вершина 0 указывает на 1 и 2
[3], // Вершина 1 указывает на 3
[3], // Вершина 2 указывает на 3
[] // Вершина 3 не указывает ни на что
];
const sortedOrder = topologicalSort(graph);
console.log(sortedOrder); // [0, 1, 2, 3] или [0, 2, 1, 3] в зависимости от порядка обхода
Объяснение кода:
- Функция topologicalSortUtil(v, visited, stack, graph):Помечает текущую вершину v как посещенную.
Рекурсивно посещает все соседние вершины, которые еще не были посещены.
Добавляет текущую вершину в стек после посещения всех её соседей. - Функция topologicalSort(graph):Инициализирует массив visited для отслеживания посещенных вершин и стек stack для хранения топологически отсортированных вершин.
Вызывает вспомогательную функцию для каждой вершины, если она еще не была посещена.
Возвращает стек в обратном порядке, чтобы получить правильный порядок топологической сортировки.
Примечание:
- Входной граф представлен в виде массива смежности, где graph[i] содержит массив вершин, на которые указывает вершина i.
- Топологическая сортировка возможна только для ориентированных ациклических графов (DAG). Если граф содержит циклы, топологическая сортировка невозможна.
Заключение
Выбор алгоритма сортировки зависит от различных факторов, таких как размер массива, тип данных, требования к производительности и стабильности. Каждый из этих алгоритмов имеет свои преимущества и недостатки, и понимание их особенностей поможет выбрать наиболее подходящий для конкретной задачи.