Pythoner
Фотография
✈️Сортировка вставками - это простой, но эффективный алгоритм сортировки, который обрабатывает входные данные, добавляя каждый новый элемент в отсортированную часть массива.
➡️Принцип работы
Сортировка вставками работает, сравнивая каждый элемент в массиве с его левым соседом. Если текущий элемент меньше, он перемещается влево. Это происходит до тех пор, пока текущий элемент не окажется больше предыдущего. Этот процесс повторяется для каждого элемента в массиве, пока весь массив не будет отсортирован.
➡️Вот пример реализации сортировки вставками на Python:
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
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print ("Отсортированный массив: ", end ="")
for i in range(len(arr)):
print ("%d" %arr[i], end =" ")
⬆️В этом коде мы проходимся по каждому элементу массива, начиная со второго, и сдвигаем его влево, пока не найдем элемент, который меньше текущего.
➡️Процесс сортировки
В сортировке вставками каждый новый элемент добавляется в уже отсортированную часть массива. Этот процесс начинается с первого элемента массива и продолжается, пока все элементы не будут отсортированы. На каждом шаге новый элемент сравнивается с элементами в отсортированной части массива и вставляется на правильное место.
➡️Преимущества и недостатки
Преимущество сортировки вставками в том, что она эффективна для небольших массивов и для массивов, которые уже частично отсортированы. Она также стабильна, что означает, что она сохраняет исходный порядок равных элементов. Однако, она не эффективна для больших массивов, так как требует больше операций сравнения и обмена элементов, чем другие алгоритмы сортировки.
🐍Pythoner
30 · 2.2K ·