The following code implements an in-place Radix sort with O(k) space overhead. It currently doesn’t deal with signed values however that should be relatively easy to add this, the high bit just needs to be sorted in reverse order.<\/p>\n
Unlike comparison sorts Radix sort only operates on integers with a complexity linear in the terms of the number of elements in the list (n) as a multiple of the number of digits in the integer. The implementation below operates in base 2.<\/p>\n
This implementation sorts each bit in turn starting with the most significant bit. It operates by maintaining pointers to the top and bottom (I term them left and right below) of the array shuffling those elements with one at the current bit position to the left and zero to the right. It does this by swapping elements each time it encounters a pair in the wrong place and moving the left and right pointers toward each other until they meet.<\/p>\n
While this sorts a single bit position, in order to sort the entire array the algorithm proceeds recursively. Once the one’s and zero’s have been sorted in the current position the Radix sort proceeds to sort all the one’s for the next lowest bit, and all the zero’s for the next lowest bit separately. While most easily described recursively, the implementation keeps track of the partitions in a vector and sorts these in a loop.<\/p>\n
The implementation below keeps track of all the bin partitions, and thus space overhead is O(2^k) where k is the number of digits. A recursive solution would possibly be more efficient, as the algorithm would not need to keep track of all partitions down to the final bit.<\/p>\n
\r\n#include <iostream>\r\n#include <vector>\r\n#include <stdint.h>\r\n#include <stdlib.h>\r\n#include <stdio.h>\r\n\r\nusing namespace std;\r\n\r\nint bits = 32;\r\n\r\nvoid dump_array(vector<int32_t> array);\r\nvoid bin_dump(int32_t v);\r\nvoid inplace_radix_sort_bit(vector<int32_t> &a,int start,int end,int bit,int &breakpoint);\r\n\r\nvoid swap(vector<int32_t> &a,int l,int r) {\r\n\r\n int32_t x = a[l];\r\n a[l] = a[r];\r\n a[r] = x;\r\n}\r\n\r\nbool bit_is_set(int32_t v,int bit) {\r\n if((v & (1 << bit)) > 0) return true;\r\n else return false;\r\n}\r\n\r\n\r\nvoid inplace_radix_sort(vector<int32_t> &a) {\r\n\r\n int breakpoint;\r\n vector<int> breakpoints;\r\n\r\n inplace_radix_sort_bit(a,0,a.size(),bits-1,breakpoint);\r\n breakpoints.push_back(0);\r\n breakpoints.push_back(breakpoint);\r\n breakpoints.push_back(a.size());\r\n\r\n for(int bit=bits-2;bit>=0;bit--) {\r\n\r\n cout << "breakpoints: ";\r\n for(int n=0;n<breakpoints.size();n++) cout << breakpoints[n] << " ";\r\n cout << endl;\r\n\r\n vector<int> newbreakpoints;\r\n for(int n=0;n<breakpoints.size()-1;n++) {\r\n if(breakpoints[n] != breakpoints[n+1])\r\n \/\/ inplace_radix_sort_bit(a,breakpoints[n]+1,breakpoints[n+1],bit,breakpoint);\r\n inplace_radix_sort_bit(a,breakpoints[n],breakpoints[n+1]-1,bit,breakpoint);\r\n newbreakpoints.push_back(breakpoint);\r\n }\r\n\r\n \/\/ create new breakpoint list (equiv for recursion)\r\n vector<int> mergebreakpoints;\r\n for(int n=0;n<breakpoints.size();n++) {\r\n mergebreakpoints.push_back(breakpoints[n]);\r\n if(n!=(breakpoints.size()-1)) mergebreakpoints.push_back(newbreakpoints[n]);\r\n }\r\n breakpoints = mergebreakpoints;\r\n\r\n \/\/ remove duplicates\r\n vector<int> cleanedbreakpoints;\r\n cleanedbreakpoints.push_back(breakpoints[0]);\r\n for(int n=1;n<breakpoints.size();n++) {\r\n if(breakpoints[n] != breakpoints[n-1]) cleanedbreakpoints.push_back(breakpoints[n]);\r\n }\r\n breakpoints = cleanedbreakpoints;\r\n }\r\n\r\n}\r\n\r\nvoid inplace_radix_sort_bit(vector<int32_t> &a,int start,int end,int bit,int &breakpoint) {\r\n\r\n \/\/ sort each bit posiiton\r\n\r\n cout << "sorting bit: " << bit << " pos: " << start << " " << end << endl;\r\n int l_pos = start;\r\n int r_pos = end;\r\n\r\n for(;l_pos < r_pos;) {\r\n cout << "l_pos: " << l_pos << " r_pos: " << r_pos << endl;\r\n cout << "comparing: " << a[l_pos] << " " << a[r_pos] << " ";\r\n bin_dump(a[l_pos]);\r\n cout << " ";\r\n bin_dump(a[r_pos]);\r\n cout << endl;\r\n \r\n bool l_bit = bit_is_set(a[l_pos],bit);\r\n bool r_bit = bit_is_set(a[r_pos],bit);\r\n if(l_bit) cout << "l_bit: 1" << endl; else cout << "l_bit: 0" << endl;\r\n if(r_bit) cout << "r_bit: 1" << endl; else cout << "r_bit: 0" << endl;\r\n\r\n if(!l_bit && r_bit) { swap(a,l_pos,r_pos); l_pos++; r_pos--; cout << "swp" << endl; if(l_pos == r_pos) if(bit_is_set(a[l_pos],bit)) {l_pos++; break;}} else\r\n if( l_bit && !r_bit) { l_pos++; r_pos--; cout << "10 linc rdec" << endl; } else\r\n if( l_bit && r_bit) { l_pos++; cout << "11 linc" << endl; if(l_pos == r_pos) {l_pos++; break;}} else\r\n if(!l_bit && !r_bit) { r_pos--; cout << "00 rdec" << endl; if(l_pos == r_pos) { break;}}\r\n }\r\n breakpoint = l_pos;\r\n dump_array(a);\r\n}\r\n\r\nvoid bin_dump(int32_t v) {\r\n\r\n for(int n=bits-1;n>=0;n--) {\r\n if(v & (1 << n)) cout << "1"; else cout << "0";\r\n }\r\n\r\n}\r\n\r\nvoid dump_array(vector<int32_t> array) {\r\n \r\n for(int n=0;n<array.size();n++) {\r\n printf("%20d ",array[n]);\r\n bin_dump(array[n]);\r\n cout << endl;\r\n }\r\n\r\n}\r\n\r\nint main() {\r\n\r\n vector<int32_t> array;\r\n for(int n=0;n<20;n++) {\r\n array.push_back(rand());\r\n }\r\n\r\n cout << "random array" << endl;\r\n dump_array(array);\r\n\r\n inplace_radix_sort(array);\r\n\r\n cout << "sorted array" << endl;\r\n dump_array(array);\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"The following code implements an in-place Radix sort with O(k) space overhead. It currently doesn’t deal with signed values however that should be relatively easy to add this, the high bit just needs to be sorted in reverse order. Unlike comparison sorts Radix sort only operates on integers with a complexity linear in the terms […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[1],"tags":[],"class_list":["post-2442","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p1RRoU-Do","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/2442","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/comments?post=2442"}],"version-history":[{"count":4,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/2442\/revisions"}],"predecessor-version":[{"id":2447,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/2442\/revisions\/2447"}],"wp:attachment":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/media?parent=2442"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/categories?post=2442"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/tags?post=2442"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}