Shell Sort – une variante du tri par insertion avec peignage préliminaire d’un tableau de nombres.
Nous devons nous rappeler comment fonctionne le tri par insertion :
1. Une boucle commence de zéro jusqu’à la fin de la boucle, le tableau est donc divisé en deux parties
2. Pour la partie gauche, une deuxième boucle est lancée, comparant les éléments de droite à gauche, le plus petit élément de droite est déposé jusqu’à ce qu’un plus petit élément de gauche soit trouvé
3. A la fin des deux boucles, on obtient une liste triée
Il était une fois l’informaticien Donald Schell qui se demandait comment améliorer l’algorithme de tri par insertion. Il a également eu l’idée de parcourir d’abord le tableau en deux cycles, mais à une certaine distance, en réduisant progressivement le « peigne » jusqu’à ce qu’il se transforme en un algorithme de tri par insertion régulier. Tout est vraiment si simple, pas d’embûches, aux deux cycles ci-dessus on en ajoute un autre, dans lequel on réduit progressivement la taille du « peigne ». La seule chose que vous devez faire est de vérifier la distance lors de la comparaison afin qu’elle ne dépasse pas le tableau.
Un sujet vraiment intéressant est le choix de la séquence permettant de modifier la longueur de comparaison à chaque itération de la première boucle. C’est intéressant car les performances de l’algorithme en dépendent.
Le tableau des options connues et de la complexité temporelle peut être trouvé ici : https : //fr .wikipedia.org/wiki/Shellsort#Gap_sequences
Différentes personnes ont participé au calcul de la distance idéale ; apparemment, ce sujet les intéressait beaucoup. Ne pourraient-ils pas simplement exécuter Ruby et appeler l’algorithme sort() le plus rapide ?
En général, ces personnes étranges ont écrit des dissertations sur le thème du calcul de la distance/écart du « peigne » pour l’algorithme Shell. J’ai simplement utilisé les résultats de leurs travaux et vérifié 5 types de séquences, 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)
Dans mon implémentation, pour un ensemble aléatoire de nombres, les écarts les plus rapides sont Sedgwick et Hibbard.
monpy
Je voudrais également mentionner l’analyseur de typage statique pour Python 3 – mypy. Aide à faire face aux problèmes inhérents aux langages à typage dynamique, à savoir qu’il élimine la possibilité de coller quelque chose là où ce n’est pas nécessaire.
Comme le disent les programmeurs expérimentés, “la saisie statique n’est pas nécessaire lorsque vous avez une équipe de professionnels”, un jour nous deviendrons tous des professionnels, nous écrirons du code en pleine unité et compréhension avec les machines, mais pour l’instant vous pouvez utiliser des utilitaires similaires. et les langages typés statiquement.
Liens
https://gitlab.com/demensdeum /algorithms/-/tree/master/sortAlgorithms/shellSort
http://mypy-lang.org/
Sources
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