Сортировка вставками. Сортировка Шелла.

Сортировка вставками

Сортировка вставками (Insertion sort) - это алгоритм сортировки, основанный на последовательном просмотре элементов массива и их вставке в отсортированную часть массива.

Худшее O(n^2)Cреднее O(n^2)

1. Берем первый элемент массива и считаем, что он отсортирован.
2. Берем второй элемент и сравниваем его с первым. Если он меньше, то меняем их местами.
3. Берем третий элемент и сравниваем его с предыдущими двумя. Если он меньше второго, то меняем их местами. Если он меньше первого, то меняем его место с первым.
4. Продолжаем этот процесс для всех элементов массива.

def insertionSort(arr):  
    n = len(arr)  
    for i in range(1, n):  
        current = arr[i]  
        j = i - 1  
        while (j >= 0 and current < arr[j]):  
            arr[j + 1] = arr[j]  
            j -= 1  
        arr[j + 1] = current

Сортировка Шелла

Сортировка Шелла (Shell sort) - это алгоритм сортировки, который является улучшением сортировки вставками. Идея состоит в сравнивании не только стоящих рядом элементов, но и на определённом расстоянии.

Худшее O(n^2)Лучшее O(n* log^2(n))

1. Выбираем начальный инкремент h, который равен длине массива, деленной на 2.
2. Разбиваем массив на подмассивы, каждый из которых состоит из элементов, разделенных на h.
3. Сортируем каждый подмассив с помощью сортировки вставками.
4. Уменьшаем инкремент h в два раза и повторяем шаги 2-3, пока h не станет равным 1.
5. Сортируем массив с помощью сортировки вставками.

Для понимания arr = [6, 5, 1, 0, 2, 4, 3]

1. h = len(arr) // 2 => рассмотрим элементы [0], [0 + h], [0 + h + h] => => сортируем сортировкой вставками [0, 5, 1, 3, 2, 4, 6]
2. Смещаемся вправо => рассмотрим [1], [1 + h], [1 + h + h] (больше длины массива) => => сравниваем элементы [0, 2, 1, 3, 5, 4, 6]
3. Сравниваем так все элементы вплоть до [h], [h + h], уменьшаем шаг на 1
4. [0, 5, 1, 3, 2, 4, 6] => => [0, 5, 1, 3, 2, 4, 6] => и т.д. вплоть до шага h=1

def shellSort(arr):  
    n = len(arr)  
    h = n // 2  
	
    while h > 0:  
        for i in range(h, n):  
            current = arr[i]  
            j = i  
            while j >= h and current < arr[j - h]:  
                arr[j] = arr[j - h]  
                j -= h  
            arr[j] = current  
        h //= 2