Вы когда-нибудь раскладывали карты игральные по порядку? Или, может, сортировали вещи в шкафу? Если да, то вы уже интуитивно знакомы с алгоритмом сортировки вставками! Звучит сложно? Да ничего подобного. Сейчас мы разберемся, что это такое, как он работает и почему он полезен – даже если вы не программист (хотя для программистов это знание просто необходимо).


Что вообще такое сортировка? И зачем она нужна?

Прежде чем углубляться в детали, давайте определимся: сортировка – это процесс упорядочивания элементов списка (например, чисел, строк, объектов) по какому-либо критерию. Представьте себе огромный список клиентов, которые не отсортированы ни по имени, ни по дате регистрации. Как найти нужного человека? А если нужно вывести их в порядке убывания прибыли? Вот тут-то и приходят на помощь алгоритмы сортировки.

Существует множество алгоритмов сортировки (пузырьковая, выбором, слиянием… список можно продолжать долго), каждый со своими сильными и слабыми сторонами. Сортировка вставками – один из самых простых для понимания и реализации. И это не значит, что он плохой! В определенных ситуациях он может быть очень эффективным.


Как работает сортировка вставками? Объясняем на пальцах

Представьте, что у вас есть колода карт, которые нужно отсортировать по возрастанию. Вы берете первую карту и держите ее в руке (это ваш “отсортированный” список). Затем вы берете вторую карту и сравниваете ее с картой в руке. Если вторая карта меньше первой, вы вставляете ее перед первой. Если больше – оставляете ее после первой.

Потом вы берете третью карту, сравниваете ее с обеими картами в руке и вставляете ее на нужное место. И так далее, пока не разберете всю колоду.

В общем виде алгоритм выглядит так:

  1. Список делится на отсортированную и неотсортированную части.
  2. Берем первый элемент из неотсортированной части.
  3. Находим ему место в отсортированной части, сдвигая элементы при необходимости.
  4. Повторяем шаги 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) в худшем случае.

Подведём итоги: что мы узнали?

Сортировка вставками – это простой и понятный алгоритм, который хорошо подходит для небольших списков и почти отсортированных данных. Он легко реализуется на любом языке программирования и может быть полезен во многих ситуациях. Но помните, что для больших списков лучше выбрать более эффективный алгоритм.

Ну а если вы дочитали до конца – поздравляю! Вы теперь знаете еще один важный инструмент в арсенале программиста (или просто человека, который любит порядок). А знаете что? Сортировка вставками часто используется в реальных приложениях для сортировки небольших подмассивов при реализации более сложных алгоритмов. Так что даже если вы не планируете писать собственные алгоритмы сортировки, знание принципов ее работы может быть очень полезным!


Будет интересно

Nikulux в Telegram

Статьи, архивы материалов, скоро ещё и мемы

(= Подписаться =)