Shell Sort \u2013 eine Variante der Einf\u00fcgungssortierung mit vorl\u00e4ufiger K\u00e4mmung eines Zahlenarrays.<\/p>\n
Wir m\u00fcssen uns daran erinnern, wie die Einf\u00fcgungssortierung funktioniert:<\/p>\n
1. Eine Schleife wird von Null bis zum Ende der Schleife gestartet, wodurch das Array in zwei Teile geteilt wird
2. F\u00fcr den linken Teil wird eine zweite Schleife gestartet, die Elemente von rechts nach links vergleicht. Das kleinere Element auf der rechten Seite wird gel\u00f6scht, bis ein kleineres Element auf der linken Seite gefunden wird
3. Am Ende beider Schleifen erhalten wir eine sortierte Liste<\/p>\n
Es war einmal der Informatiker Donald Schell, der sich fragte, wie man den Einf\u00fcgungssortierungsalgorithmus verbessern k\u00f6nnte. Er kam auch auf die Idee, das Array zun\u00e4chst in zwei Zyklen zu durchlaufen, jedoch in einem bestimmten Abstand, und den \u201eKamm\u201c schrittweise zu verkleinern, bis daraus ein regul\u00e4rer Einf\u00fcgungssortierungsalgorithmus wird. Alles ist wirklich so einfach, keine Fallstricke. Zu den beiden oben genannten Zyklen f\u00fcgen wir einen weiteren hinzu, in dem wir die Gr\u00f6\u00dfe des \u201eKamms\u201c schrittweise reduzieren. Das Einzige, was Sie tun m\u00fcssen, ist, beim Vergleich den Abstand zu \u00fcberpr\u00fcfen, damit er nicht \u00fcber das Array hinausgeht.<\/p>\n
Ein wirklich interessantes Thema ist die Auswahl der Reihenfolge zum \u00c4ndern der Vergleichsl\u00e4nge bei jeder Iteration der ersten Schleife. Dies ist deshalb interessant, weil die Leistung des Algorithmus davon abh\u00e4ngt.<\/p>\n
Die Tabelle bekannter Optionen und Zeitkomplexit\u00e4t finden Sie hier: https: \/\/en .wikipedia.org\/wiki\/Shellsort#Gap_sequences<\/a><\/p>\n An der Berechnung des idealen Abstands waren verschiedene Personen beteiligt; f\u00fcr sie war dieses Thema offenbar so interessant. K\u00f6nnten sie nicht einfach Ruby ausf\u00fchren und den schnellsten sort()-Algorithmus aufrufen?<\/p>\n Im Allgemeinen haben diese seltsamen Leute Dissertationen zum Thema der Berechnung des Abstands\/der L\u00fccke des \u201eKamms\u201c f\u00fcr den Shell-Algorithmus geschrieben. Ich habe einfach die Ergebnisse ihrer Arbeit verwendet und f\u00fcnf Arten von Sequenzen \u00fcberpr\u00fcft: Hibbard, Knuth-Pratt, Chiura, Sedgwick.<\/p>\n In meiner Implementierung sind f\u00fcr einen zuf\u00e4lligen Satz von Zahlen die schnellsten L\u00fccken Sedgwick und Hibbard.<\/p>\n Ich m\u00f6chte auch den statischen Typisierungsanalysator f\u00fcr Python 3 erw\u00e4hnen – mypy. Hilft bei der Bew\u00e4ltigung der Probleme, die Sprachen mit dynamischer Eingabe innewohnen, indem es die M\u00f6glichkeit ausschlie\u00dft, etwas dort festzuhalten, wo es nicht ben\u00f6tigt wird.<\/p>\n Wie erfahrene Programmierer sagen: \u201eStatisches Tippen ist nicht erforderlich, wenn Sie ein Team von Profis haben.\u201c Eines Tages werden wir alle Profis, wir werden Code in v\u00f6lliger Einheit und Verst\u00e4ndnis mit Maschinen schreiben, aber im Moment k\u00f6nnen Sie \u00e4hnliche Dienstprogramme verwenden und statisch typisierte Sprachen.<\/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 eine Variante der Einf\u00fcgungssortierung mit vorl\u00e4ufiger K\u00e4mmung eines Zahlenarrays. Wir m\u00fcssen uns daran erinnern, wie die Einf\u00fcgungssortierung funktioniert: 1. Eine Schleife wird von Null bis zum Ende der Schleife gestartet, wodurch das Array in zwei Teile geteilt wird2. F\u00fcr den linken Teil wird eine zweite Schleife gestartet, die Elemente von rechts nachContinue reading “Muschelsortierung”<\/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":"de","enabled_languages":["en","ru","zh","de","fr","ja","pt","hi"],"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},"hi":{"title":false,"content":false,"excerpt":false}}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/posts\/3311","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/comments?post=3311"}],"version-history":[{"count":15,"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/posts\/3311\/revisions"}],"predecessor-version":[{"id":3884,"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/posts\/3311\/revisions\/3884"}],"wp:attachment":[{"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/media?parent=3311"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/categories?post=3311"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/de\/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>\nmypy<\/h3>\n
Links<\/h3>\n
http:\/\/mypy-lang.org\/<\/a><\/p>\nQuellen<\/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":"