# Tag Info

15

Radix sorts are often, in practice, the fastest and most useful sorts on parallel machines. Zagha and Blelloch: Radix sort for vector multiprocessors. Supercomputing, 1991: 712-721. Blelloch, Leiserson, Maggs, Plaxton, Smith, and Zagha: A Comparison of Sorting Algorithms for the Connection Machine CM-2. Symp Parallel Algorithms and Arch (SPAA-3):3-16, 1991. ...

15

You can choose $k = 1$ and then the time is $\Theta(32(n+2)) = \Theta(n)$ and the space is $\Theta(2n + 2) = \Theta(n)$. In general, if you replace 32 by any fixed number, the complexities will be $\Theta(n)$. If, however, you try to use radix sort with integers of non-constant width $m$, the complexities will be as stated (with $32$ replaced by $m$), or ...

4

Integers that are equal in some digit aren't always equal (e.g., 12 and 13). Let's sort [13, 12] using a LSD-first radix sort (base 10). But we'll use an unstable sort for each digit. First we sort by the 1's place, so the array becomes [12, 13]. Now we sort by the 10's places, but 12 and 13 have the same digit. Since the sort is unstable, the resulting ...

4

Bitvector approach is correct solution. Problem statement tells that you are given $n$ different integers so there is no need to count multiple occurrence of number in sequence. This also allows you to cut down needed storage to $\lceil{\frac{750}{8}}\rceil = 94$ bytes. Now the algorithm: Input: $A$ - array of unique integers, 1 based Output: None - we ...

4

Radix sort sorts numbers by sorting on the least significant digit first. This is somewhat counterintuitive compared to the rather straightforward method by sorting on the most significant digit first. The key point to radix sort is that the digit sorts used in each iteration of radix sort are stable: numbers (digit here) with the same value appear in the ...

4

This is a textbook application of radix sort. Think of the inputs as 2-digit numbers in base $n$. Using a stable version of counting sort, sort the numbers first according to the least significant digit and then according to the most significant digits. Each pass takes $O(n)$, for a total running time of $O(n)$. The same approach works for numbers up to $n^... 3 I'll analyze some basic strategies, show that always stacking is best in your model, and then discuss a more sophisticated strategy. Analysis of basic strategies: never stack The simplest strategy is one where you never stack boxes: when you pick it up, if it doesn't belong to a cage behind you, you put it back down where it was. Heuristically, I expect ... 3 @Robert: Your link is quite surprising (actually I could not find the quoted sentence). My personal experience is for random input, radix sort is much faster than the STL std::sort(), which uses a variant of quicksort. I used to make an algorithm 50% faster by replacing std::sort() with an unstable radix sort. I am not sure what is the "memory optimized ... 2 The asymptotic runtime ignores access times for the digits. On typical hardware a base 256 number can be manipulated faster than extracting base 10 digits from the same number. If you have multiple CPUs, you can more easily exploit parallel processing by using a larger base. The large base will spread the numbers across many buckets which can then be ... 2 In theory sorting a long sequence of int should be a prime candidate for radix sort as it grows linear in the number of elements to be sorted, while any comparison based sorting algorithm can't be faster than N log N. 2 If I understand OP's question correctly - the question is what is the time-complexity estimate for MSD radix sort, taking into account what OP calls AmountofNodes or recursive frames for an MSD sort, which must fill the count[] array ($R$) per each recursive frame and than iterate through the count[] array to create subfiles. I couldn't find this in the ... 2 Radix sort always uses the results of the previous pass, not the original array. It does not attempt to store the original value of the array. You can find a description of radix sort at Wikipedia or in standard algorithms textbooks, and you'll see that it has this property. As Wikipedia describes, radix sort is stable if you sort the digits starting from ... 2 If you want to implement this on a RAM with integer math (ie. a real computer if your n is smaller than$2^{32}$), you can have a look at Upper bounds for sorting integers on random access machines. The authors show that integers in the range [0,$n^c$] can be sorted in$O(n(1 + \log c))$. Word RAM models add some loglog factors to that runtime. 2 Let me start with a short introduction on computation models. A (C-like) computation model specifies the inventory of operations, and the cost of each operation. Two popular computation models are the bit complexity model and the word RAM model, though the latter doesn't really have a canonical description. In the bit complexity model, all basic operations ... 2 The idea seems wrong at its core. The missing parts are: what is the distribution and range of the data. How many items do you have? (You may not know this in advance, but it renders some algorithms useless). The counting sort works well when the range is compact, it gives good memory requirements and the mere array traversal is not computationally ... 2 A$k$represented this number of digits of maximum value. B k is the number of bits required to represent largest element in the array This translates to number of digits required to represent the max value in binary. A is equivalent to B. Here is how: Say largest element in the array is 1233. According to B,$k = log_2(1233) \approx 11$... 2 Note in the RAM model, indirection always takes constant time regardless of how large the address is, so each process of radix sort with base$b$takes$O(n+b)$time. As a result, the radix sort takes$O((n+b)\log_b(n\log n))=O((n+b)\log_b n)$time. Choosing$b=n$makes the asymptotic time linear. Edit: as suggested by Thinh D. Nguyen, since extracting each ... 1 It would work, the only problem is that it will generate a lot of extra piles for the intermediate results that are difficult to track. if the sorting algorithm sorts the$d$-digit numbers starting from their most significative digit it would create 10 piles at first (one pile for the numbers starting with 0, another one for those starting with 1 and so on) ... 1 Radix sort splits data into own digits of given size, you may choose the base in which data would be treated. If you have 64bit integer you may choose size of radix to be any number, say 2 bits, 4bits, 21bits, 32bits etc., but since computer stores digits as binary numbers it makes more sense to stick with power of two. Also, you would like to omit modulo ... 1 There are exactly 10^9 unique nine digit numbers, so the sorted array is just 0, 1, 2, 3, ..., 999,999,999. 1 Another way to think about$k$is to express the range of numbers in terms of$n$. If you think this way, the usual radix sort algorithm sorts$n$integers in the range$[1,n^c]$in$O(cn)$time using$O(n)$words of extra space. The parameter$c$doesn't enter into the space complexity analysis because it measures the number of radix passes. 1 Here is description of the proposed algorithm. The algorithm is further improvement of the one proposed in Parallel radix sort with virtual memory and write-combining. They implemented fastest parallel LSD radix sort that avoids the counting pass by using "indefinite" space for output buckets. Each bucket allocs space on-demand using hardware paged memory ... 1 Assume, as is often the case, that all elements in the list have width$\Theta(\log n)$. This means that$w = \Theta(\log n)$and so$x = nw = \Theta(n\log n)$. You can check that$n = \Theta(x/\log x)$, and this allows you to convert running times stated as a function of$n$to running times stated as a function of$x$. For example, if the running time of ... 1 In the RAM model of computation, machine words are$\Theta(\log n)$bits long (where$n$is the size of the input in bits), and operations on machine words can be done in$O(1)$. Counting sort has running time$O(N + k)$in the RAM model assuming that each value is$\Theta(\log n)$bits long. Let us now consider an array consisting of$N$values, the ... 1 Use counting sort. In$O(n)$, count the number of elements of each value, and then in$O(m+n)$go over the histogram and translate it to the sorted array. 1 Radix sort for integers of arbitrary length has$\mathcal{O}(mn)$time complexity, where m is the length of number. Count digits takes$\mathcal{O}(\log(n))$time, so, your cycle will take at least (in worst case though)$\mathcal{O}(n \log(n))\$ time which is the best possible for general case of sorting problem. Because to find complexity of 2-level cycle, ...

1

Every problem can be solved with yet another indirection: First create B as an array of self-indexes - i.e set B[i] = i for all i. Next create a 'comparator' object around A, which compares integers i and j by actually comparing A[i] with A[j]. Now sort B using this comparator.

1

There are many ways to do it. The following approach allows to fairly split work between many cores. I believe that it's used even in GPU implementations of radix sort, such as ones provided by Boost.Compute and CUDA Thrust. I describe here one pass of LSD radix sort that distributes data into R buckets: First stage: split input block into K parts, where K ...

1

It turns out that within each round of radix sort, we can take advantage of parallelism. We need to reorder the keys (in a stable manner) according to the relevant bit. The simplest to do this in parallel would be as follows: /* perform one round of radix-sort on the given input * sequence, returning a new sequence reordered according * to the kth bit */ ...

Only top voted, non community-wiki answers of a minimum length are eligible