#radix sort

[quite-simple-actually]

This is so elegant omg, I never knew how that worked

it's so fast too! It needs more memory, but little time and processing power. I might get my hands on Assembly, to be able to touch individual bits, and write something like this, as an exercise in making things way too complicated to see how they work.

School year is over, so I have free time, so I will use this blog more often. Hopefully.

[facingissuesonit]

Radix Sort Program and Complexity (Big-O)

Radix Sort Program and Complexity (Big-O)

Radixsort sorts numeric data (integers or float) by considering a string of numbers where digit by digit sort starting from least significant digit position to most significant digit position. To sort these specific positions data counting sort as a subroutine.

Counting sortis a linear time sorting algorithm that sort in O(n+k) but that will worst in case of items range from 1 to n2 that sort in…

View On WordPress

[i-am-carbon14]

I was messing around with Radix Sort on images and changing the starting position and I made some cool sorted colors from the first image of random pixels

[joyjing1-blog]

Weekend Learning

Topics

Radix Sorting - bucket sorting

LSD - Least Significant Digit (start from ones digit, move <--)

MSD - Most Significant Digit (start from left digit, move -->)

Use nested buckets - MSD for 3-digit numbers ex:

Start with hundreds-place-digit % 10 bucket

Within that bucket, place in tens-place-digit % 10 bucket

Within that bucket, place in ones-place-digit % 10 bucket

Can mod by different size/number of buckets

Will take O(n) time to place elements - placing in sorted order

Will take O(n) time to retrieve elements in sorted order

Total sort time is O(n) time

Not a comparative sort, since merely placing elements

Can only work with arrays of integers

Good for when you have a set range of integes since sort is very fast

Bad for an infinite/unknown range, since can't set the appropriate number of buckets

Heaps - Binary tree where each parent is smaller than its children

Min Heap - default, what most people assume when talking about Heaps

Max Heap - binary tree where each parent is larger than its children

Often stored as an array where reading in a Breadth First manner

[1,2,3,4,5,6,7]

1 - root

2, 3 -- children of 1

4, 5 -- children of 2

6, 7 -- children of 3

Can reference parents/children by index

Parent of node i is node (i-1)/2

Children of node i are (i*2)+1 & (i*2)+2

O(n) time to place all elememnts

Heap Sort

Percolation - can either percolate up or percolate down

Percolating up - add a new element on the end of the array (become new leaf of tree), then compare it to its parent (using index). If it is smaller than its parent, swap positions. Compare to new parent. Continue this until new element is smaller than its parent (in correct position)

Percolating down - add a new element to the beginning of the array (make it the new root). Of its two children, swap with the smaller of the two (if it's smaller. Check new children, and swap with the smaller of the two if it's still larger. Continue this until it is larger than its children.

Because we're storing a binary tree in an array, it will compact to the top (so no extra-long branches)

Number of levels for n nodes --> log(n)

Hence, will take max O(logn) time to percolate up or percolate down

Because it takes O(logn) time to place 1 element, it will take O(nlogn) time to place all objects into the binary tree. Once placed, elements are in sorted order

Take first element, place at end of array and percolate up. This will take max O(logn) time

O(nlogn) time to sort all elements

In-place algorithm

Not a stable sort

Chat with Nicholas Neumann-Chun

[liblepre]

Devlog 33 - Sorting

Lately I’ve been a bit busy, but I managed to do some research on sorting.

I wanted to make sure Lepre does not weight on the user with something so basic like sorting. I searched the web for some benchmarks, but I wasn’t lucky.

I’ve found this radix sort implementation http://erik.gorset.no/2011/04/radix-sort-is-faster-than-quicksort.html claiming to be faster than quick sort. So I’ve implemented quicksort, radix sort and insertion sort and I benchmarked them. The results were positive. Luckily Casey Muratori started coding the z sorting too in Handmade Hero, so on the its forums: https://hero.handmadedev.org/forum/code-discussion/1020-day-229-what-about-radix-sort Interestingly faster radix sort that one! Using an auxiliary array improves cache locality and makes radix sort really faster! I implemented that one too and here are the results. (time in ns on the y-axis, number of ordered elements on the x-axis)

Note: below 65336 the algorithms use 16bit unsigned and above they use 32bit ones.

As you can see radix sort without additional memory (radix) is way slower than quick sort iterative (qsi) on the 32bit range. Radix with additional memory (radix_mc) is instead faster than qsi in that range.

But let’s take a look closer in the 16bit range.

Hey, look! Radix is faster than qsi! But still radix_mc is faster. Maybe log scale could help.

So, insertion sort (ins) is actually faster than all of them below a certain threshold. Radix_mc is the faster one, above the ins threshold. So we have a winner!

Note: radix_mc times account for the reordering of the keys, so it is actually faster if you don’t need the keys to be reordered!

A question remains: do the 16bit specialization actually shortens times for radix_mc? For radix it’s clear that it does. Let’s see.

A little bit, above a certain threshold. And yeah, radix has a great benefit from that.

All these data refers to reordering an array of random data, generated with a xorshift128plus. Generally in real life usage you’ll not be adding quads with a random z. What if there are repetitions?

Qsi is the one that benefits more from repetitions. The others are practically the same.

Conclusion

The fastest sorting algorithm for 16bit unsigned values is radix_mc. We can sort 2^16 elements in under a ms. This is pretty good.

It occurs to me that rendering sprites from a 3D world would require to use 32 bit floating point numbers. We could map the z of the sprites in view to the 16bit unsigned domain. It has been done here http://stereopsis.com/radix.html for float32 to u32. So we could use 32 bit values or convert float32 to float16 ( like https://www.mathworks.com/matlabcentral/fileexchange/23173-ieee-754r-half-precision-floating-point-converter )and then to u16. I’ll have to build a test scenario and verify which is the best solution.

[ I’ve taken the qsi from https://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Quicksort#Iterative_Quicksort ]

The last commit: https://bitbucket.org/theGiallo/liblepre/commits/99aee5b563a4e2dbda472df366b488c2a2bb65cd. (there are other new things, but I’m going to split the devlog in two)

* jumps away *

[ictjobs-blog]

New Post has been published on Learning Hub

New Post has been published on http://ictjobs.info/implement-radix-sort/

Implement radix sort in c

#include <cstdio> // printf, puts #include <cstdlib> // srand, rand #include <ctime> // time, clock, time_t #include <cstring> // memset // every programmer should know memset

#define MAX 6000000 // array size #define RANGE 1000000 // range void radix_sort(int *, int); // implementations of this functions you can find in // article describing counting sort void generate(int*, int); void write(int*, int); void quick_sort(int *, int, int); void counting_sort(int *, int, int); int main(int argc, char** argv) { int* T = new int[MAX]; time_t start, end; long dif; srand(time(NULL)); puts("quicksort, O(nlog(n))"); puts("counting sort, O(n)"); // here similar code to below: puts("radix sort, O(n*k):"); generate(T, MAX); start = clock(); radix_sort(T, MAX); end = clock(); dif = end - start; printf("%ld\n", dif / 1000); delete[] T; return 0; } // implementation very similar to counting sort - // isn't it?

// could be whatever function you like, // but in this case we'll try counting sort. // this example assumes, that processor // uses little endian format // int byte - which byte is it void radix(int byte, int size, int *A, int *TEMP) { int* COUNT = new (int[256]); memset(COUNT, 0, 256 * sizeof(int)); // multiplying by 8 to get the right bit shift // in next calculations. // 8 - the count of bits in byte. byte = byte << 3; // right shift // to achieve right byte. // [3rd ] [2nd ] [1st ] [0 byte ] // [++++++++ +++++++++ ++++++++ +++++++++] // most significant is 0-byte. // just counting sort: for (int i = 0; i < size; ++i) ++COUNT[((A[i]) >> (byte)) & 0xFF]; for (int i = 1; i < 256; ++i) COUNT[i] += COUNT[i - 1]; for (int i = size - 1; i >= 0; --i) { TEMP[COUNT[(A[i] >> (byte)) & 0xFF] - 1] = A[i]; --COUNT[(A[i] >> (byte)) & 0xFF]; } delete[] COUNT; } // in this case in radix sort we are sorting // parts of an integer by bytes positions. // assuming that values of A are greater // than 0 void radix_sort(int *A, int size) { int* TEMP = new (int[size]); // in my processor sizeof(int) is 4 for (unsigned int i = 0; i < sizeof(int); i += 2) { // even byte radix(i, size, A, TEMP); // odd byte // reuse of TEMP array radix(i + 1, size, TEMP, A); } delete[] TEMP; }

Output

quicksort, O(nlog(n)) 1890 counting sort, O(n) 1190 radix sort, O(n*k): 880