Реализация и анализ Insertion Sort
Всем привет!
Мы продолжаем радовать вас контентом, который обычно заставляет нас боятся собеседований. Надеемся вы пытаетесь осмыслить все алгоритмы, которые мы тут с вами разбираем, ведь совсем скоро вступим в бой с задачками на лит код и будем устранять все пробелы в наших знаниях.
Если вы забыли про что мы говорили в предыдущем посте, то мы советуем освежить его в памяти, перейдя по этой ссылке. А теперь вернемся к нашим красивым алгоритмам :)
Сегодня разговор пойдет про insertion sort.
Алгоритм работает, перебирая массив и вставляя каждый элемент в правильное положение в отсортированной части массива.
Реализация алгоритма:
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i-1
while j >= 0 and key < arr[j] :
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
Вот как работает алгоритм:
Мы начинаем со второго элемента массива (i=1) и предполагаем, что первый элемент (i=0) уже отсортирован.
Мы сохраняем текущий элемент в переменной с именем key.
Мы сравниваем ключ с каждым предшествующим ему элементом (j=i-1), начиная с последнего элемента отсортированной части массива, и перемещаем все элементы, которые больше ключа, на одну позицию вправо.
Мы вставляем ключ в правильное положение в отсортированной части массива, вставляя его после последнего элемента, который меньше или равен ключу.
Мы повторяем этот процесс для каждого элемента массива.
Временная сложность:
O(n)
Надеемся вам нравится наш материал. Если у вас есть какие-то предложения или идеи, то не стесняйтесь их озвучивать в комментариях. Мы желаем вам успехов в изучении алгоритмов и суперского настроения!
#learning_python_algorithms
