Shell Sort \u2013 uma variante da classifica\u00e7\u00e3o por inser\u00e7\u00e3o com combina\u00e7\u00e3o preliminar de uma matriz de n\u00fameros.<\/p>\n
Precisamos lembrar como funciona a classifica\u00e7\u00e3o por inser\u00e7\u00e3o:<\/p>\n
1. Um loop \u00e9 iniciado do zero at\u00e9 o final do loop, assim o array \u00e9 dividido em duas partes
2. Para a parte esquerda, um segundo loop \u00e9 iniciado, comparando os elementos da direita para a esquerda, o elemento menor \u00e0 direita \u00e9 descartado at\u00e9 que um elemento menor \u00e0 esquerda seja encontrado
3. No final de ambos os loops, obtemos uma lista ordenada<\/p>\n
Era uma vez, o cientista da computa\u00e7\u00e3o Donald Schell se perguntou como melhorar o algoritmo de classifica\u00e7\u00e3o por inser\u00e7\u00e3o. Ele tamb\u00e9m teve a ideia de primeiro percorrer o array em dois ciclos, mas a uma certa dist\u00e2ncia, reduzindo gradativamente o \u201cpente\u201d at\u00e9 que ele se transforme em um algoritmo regular de ordena\u00e7\u00e3o por inser\u00e7\u00e3o. Tudo \u00e9 realmente t\u00e3o simples, sem armadilhas, aos dois ciclos acima acrescentamos outro, no qual vamos reduzindo gradativamente o tamanho do \u201cpente\u201d. A \u00fanica coisa que voc\u00ea precisa fazer \u00e9 verificar a dist\u00e2ncia ao comparar para que ela n\u00e3o ultrapasse o array.<\/p>\n
Um t\u00f3pico realmente interessante \u00e9 escolher a sequ\u00eancia para alterar o comprimento da compara\u00e7\u00e3o a cada itera\u00e7\u00e3o do primeiro loop. \u00c9 interessante porque o desempenho do algoritmo depende disso.<\/p>\n
A tabela de op\u00e7\u00f5es conhecidas e complexidade de tempo pode ser encontrada aqui: https: \/\/en.wikipedia.org\/wiki\/Shellsort#Gap_sequences<\/a><\/p>\n Pessoas diferentes estiveram envolvidas no c\u00e1lculo da dist\u00e2ncia ideal, aparentemente, esse assunto era muito interessante para elas. Eles n\u00e3o poderiam simplesmente executar Ruby e chamar o algoritmo sort() mais r\u00e1pido?<\/p>\n Em geral, essas pessoas estranhas escreveram disserta\u00e7\u00f5es sobre o tema do c\u00e1lculo da dist\u00e2ncia\/gap do \u201cpente\u201d para o algoritmo Shell. Simplesmente usei os resultados do trabalho deles e verifiquei 5 tipos de sequ\u00eancias, Hibbard, Knuth-Pratt, Chiura, Sedgwick.<\/p>\n Na minha implementa\u00e7\u00e3o, para um conjunto aleat\u00f3rio de n\u00fameros, as lacunas mais r\u00e1pidas s\u00e3o Sedgwick e Hibbard.<\/p>\n Gostaria tamb\u00e9m de mencionar o analisador de tipagem est\u00e1tica para Python 3 – meu Deus. Ajuda a resolver os problemas inerentes \u00e0s linguagens com digita\u00e7\u00e3o din\u00e2mica, nomeadamente, elimina a possibilidade de colar algo onde n\u00e3o \u00e9 necess\u00e1rio.<\/p>\n Como dizem programadores experientes, \u201ca digita\u00e7\u00e3o est\u00e1tica n\u00e3o \u00e9 necess\u00e1ria quando voc\u00ea tem uma equipe de profissionais\u201d, um dia todos nos tornaremos profissionais, escreveremos c\u00f3digo em total unidade e compreens\u00e3o com as m\u00e1quinas, mas por enquanto voc\u00ea pode usar utilit\u00e1rios semelhantes e linguagens de tipo estaticamente.<\/p>\n https:\/\/gitlab.com\/demensdeum \/algoritmos\/-\/tree\/master\/sortAlgorithms\/shellSort<\/a> https:\/\/dl.acm.org\/doi\/10.1145\/368370.368387 <\/a> Shell Sort \u2013 uma variante da classifica\u00e7\u00e3o por inser\u00e7\u00e3o com combina\u00e7\u00e3o preliminar de uma matriz de n\u00fameros. Precisamos lembrar como funciona a classifica\u00e7\u00e3o por inser\u00e7\u00e3o: 1. Um loop \u00e9 iniciado do zero at\u00e9 o final do loop, assim o array \u00e9 dividido em duas partes2. Para a parte esquerda, um segundo loop \u00e9 iniciado, comparandoContinue reading “Classifica\u00e7\u00e3o de casca”<\/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":"pt","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\/pt\/wp-json\/wp\/v2\/posts\/3311","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/comments?post=3311"}],"version-history":[{"count":15,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/posts\/3311\/revisions"}],"predecessor-version":[{"id":3884,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/posts\/3311\/revisions\/3884"}],"wp:attachment":[{"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/media?parent=3311"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/categories?post=3311"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/pt\/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>\nmeupy<\/h3>\n
Links<\/h3>\n
http:\/\/mypy-lang.org\/<\/a><\/p>\nFontes<\/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":"