Shell Sort – uma variante da classificação por inserção com combinação preliminar de uma matriz de números.
Precisamos lembrar como funciona a classificação por inserção:
1. Um loop é iniciado do zero até o final do loop, assim o array é dividido em duas partes
2. Para a parte esquerda, um segundo loop é iniciado, comparando os elementos da direita para a esquerda, o elemento menor à direita é descartado até que um elemento menor à esquerda seja encontrado
3. No final de ambos os loops, obtemos uma lista ordenada
Era uma vez, o cientista da computação Donald Schell se perguntou como melhorar o algoritmo de classificação por inserção. Ele também teve a ideia de primeiro percorrer o array em dois ciclos, mas a uma certa distância, reduzindo gradativamente o “pente” até que ele se transforme em um algoritmo regular de ordenação por inserção. Tudo é realmente tão simples, sem armadilhas, aos dois ciclos acima acrescentamos outro, no qual vamos reduzindo gradativamente o tamanho do “pente”. A única coisa que você precisa fazer é verificar a distância ao comparar para que ela não ultrapasse o array.
Um tópico realmente interessante é escolher a sequência para alterar o comprimento da comparação a cada iteração do primeiro loop. É interessante porque o desempenho do algoritmo depende disso.
A tabela de opções conhecidas e complexidade de tempo pode ser encontrada aqui: https: //en.wikipedia.org/wiki/Shellsort#Gap_sequences
Pessoas diferentes estiveram envolvidas no cálculo da distância ideal, aparentemente, esse assunto era muito interessante para elas. Eles não poderiam simplesmente executar Ruby e chamar o algoritmo sort() mais rápido?
Em geral, essas pessoas estranhas escreveram dissertações sobre o tema do cálculo da distância/gap do “pente” para o algoritmo Shell. Simplesmente usei os resultados do trabalho deles e verifiquei 5 tipos de sequências, Hibbard, Knuth-Pratt, Chiura, Sedgwick.
import time
import random
from functools import reduce
import math
DEMO_MODE = False
if input("Demo Mode Y/N? ").upper() == "Y":
DEMO_MODE = True
class Colors:
BLUE = '\033[94m'
RED = '\033[31m'
END = '\033[0m'
def swap(list, lhs, rhs):
list[lhs], list[rhs] = list[rhs], list[lhs]
return list
def colorPrintoutStep(numbers: List[int], lhs: int, rhs: int):
for index, number in enumerate(numbers):
if index == lhs:
print(f"{Colors.BLUE}", end = "")
elif index == rhs:
print(f"{Colors.RED}", end = "")
print(f"{number},", end = "")
if index == lhs or index == rhs:
print(f"{Colors.END}", end = "")
if index == lhs or index == rhs:
print(f"{Colors.END}", end = "")
print("\n")
input(">")
def ShellSortLoop(numbers: List[int], distanceSequence: List[int]):
distanceSequenceIterator = reversed(distanceSequence)
while distance:= next(distanceSequenceIterator, None):
for sortArea in range(0, len(numbers)):
for rhs in reversed(range(distance, sortArea + 1)):
lhs = rhs - distance
if DEMO_MODE:
print(f"Distance: {distance}")
colorPrintoutStep(numbers, lhs, rhs)
if numbers[lhs] > numbers[rhs]:
swap(numbers, lhs, rhs)
else:
break
def ShellSort(numbers: List[int]):
global ShellSequence
ShellSortLoop(numbers, ShellSequence)
def HibbardSort(numbers: List[int]):
global HibbardSequence
ShellSortLoop(numbers, HibbardSequence)
def ShellPlusKnuttPrattSort(numbers: List[int]):
global KnuttPrattSequence
ShellSortLoop(numbers, KnuttPrattSequence)
def ShellPlusCiuraSort(numbers: List[int]):
global CiuraSequence
ShellSortLoop(numbers, CiuraSequence)
def ShellPlusSedgewickSort(numbers: List[int]):
global SedgewickSequence
ShellSortLoop(numbers, SedgewickSequence)
def insertionSort(numbers: List[int]):
global insertionSortDistanceSequence
ShellSortLoop(numbers, insertionSortDistanceSequence)
def defaultSort(numbers: List[int]):
numbers.sort()
def measureExecution(inputNumbers: List[int], algorithmName: str, algorithm):
if DEMO_MODE:
print(f"{algorithmName} started")
numbers = inputNumbers.copy()
startTime = time.perf_counter()
algorithm(numbers)
endTime = time.perf_counter()
print(f"{algorithmName} performance: {endTime - startTime}")
def sortedNumbersAsString(inputNumbers: List[int], algorithm) -> str:
numbers = inputNumbers.copy()
algorithm(numbers)
return str(numbers)
if DEMO_MODE:
maximalNumber = 10
numbersCount = 10
else:
maximalNumber = 10
numbersCount = random.randint(10000, 20000)
randomNumbers = [random.randrange(1, maximalNumber) for i in range(numbersCount)]
ShellSequenceGenerator = lambda n: reduce(lambda x, _: x + [int(x[-1]/2)], range(int(math.log(numbersCount, 2))), [int(numbersCount / 2)])
ShellSequence = ShellSequenceGenerator(randomNumbers)
ShellSequence.reverse()
ShellSequence.pop()
HibbardSequence = [
0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095,
8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575,
2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727,
268435455, 536870911, 1073741823, 2147483647, 4294967295, 8589934591
]
KnuttPrattSequence = [
1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720,
797161, 2391484, 7174453, 21523360, 64570081, 193710244, 581130733,
1743392200, 5230176601, 15690529804, 47071589413
]
CiuraSequence = [
1, 4, 10, 23, 57, 132, 301, 701, 1750, 4376,
10941, 27353, 68383, 170958, 427396, 1068491,
2671228, 6678071, 16695178, 41737946, 104344866,
260862166, 652155416, 1630388541
]
SedgewickSequence = [
1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905,
8929, 16001, 36289, 64769, 146305, 260609, 587521,
1045505, 2354689, 4188161, 9427969, 16764929, 37730305,
67084289, 150958081, 268386305, 603906049, 1073643521,
2415771649, 4294770689, 9663381505, 17179475969
]
insertionSortDistanceSequence = [1]
algorithms = {
"Default Python Sort": defaultSort,
"Shell Sort": ShellSort,
"Shell + Hibbard" : HibbardSort,
"Shell + Prat, Knutt": ShellPlusKnuttPrattSort,
"Shell + Ciura Sort": ShellPlusCiuraSort,
"Shell + Sedgewick Sort": ShellPlusSedgewickSort,
"Insertion Sort": insertionSort
}
for name, algorithm in algorithms.items():
measureExecution(randomNumbers, name, algorithm)
reference = sortedNumbersAsString(randomNumbers, defaultSort)
for name, algorithm in algorithms.items():
if sortedNumbersAsString(randomNumbers, algorithm) != reference:
print("Sorting validation failed")
exit(1)
print("Sorting validation success")
exit(0)
Na minha implementação, para um conjunto aleatório de números, as lacunas mais rápidas são Sedgwick e Hibbard.
meupy
Gostaria também de mencionar o analisador de tipagem estática para Python 3 – meu Deus. Ajuda a resolver os problemas inerentes às linguagens com digitação dinâmica, nomeadamente, elimina a possibilidade de colar algo onde não é necessário.
Como dizem programadores experientes, “a digitação estática não é necessária quando você tem uma equipe de profissionais”, um dia todos nos tornaremos profissionais, escreveremos código em total unidade e compreensão com as máquinas, mas por enquanto você pode usar utilitários semelhantes e linguagens de tipo estaticamente.
Links
https://gitlab.com/demensdeum /algoritmos/-/tree/master/sortAlgorithms/shellSort
http://mypy-lang.org/
Fontes
https://dl.acm.org/doi/10.1145/368370.368387
https://en.wikipedia.org/wiki/Shellsort
http://rosettacode.org/wiki/Sorting_algorithms/Shell_sort
https://ru.wikipedia.org/wiki/Сортировка_Шелла
https://neerc.ifmo.ru/wiki/index.php?title=Сортировка_Шелла
https://twitter.com/gvanrossum/status/700741601966985216
