Sorting algorithms/Radix sort: Difference between revisions
m (moved Radix sort to Sorting algorithms/Radix sort: Group with other sorts) |
m (Merge introductory paragraphs) |
||
Line 1: | Line 1: | ||
{{task|Sorting Algorithms}}{{Sorting Algorithm}} |
{{task|Sorting Algorithms}}{{Sorting Algorithm}} |
||
In this task, the goal is to sort an integer array with the radix sort algorithm. |
In this task, the goal is to sort an integer array with the [[wp:Radix sort|radix sort algorithm]]. The primary purpose is to complete the characterization of sort algorithms task. |
||
For more information see the detailed article on [[wp:Radix_sort|Wikipedia]]. |
|||
=={{header|J}}== |
=={{header|J}}== |
Revision as of 10:21, 19 January 2011
You are encouraged to solve this task according to the task description, using any language you may know.
Sorting Algorithm
This is a sorting algorithm. It may be applied to a set of data in order to sort it.
For comparing various sorts, see compare sorts.
For other sorting algorithms, see sorting algorithms, or:
Heap sort | Merge sort | Patience sort | Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort
In this task, the goal is to sort an integer array with the radix sort algorithm. The primary purpose is to complete the characterization of sort algorithms task.
J
keys f/. data
evaluates the function f on each group of data at the same position as similar keys. Sorting requires ordered keys. This code uses a J idiom: prepend the keys and matching data. The extra data is removed by behead }.
.
<lang j> NB. queue implementation of LSB radix sort. radixSort =: 3 : 0 NB. base radixSort data 16 radixSort y
keys =. x #.^:_1 y NB. compute keys length =. {:#{.keys extra =. (x,-length) {. ,. buckets =. i.x for_pass. 0{i.-length do.
keys =. ,&:>/ (buckets,keys{~"1<pass) <@:}./.extra,keys extra =. 1 |. extra
end. x#.keys NB. restore the data ) </lang>
Sort 10 small numbers in base 3.
(,: 3&radixSort) ?@#~10 1 3 8 9 0 0 8 7 1 6 0 0 1 1 3 6 7 8 8 9
Python
The wikipedia article cited in the introduction includes a python implementation of LSB radix sort.