Как сделать сортировку массива методом вставки python?

Question

Карина Абдуллаева · Accepted Answer

**Сортировка вставками (Insertion Sort)** — это алгоритм сортировки, на каждом шаге которого массив постепенно перебирается слева направо. При этом каждый последующий элемент размещается так, чтобы он оказался между ближайшими элементами с минимальным и максимальным значением. Подробнее можно прочитать в [Википедии](https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%81%D1%82%D0%B0%D0%B2%D0%BA%D0%B0%D0%BC%D0%B8).

[визуализация алгоритма сортировки вставками](https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%81%D1%82%D0%B0%D0%B2%D0%BA%D0%B0%D0%BC%D0%B8#/media/%D0%A4%D0%B0%D0%B9%D0%BB:Insertion-sort-example-300px.gif "enter image title here")

```python
def insertion_sort(array):
    n = len(array)
    for i in range(1, n):
        x = array[i]
        j = i

        while j > 0 and array[j - 1] > x:
            array[j] = array[j - 1]
            j -= 1
            
        array[j] = x

    return array


insertion_sort([6, 5, 3, 8, 9, 1]) # [1, 3, 5, 6, 8, 9]

```

Как сделать сортировку массива методом вставки python?

Ответы

Каталог