Вы когда-нибудь раскладывали карты игральные по порядку? Или, может, сортировали вещи в шкафу? Если да, то вы уже интуитивно знакомы с алгоритмом сортировки вставками! Звучит сложно? Да ничего подобного. Сейчас мы разберемся, что это такое, как он работает и почему он полезен – даже если вы не программист (хотя для программистов это знание просто необходимо).
Что вообще такое сортировка? И зачем она нужна?
Прежде чем углубляться в детали, давайте определимся: сортировка – это процесс упорядочивания элементов списка (например, чисел, строк, объектов) по какому-либо критерию. Представьте себе огромный список клиентов, которые не отсортированы ни по имени, ни по дате регистрации. Как найти нужного человека? А если нужно вывести их в порядке убывания прибыли? Вот тут-то и приходят на помощь алгоритмы сортировки.
Существует множество алгоритмов сортировки (пузырьковая, выбором, слиянием… список можно продолжать долго), каждый со своими сильными и слабыми сторонами. Сортировка вставками – один из самых простых для понимания и реализации. И это не значит, что он плохой! В определенных ситуациях он может быть очень эффективным.
Как работает сортировка вставками? Объясняем на пальцах
Представьте, что у вас есть колода карт, которые нужно отсортировать по возрастанию. Вы берете первую карту и держите ее в руке (это ваш “отсортированный” список). Затем вы берете вторую карту и сравниваете ее с картой в руке. Если вторая карта меньше первой, вы вставляете ее перед первой. Если больше – оставляете ее после первой.
Потом вы берете третью карту, сравниваете ее с обеими картами в руке и вставляете ее на нужное место. И так далее, пока не разберете всю колоду.
В общем виде алгоритм выглядит так:
- Список делится на отсортированную и неотсортированную части.
- Берем первый элемент из неотсортированной части.
- Находим ему место в отсортированной части, сдвигая элементы при необходимости.
- Повторяем шаги 2-3, пока вся колода не будет отсортирована.
Звучит просто? А теперь давайте посмотрим на код!
Сортировка вставками в разных языках программирования: практика – критерий истины
Давайте рассмотрим реализацию сортировки вставками на нескольких популярных языках программирования. Не пугайтесь, если вы не знакомы с ними – я постараюсь объяснить каждый шаг максимально понятно.
Swift:
func insertionSort(_ array: [Int]) -> [Int] {
var arr = array // Создаем копию массива, чтобы не изменять исходный
for i in 1..<arr.count {
let key = arr[i]
var j = i - 1
while j >= 0 && arr[j] > key {
arr[j + 1] = arr[j] // Сдвигаем элементы вправо, чтобы освободить место для вставки
j -= 1
}
arr[j + 1] = key // Вставляем элемент на нужное место
}
return arr
}
let unsortedArray = [5, 2, 8, 1, 9, 4]
let sortedArray = insertionSort(unsortedArray)
print("Отсортированный массив: \(sortedArray)") // Вывод: Отсортированный массив: [1, 2, 4, 5, 8, 9]
- Здесь мы создаем функцию
insertionSort, которая принимает массив целых чисел и возвращает отсортированный массив. - В цикле
forмы проходим по массиву, начиная со второго элемента (индекс 1). - Переменная
keyхранит текущий элемент, который нужно вставить на место. - Цикл
whileсдвигает элементы отсортированной части массива вправо, пока не найдет подходящее место дляkey.
Kotlin:
fun insertionSort(array: IntArray): IntArray {
val arr = array.copyOf() // Создаем копию массива
for (i in 1 until arr.size) {
val key = arr[i]
var j = i - 1
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]
j--
}
arr[j + 1] = key
}
return arr
}
fun main() {
val unsortedArray = intArrayOf(5, 2, 8, 1, 9, 4)
val sortedArray = insertionSort(unsortedArray)
println("Отсортированный массив: ${sortedArray.contentToString()}") // Вывод: Отсортированный массив: [1, 2, 4, 5, 8, 9]
}
- Kotlin очень похож на Swift в плане синтаксиса и логики работы. Обратите внимание на использование
copyOf()для создания копии массива.
Java:
public class InsertionSort {
public static int[] insertionSort(int[] array) {
int[] arr = array.clone(); // Создаем копию массива
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
return arr;
}
public static void main(String[] args) {
int[] unsortedArray = {5, 2, 8, 1, 9, 4};
int[] sortedArray = insertionSort(unsortedArray);
System.out.println("Отсортированный массив: " + java.util.Arrays.toString(sortedArray)); // Вывод: Отсортированный массив: [1, 2, 4, 5, 8, 9]
}
}
- В Java мы используем метод
clone()для создания копии массива. Также обратите внимание на использованиеjava.util.Arrays.toString()для вывода содержимого массива.
JavaScript:
function insertionSort(array) {
const arr = [...array]; // Создаем копию массива с помощью spread syntax
for (let i = 1; i < arr.length; 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 unsortedArray = [5, 2, 8, 1, 9, 4];
const sortedArray = insertionSort(unsortedArray);
console.log("Отсортированный массив:", sortedArray); // Вывод: Отсортированный массив: [1, 2, 4, 5, 8, 9]
- В JavaScript мы используем spread syntax (
...) для создания копии массива. Это более современный и удобный способ по сравнению с другими методами.
Python:
def insertion_sort(array):
arr = array[:] # Создаем копию массива с помощью среза
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
unsorted_array = [5, 2, 8, 1, 9, 4]
sorted_array = insertion_sort(unsorted_array)
print("Отсортированный массив:", sorted_array) # Вывод: Отсортированный массив: [1, 2, 4, 5, 8, 9]
- В Python мы используем срез (
[:]) для создания копии массива. Это простой и элегантный способ.
Как видите, логика работы алгоритма одинакова во всех языках. Различаются только синтаксис и некоторые детали реализации.
Когда использовать сортировку вставками? И когда лучше выбрать другой алгоритм?
Сортировка вставками хорошо подходит для:
- Небольших списков: Для небольшого количества элементов она работает очень быстро.
- Почти отсортированных списков: Если список уже почти отсортирован, сортировка вставками будет работать очень эффективно. В этом случае количество сдвигов элементов будет минимальным.
- Онлайн-сортировки: Сортировку вставками можно использовать для сортировки данных по мере их поступления.
Однако, если у вас большой неотсортированный список, лучше выбрать более эффективный алгоритм, например, быструю сортировку (Quick Sort) или сортировку слиянием (Merge Sort). Они имеют сложность O(n log n), в то время как сортировка вставками имеет сложность O(n^2) в худшем случае.
Подведём итоги: что мы узнали?
Сортировка вставками – это простой и понятный алгоритм, который хорошо подходит для небольших списков и почти отсортированных данных. Он легко реализуется на любом языке программирования и может быть полезен во многих ситуациях. Но помните, что для больших списков лучше выбрать более эффективный алгоритм.
Ну а если вы дочитали до конца – поздравляю! Вы теперь знаете еще один важный инструмент в арсенале программиста (или просто человека, который любит порядок). А знаете что? Сортировка вставками часто используется в реальных приложениях для сортировки небольших подмассивов при реализации более сложных алгоритмов. Так что даже если вы не планируете писать собственные алгоритмы сортировки, знание принципов ее работы может быть очень полезным!





