Bucket Sort \u2013 sorting by buckets. The algorithm is similar to counting sort, with the difference that the numbers are collected in \u201cbuckets\u201d-ranges, then the buckets are sorted using any other, sufficiently productive, sorting algorithm, and the final chord is the unfolding of the \u201cbuckets\u201d one by one, resulting in a sorted list.<\/p>\n
The algorithm’s time complexity is O(nk). The algorithm works in linear time for data that obeys a uniform distribution law. To put it simply, the elements must be in a certain range, without “spikes”, for example, numbers from 0.0 to 1.0. If among such numbers there are 4 or 999, then such a series is no longer considered “even” according to the yard laws.<\/p>\n
Example of implementation in Julia:<\/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":"Bucket Sort \u2013 sorting by buckets. The algorithm is similar to counting sort, with the difference that the numbers are collected in \u201cbuckets\u201d-ranges, then the buckets are sorted using any other, sufficiently productive, sorting algorithm, and the final chord is the unfolding of the \u201cbuckets\u201d one by one, resulting in a sorted list. The algorithm’sContinue reading “Bucket Sort”<\/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":"en","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\/wp-json\/wp\/v2\/posts\/3404","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/comments?post=3404"}],"version-history":[{"count":5,"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/posts\/3404\/revisions"}],"predecessor-version":[{"id":3872,"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/posts\/3404\/revisions\/3872"}],"wp:attachment":[{"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/media?parent=3404"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/categories?post=3404"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/tags?post=3404"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}