Продолжая наше погружение в алгоритмы сортировки, мы продолжим с того места, где остановились, и начнем рассматривать алгоритм Сортировка вставками. Обладая средней сложностью и сложностью в худшем случае 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 алгоритма сортировки вставками. Если вы еще этого не сделали, попробуйте переделать его шаг за шагом, используя ручку, бумагу и время. Вы не ошибетесь с этим подходом, и вы не только немного лучше подготовитесь к этому собеседованию по программированию, но и дадите себе возможность по-настоящему погрузиться в алгоритм, эффективно разбирая его по частям и полностью понимая. . По крайней мере, это цель этого знания, которым я только что поделился. Конечно, Интернет является огромным источником информации, поэтому, если вам нужно больше информации по этому вопросу, на самом деле это всего лишь поиск.
Берегите себя, и увидимся на следующем! Удачного кодирования!