Shell Sort \u2013 une variante du tri par insertion avec peignage pr\u00e9liminaire d’un tableau de nombres.<\/p>\n
Nous devons nous rappeler comment fonctionne le tri par insertion\u00a0:<\/p>\n
1. Une boucle commence de z\u00e9ro jusqu’\u00e0 la fin de la boucle, le tableau est donc divis\u00e9 en deux parties
2. Pour la partie gauche, une deuxi\u00e8me boucle est lanc\u00e9e, comparant les \u00e9l\u00e9ments de droite \u00e0 gauche, le plus petit \u00e9l\u00e9ment de droite est d\u00e9pos\u00e9 jusqu’\u00e0 ce qu’un plus petit \u00e9l\u00e9ment de gauche soit trouv\u00e9
3. A la fin des deux boucles, on obtient une liste tri\u00e9e<\/p>\n
Il \u00e9tait une fois l’informaticien Donald Schell qui se demandait comment am\u00e9liorer l’algorithme de tri par insertion. Il a \u00e9galement eu l’id\u00e9e de parcourir d’abord le tableau en deux cycles, mais \u00e0 une certaine distance, en r\u00e9duisant progressivement le \u00ab peigne \u00bb jusqu’\u00e0 ce qu’il se transforme en un algorithme de tri par insertion r\u00e9gulier. Tout est vraiment si simple, pas d’emb\u00fbches, aux deux cycles ci-dessus on en ajoute un autre, dans lequel on r\u00e9duit progressivement la taille du \u00ab peigne \u00bb. La seule chose que vous devez faire est de v\u00e9rifier la distance lors de la comparaison afin qu’elle ne d\u00e9passe pas le tableau.<\/p>\n
Un sujet vraiment int\u00e9ressant est le choix de la s\u00e9quence permettant de modifier la longueur de comparaison \u00e0 chaque it\u00e9ration de la premi\u00e8re boucle. C’est int\u00e9ressant car les performances de l’algorithme en d\u00e9pendent.<\/p>\n
Le tableau des options connues et de la complexit\u00e9 temporelle peut \u00eatre trouv\u00e9 ici\u00a0: https\u00a0: \/\/fr .wikipedia.org\/wiki\/Shellsort#Gap_sequences<\/a><\/p>\n Diff\u00e9rentes personnes ont particip\u00e9 au calcul de la distance id\u00e9ale\u00a0; apparemment, ce sujet les int\u00e9ressait beaucoup. Ne pourraient-ils pas simplement ex\u00e9cuter Ruby et appeler l’algorithme sort() le plus rapide\u00a0?<\/p>\n En g\u00e9n\u00e9ral, ces personnes \u00e9tranges ont \u00e9crit des dissertations sur le th\u00e8me du calcul de la distance\/\u00e9cart du \u00ab peigne \u00bb pour l’algorithme Shell. J’ai simplement utilis\u00e9 les r\u00e9sultats de leurs travaux et v\u00e9rifi\u00e9 5 types de s\u00e9quences, Hibbard, Knuth-Pratt, Chiura, Sedgwick.<\/p>\n Dans mon impl\u00e9mentation, pour un ensemble al\u00e9atoire de nombres, les \u00e9carts les plus rapides sont Sedgwick et Hibbard.<\/p>\n Je voudrais \u00e9galement mentionner l’analyseur de typage statique pour Python 3 – mypy. Aide \u00e0 faire face aux probl\u00e8mes inh\u00e9rents aux langages \u00e0 typage dynamique, \u00e0 savoir qu’il \u00e9limine la possibilit\u00e9 de coller quelque chose l\u00e0 o\u00f9 ce n’est pas n\u00e9cessaire.<\/p>\n Comme le disent les programmeurs exp\u00e9riment\u00e9s, “la saisie statique n’est pas n\u00e9cessaire lorsque vous avez une \u00e9quipe de professionnels”, un jour nous deviendrons tous des professionnels, nous \u00e9crirons du code en pleine unit\u00e9 et compr\u00e9hension avec les machines, mais pour l’instant vous pouvez utiliser des utilitaires similaires. et les langages typ\u00e9s statiquement.<\/p>\n https:\/\/gitlab.com\/demensdeum \/algorithms\/-\/tree\/master\/sortAlgorithms\/shellSort<\/a> https:\/\/dl.acm.org\/doi\/10.1145\/368370.368387 <\/a> Shell Sort \u2013 une variante du tri par insertion avec peignage pr\u00e9liminaire d’un tableau de nombres. Nous devons nous rappeler comment fonctionne le tri par insertion\u00a0: 1. Une boucle commence de z\u00e9ro jusqu’\u00e0 la fin de la boucle, le tableau est donc divis\u00e9 en deux parties2. Pour la partie gauche, une deuxi\u00e8me boucle est lanc\u00e9e,Continue reading “Tri des coquilles”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[61,52],"tags":[131,197,190],"class_list":["post-3311","post","type-post","status-publish","format-standard","hentry","category-techie","category-tutorials","tag-algorithms","tag-shell-sorting","tag-sorting","entry"],"translation":{"provider":"WPGlobus","version":"3.0.2","language":"fr","enabled_languages":["en","ru","zh","de","fr","ja","pt"],"languages":{"en":{"title":true,"content":true,"excerpt":false},"ru":{"title":true,"content":true,"excerpt":false},"zh":{"title":true,"content":true,"excerpt":false},"de":{"title":true,"content":true,"excerpt":false},"fr":{"title":true,"content":true,"excerpt":false},"ja":{"title":true,"content":true,"excerpt":false},"pt":{"title":true,"content":true,"excerpt":false}}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts\/3311","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/comments?post=3311"}],"version-history":[{"count":15,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts\/3311\/revisions"}],"predecessor-version":[{"id":3884,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts\/3311\/revisions\/3884"}],"wp:attachment":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/media?parent=3311"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/categories?post=3311"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/tags?post=3311"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}import time\nimport random\nfrom functools import reduce\nimport math\n\nDEMO_MODE = False\n\nif input(\"Demo Mode Y\/N? \").upper() == \"Y\":\n DEMO_MODE = True\n\nclass Colors:\n BLUE = '\\033[94m'\n RED = '\\033[31m'\n END = '\\033[0m'\n\ndef swap(list, lhs, rhs):\n list[lhs], list[rhs] = list[rhs], list[lhs]\n return list\n\ndef colorPrintoutStep(numbers: List[int], lhs: int, rhs: int):\n for index, number in enumerate(numbers):\n if index == lhs:\n print(f\"{Colors.BLUE}\", end = \"\")\n elif index == rhs:\n print(f\"{Colors.RED}\", end = \"\")\n print(f\"{number},\", end = \"\")\n if index == lhs or index == rhs:\n print(f\"{Colors.END}\", end = \"\")\n if index == lhs or index == rhs:\n print(f\"{Colors.END}\", end = \"\")\n print(\"\\n\")\n input(\">\")\n\ndef ShellSortLoop(numbers: List[int], distanceSequence: List[int]):\n distanceSequenceIterator = reversed(distanceSequence)\n while distance:= next(distanceSequenceIterator, None):\n for sortArea in range(0, len(numbers)):\n for rhs in reversed(range(distance, sortArea + 1)):\n lhs = rhs - distance\n if DEMO_MODE:\n print(f\"Distance: {distance}\")\n colorPrintoutStep(numbers, lhs, rhs)\n if numbers[lhs] > numbers[rhs]:\n swap(numbers, lhs, rhs)\n else:\n break\n\ndef ShellSort(numbers: List[int]):\n global ShellSequence\n ShellSortLoop(numbers, ShellSequence)\n\ndef HibbardSort(numbers: List[int]):\n global HibbardSequence\n ShellSortLoop(numbers, HibbardSequence)\n\ndef ShellPlusKnuttPrattSort(numbers: List[int]):\n global KnuttPrattSequence\n ShellSortLoop(numbers, KnuttPrattSequence)\n\ndef ShellPlusCiuraSort(numbers: List[int]):\n global CiuraSequence\n ShellSortLoop(numbers, CiuraSequence)\n\ndef ShellPlusSedgewickSort(numbers: List[int]):\n global SedgewickSequence\n ShellSortLoop(numbers, SedgewickSequence)\n\ndef insertionSort(numbers: List[int]):\n global insertionSortDistanceSequence\n ShellSortLoop(numbers, insertionSortDistanceSequence)\n\ndef defaultSort(numbers: List[int]):\n numbers.sort()\n\ndef measureExecution(inputNumbers: List[int], algorithmName: str, algorithm):\n if DEMO_MODE:\n print(f\"{algorithmName} started\")\n numbers = inputNumbers.copy()\n startTime = time.perf_counter()\n algorithm(numbers)\n endTime = time.perf_counter()\n print(f\"{algorithmName} performance: {endTime - startTime}\")\n\ndef sortedNumbersAsString(inputNumbers: List[int], algorithm) -> str:\n numbers = inputNumbers.copy()\n algorithm(numbers)\n return str(numbers)\n\nif DEMO_MODE:\n maximalNumber = 10\n numbersCount = 10\nelse:\n maximalNumber = 10\n numbersCount = random.randint(10000, 20000)\n\nrandomNumbers = [random.randrange(1, maximalNumber) for i in range(numbersCount)]\n\nShellSequenceGenerator = lambda n: reduce(lambda x, _: x + [int(x[-1]\/2)], range(int(math.log(numbersCount, 2))), [int(numbersCount \/ 2)])\nShellSequence = ShellSequenceGenerator(randomNumbers)\nShellSequence.reverse()\nShellSequence.pop()\n\nHibbardSequence = [\n 0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095,\n 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575,\n 2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727,\n 268435455, 536870911, 1073741823, 2147483647, 4294967295, 8589934591\n]\n\nKnuttPrattSequence = [\n 1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720, \n 797161, 2391484, 7174453, 21523360, 64570081, 193710244, 581130733, \n 1743392200, 5230176601, 15690529804, 47071589413\n]\n\nCiuraSequence = [\n 1, 4, 10, 23, 57, 132, 301, 701, 1750, 4376, \n 10941, 27353, 68383, 170958, 427396, 1068491, \n 2671228, 6678071, 16695178, 41737946, 104344866, \n 260862166, 652155416, 1630388541\n]\n\nSedgewickSequence = [\n 1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905,\n 8929, 16001, 36289, 64769, 146305, 260609, 587521, \n 1045505, 2354689, 4188161, 9427969, 16764929, 37730305, \n 67084289, 150958081, 268386305, 603906049, 1073643521, \n 2415771649, 4294770689, 9663381505, 17179475969\n]\n\ninsertionSortDistanceSequence = [1]\n\nalgorithms = {\n \"Default Python Sort\": defaultSort,\n \"Shell Sort\": ShellSort,\n \"Shell + Hibbard\" : HibbardSort,\n \"Shell + Prat, Knutt\": ShellPlusKnuttPrattSort,\n \"Shell + Ciura Sort\": ShellPlusCiuraSort,\n \"Shell + Sedgewick Sort\": ShellPlusSedgewickSort,\n \"Insertion Sort\": insertionSort\n}\n\nfor name, algorithm in algorithms.items():\n measureExecution(randomNumbers, name, algorithm)\n\nreference = sortedNumbersAsString(randomNumbers, defaultSort)\n\nfor name, algorithm in algorithms.items():\n if sortedNumbersAsString(randomNumbers, algorithm) != reference:\n print(\"Sorting validation failed\")\n exit(1)\n\nprint(\"Sorting validation success\")\nexit(0)\n<\/code><\/pre>\n<\/div>\n<\/div>\nmonpy<\/h3>\n
Liens<\/h3>\n
http:\/\/mypy-lang.org\/<\/a><\/p>\nSources<\/h3>\n
https:\/\/en.wikipedia.org\/wiki\/Shellsort<\/a>
\nhttp:\/\/rosettacode.org\/wiki\/Sorting_algorithms\/Shell_sort<\/a>
\nhttps:\/\/ru.wikipedia.org\/wiki\/\u0421\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430_\u0428\u0435\u043b\u043b\u0430<\/a>
\nhttps:\/\/neerc.ifmo.ru\/wiki\/index.php?title=\u0421\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430_\u0428\u0435\u043b\u043b\u0430<\/a>
\nhttps:\/\/twitter.com\/gvanrossum\/status\/700741601966985216<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"