Tri par seaux\u00a0: tri par seaux. L’algorithme est similaire au tri par comptage, \u00e0 la diff\u00e9rence que les nombres sont collect\u00e9s dans des plages de \u00ab seaux \u00bb, puis les seaux sont tri\u00e9s \u00e0 l’aide de tout autre algorithme de tri suffisamment productif, et l’\u00e9tape finale consiste \u00e0 d\u00e9plier les \u00ab seaux \u00bb par un, ce qui donne une liste tri\u00e9e <\/p>\n
La complexit\u00e9 temporelle de l’algorithme est O(nk). L’algorithme fonctionne en temps lin\u00e9aire pour des donn\u00e9es ob\u00e9issant \u00e0 une loi de distribution uniforme. Pour faire simple, les \u00e9l\u00e9ments doivent \u00eatre dans une certaine plage, sans \u00ab pointes \u00bb, par exemple des nombres de 0,0 \u00e0 1,0. Si parmi ces nombres il y en a 4 ou 999, alors selon les lois de la cour, une telle rang\u00e9e n’est plus consid\u00e9r\u00e9e comme \u00ab paire \u00bb. <\/p>\n
Exemple d’impl\u00e9mentation dans Julia\u00a0:<\/p>\n
buckets = Vector{Vector{Int}}()\n \n for i in 0:bucketsCount - 1\n bucket = Vector{Int}()\n push!(buckets, bucket)\n end\n\n maxNumber = maximum(numbers)\n\n for i in 0:length(numbers) - 1\n bucketIndex = 1 + Int(floor(bucketsCount * numbers[1 + i] \/ (maxNumber + 1)))\n push!(buckets[bucketIndex], numbers[1 + i])\n end\n\n for i in 0:length(buckets) - 1\n bucketIndex = 1 + i\n buckets[bucketIndex] = sort(buckets[bucketIndex])\n end\n\n flat = [(buckets...)...]\n print(flat, \"\\n\")\n\nend\n\nnumbersCount = 10\nmaxNumber = 10\nnumbers = rand(1:maxNumber, numbersCount)\nprint(numbers,\"\\n\")\nbucketsCount = 10\nbucketSort(numbers, bucketsCount)<\/code><\/pre>\n<\/div>\n\u041d\u0430 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0442\u0430\u043a\u0436\u0435 \u0432\u043b\u0438\u044f\u0435\u0442 \u0447\u0438\u0441\u043b\u043e \u0432\u0435\u0434\u0435\u0440, \u0434\u043b\u044f \u0431\u043e\u043b\u044c\u0448\u0435\u0433\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0447\u0438\u0441\u0435\u043b \u043b\u0443\u0447\u0448\u0435 \u0432\u0437\u044f\u0442\u044c \u0431\u043e\u043b\u044c\u0448\u0435\u0435 \u0447\u0438\u0441\u043b\u043e \u0432\u0435\u0434\u0435\u0440 (Algorithms in a nutshell by George T. Heineman)<\/p>\n
\u0421\u0441\u044b\u043b\u043a\u0438<\/h3>\n
https:\/\/gitlab.com\/demensdeum\/algorithms\/-\/tree\/master\/sortAlgorithms\/bucketSort<\/a><\/p>\n\u0418\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0438<\/h3>\n
https:\/\/www.youtube.com\/watch?v=VuXbEb5ywrU<\/a>
\nhttps:\/\/www.youtube.com\/watch?v=ELrhrrCjDOA<\/a>
\nhttps:\/\/medium.com\/karuna-sehgal\/an-introduction-to-bucket-sort-62aa5325d124<\/a>
\nhttps:\/\/www.geeksforgeeks.org\/bucket-sort-2\/<\/a>
\nhttps:\/\/ru.wikipedia.org\/wiki\/%D0%91%D0%BB%D0%BE%D1%87%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0<\/a>
\nhttps:\/\/www.youtube.com\/watch?v=LPrF9yEKTks<\/a>
\nhttps:\/\/en.wikipedia.org\/wiki\/Bucket_sort<\/a>
\nhttps:\/\/julialang.org\/<\/a>
\nhttps:\/\/www.oreilly.com\/library\/view\/algorithms-in-a\/9780596516246\/ch04s08.html<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"Tri par seaux\u00a0: tri par seaux. L’algorithme est similaire au tri par comptage, \u00e0 la diff\u00e9rence que les nombres sont collect\u00e9s dans des plages de \u00ab seaux \u00bb, puis les seaux sont tri\u00e9s \u00e0 l’aide de tout autre algorithme de tri suffisamment productif, et l’\u00e9tape finale consiste \u00e0 d\u00e9plier les \u00ab seaux \u00bb par un,Continue reading “Tri par seau”<\/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,206,190],"class_list":["post-3404","post","type-post","status-publish","format-standard","hentry","category-techie","category-tutorials","tag-algorithms","tag-bucketsort","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\/3404","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=3404"}],"version-history":[{"count":5,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts\/3404\/revisions"}],"predecessor-version":[{"id":3872,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts\/3404\/revisions\/3872"}],"wp:attachment":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/media?parent=3404"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/categories?post=3404"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/tags?post=3404"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}