Сортировка на Шел. Примери и свойства.
Сортировката на Шел (Shell sort) е алгоритъм за сортиране, който работи като сравнява елементите, които са на разстояние друг от друг. Това разстояние се нарича "шаг" (gap). След това елементите се сравняват и разменят с помощта на алгоритъма за сортиране по метода на мехурчето (bubble sort). След това се намаля шагът и се повтаря процесът. Процесът се продължава докато шагът стане равен на 1.
Пример за реализация на сортировка на Шел на Python:
def shell_sort(arr):
n = len(arr)
h = n // 2 # Начален размер на стъпката
while h > 0:
for i in range(h, n):
temp = arr[i]
j = i
while j >= h and arr[j - h] > temp:
arr[j] = arr[j - h]
j -= h
arr[j] = temp
h //= 2 # Намаляване на размера на стъпкатa
return arr;
Постъпателни алгоритми – синтез на кодове на Huffman(компресия на файл).
Постъпателни алгоритми (Greedy):
Постъпателните алгоритми, или алгоритми, базирани на жадните решения, представляват стратегия за решаване на проблеми, при която възможно най-доброто решение се избира на всяка стъпка. Алгоритмът прави локални оптимални избори, без да се интересува от това, какви последствия могат да възникнат в бъдеще. Този вид алгоритми е често използван при решаване на оптимизационни проблеми и задачи, в които няма нужда от глобално оптимално решение.
Алгоритъмът на Хъфман (Huffman) е често използван за компресия на данни. Този алгоритъм предоставя постъпателен метод за създаване на префиксен код, който се използва за представяне на символи с различни дължини на кода, така че няма код, който е префикс на друг.
https://dvt32.blogspot.com/2017/01/algorithmo-2.html
Сподели с приятели: |