Продолжая наше погружение в алгоритмы сортировки, мы продолжим с того места, где остановились, и начнем рассматривать алгоритм Сортировка вставками. Обладая средней сложностью и сложностью в худшем случае O(N²), но сложностью в лучшем случае O(N), алгоритм перебирает элементы массива и на каждой итерации он удаляет текущий элемент, находит место, которому он по праву принадлежит в отсортированном списке, и вставляет его туда, сдвигая все остальные элементы вправо.

Этот алгоритм перечисляет, среди его преимуществ, следующее:

  • это очень легко реализовать;
  • он достаточно эффективен для небольших наборов данных, как и другие алгоритмы квадратичной сортировки;
  • на практике он более эффективен, чем большинство других простых квадратичных алгоритмов, таких как пузырьковая сортировка;
  • он отличается адаптивностью в том смысле, что он эффективен для наборов данных, которые уже находятся в почти отсортированном состоянии;
  • он стабилен, что означает, что он не меняет относительный порядок равных элементов;
  • это на месте, то есть требуется только постоянный объем дополнительного пространства памяти;
  • он также может сортировать список по мере его получения.

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

Давайте сделаем быстрый практический пример, чтобы лучше визуализировать и понять, как работает алгоритм. Учитывая arr=[5, 4, 3, 2, 1], мы хотели бы отсортировать его в порядке возрастания:

  • мы используем цикл for, где i принимает значения от 1 до N-1 (в нашем случае i=[1, 2, 3, 4]);
  • i=1; обр=[5, 4, 3, 2, 1]; обр[я]=4; мы сохраняем это значение в переменную temp;
  • на каждом шаге мы (повторно) инициализируем j равным i-1;
  • затем мы запускаем цикл while, работающий до тех пор, пока j≥0 и temp‹arr[j]; мы собираемся «переместить» элементы [0…j], которые больше, чем temp, влево, эффективно «освобождая место» для temp, который вмешается в правильном положении. Если что-то кажется неясным, просто продолжайте, через некоторое время станет ясно;
  • j=i-1=0; j ≥0, temp=4, arr[j]=5; temp‹arr[j], поэтому мы копируем arr[j] в arr[j+1], затем уменьшаем j: arr=[5, 5, 3, 2, 1];
  • j=-1; внутренний цикл while заканчивается. Мы помещаем значение temp в arr[j+1]; обр=[4, 5, 3, 2, 1];
  • i=2; обр=[4, 5, 3, 2, 1]; обр[я]=3; мы сохраняем его в temp;
  • сбросить j до i-1;
  • запустить цикл while;
  • j=i-1=1; j≥0, темп=3, обр[j]=5; temp‹arr[j], поэтому мы копируем arr[j] в arr[j+1], затем уменьшаем j: arr=[4, 5, 5, 2, 1];
  • j=0, темп=3, обр[j]=4; temp‹arr[j], поэтому мы копируем arr[j] в arr[j+1], затем уменьшаем j: arr=[4, 4, 5, 2, 1];
  • j=-1; внутренний цикл while заканчивается. Мы помещаем значение temp в arr[j+1]: arr=[3, 4, 5, 2, 1];
  • i=3; обр=[3, 4, 5, 2, 1]; обр[я]=2; мы сохраняем его в temp;
  • сбросить j до i-1;
  • запустить цикл while;
  • j=i-1=2; j≥0, темп=2, обр[j]=5; мы копируем arr[j] в arr[j+1], затем уменьшаем j: arr=[3, 4, 5, 5, 1];
  • j=1, темп=2, обр[j]=4; temp‹arr[j], поэтому мы копируем arr[j] в arr[j+1], затем уменьшаем j: arr=[3, 4, 4, 5, 1];
  • j=0, темп=2, обр[j]=3; temp‹arr[j], поэтому мы копируем arr[j] в arr[j+1], затем уменьшаем j: arr=[3, 3, 4, 5, 1];
  • j=-1; внутренний цикл while заканчивается. Мы помещаем значение temp в arr[j+1]: arr=[2, 3, 4, 5, 1];
  • i=4; обр=[2, 3, 4, 5, 1]; обр[я]=1; мы сохраняем его в temp;
  • сбросить j до i-1;
  • запустить цикл while;
  • j=i-1=3; j≥0, темп=1, обр[j]=5; temp‹arr[j], поэтому мы копируем arr[j] в arr[j+1], затем уменьшаем j: arr=[2, 3, 4, 5, 5];
  • j=2; j≥0, темп=1, обр[j]=4; temp‹arr[j], поэтому мы копируем arr[j] в arr[j+1], затем уменьшаем j: arr=[2, 3, 4, 4, 5];
  • j=1; j≥0, темп=1, обр[j]=3; temp‹arr[j], поэтому мы копируем arr[j] в arr[j+1], затем уменьшаем j: arr=[2, 3, 3, 4, 5];
  • j=0; j≥0, темп=1, обр[j]=2; temp‹arr[j], поэтому мы копируем arr[j] в arr[j+1], затем уменьшаем j: arr=[2, 2, 3, 4, 5];
  • j=-1; внутренний цикл while заканчивается. Мы помещаем значение temp в arr[j+1]: arr=[1, 2, 3, 4, 5];
  • Цикл for завершается, и все готово. Отсортированный массив: arr=[1, 2, 3, 4, 5].

Полный код ниже:

def insertion_sort(arr):
    """Algorithm main function."""
    # iterate through elements 1 through n-1
    for i in range(1, len(arr)):
        temp = arr[i]
        j = i - 1
        # make room for temp
        # for descending order sorting, replace < with > below
        while j >= 0 and temp < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        # place temp at its correct place
        arr[j + 1] = temp
    return arr

Вот оно. Очень простая реализация Python алгоритма сортировки вставками. Если вы еще этого не сделали, попробуйте переделать его шаг за шагом, используя ручку, бумагу и время. Вы не ошибетесь с этим подходом, и вы не только немного лучше подготовитесь к этому собеседованию по программированию, но и дадите себе возможность по-настоящему погрузиться в алгоритм, эффективно разбирая его по частям и полностью понимая. . По крайней мере, это цель этого знания, которым я только что поделился. Конечно, Интернет является огромным источником информации, поэтому, если вам нужно больше информации по этому вопросу, на самом деле это всего лишь поиск.

Берегите себя, и увидимся на следующем! Удачного кодирования!