formulasearchengine - User contributions [en]

Radiosity (computer graphics)

2014-02-02T15:01:43Z

91.157.20.124: /* Limitations */ remove redundant colons for readability

{{Infobox Algorithm
|class=[[Sorting algorithm]]
|image=
|data=[[Array data type|Array]]
|time=<math>O(kN)</math>
|space=<math>O(k + N)</math>
|optimal=exactly correct
}}
In [[computer science]], '''radix sort''' is a non-[[Comparison sort|comparative]] [[integer sorting|integer]] [[sorting algorithm]] that sorts data with integer keys by grouping keys by the individual digits which share the same [[Significant figures|significant]] position and value. A [[positional notation]] is required, but because integers can represent strings of characters (e.g., names or dates) and specially formatted floating point numbers, [[radix]] sort is not limited to integers. Radix sort dates back as far as 1887 to the work of [[Herman Hollerith]] on [[tabulating machines]].<ref>{{Cite patent|US|395781}} and {{Cite patent|UK|327}}</ref>

Most digital computers internally represent all of their data as electronic representations of binary numbers, so processing the digits of integer representations by groups of binary digit representations is most convenient. Two classifications of radix sorts are [[least significant digit]] (LSD) radix sorts and [[most significant digit]] (MSD) radix sorts. LSD radix sorts process the integer representations starting from the least digit and move towards the most significant digit. MSD radix sorts work the other way around.

The integer representations that are processed by sorting algorithms are often called "keys", which can exist all by themselves or be associated with other data.

LSD radix sorts typically use the following sorting order: short keys come before longer keys, and keys of the same length are sorted lexicographically. This coincides with the normal order of integer representations, such as the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.

MSD radix sorts use lexicographic order, which is suitable for sorting strings, such as words, or fixed-length integer representations. A sequence such as "b, c, d, e, f, g, h, i, j, ba" would be lexicographically sorted as "b, ba, c, d, e, f, g, h, i, j". If lexicographic ordering is used to sort variable-length integer representations, then the representations of the numbers from 1 to 10 would be output as 1, 10, 2, 3, 4, 5, 6, 7, 8, 9, as if the shorter keys were left-justified and padded on the right with blank characters to make the shorter keys as long as the longest key for the purpose of determining sorted order.

==Efficiency==

Radix sort efficiency is O(''d''·''n'') for n keys which have ''d'' or fewer digits. Sometimes ''d'' is presented as a constant, which would make radix sort better (for sufficiently large ''n'') than the best comparison-based sorting algorithms, which are all O(''n''·log(''n'')). However, in general ''d'' cannot be considered a constant. In particular, under the common (but sometimes implicit) assumption that all keys are distinct, then ''d'' must be at least of the order of log(''n''), however other sorting methods become O(log (n) * log (n) * n) under similar constraints as they also need to step through an ever increasing number of symbols to do the comparisons.

==Least significant digit radix sorts==

A [[least significant digit]] (LSD) radix sort is a fast [[Stable sort|stable]] [[sorting algorithm]] which can be used to sort keys in integer representation order. Keys may be a [[string (computer science)|string]] of characters, or numerical digits in a given 'radix'. The processing of the keys begins at the [[least significant digit]] (i.e., the rightmost digit), and proceeds to the [[most significant digit]] (i.e., the leftmost digit). The sequence in which digits are processed by a [[least significant digit|LSD]] radix sort is the opposite of the sequence in which digits are processed by a [[most significant digit]] (MSD) radix sort.

An [[least significant digit|LSD]] radix sort operates in [[big O notation|O]](''nk'') time, where ''n'' is the number of keys, and ''k'' is the average key length. This kind of performance for variable-length keys can be achieved by grouping all of the keys that have the same length together and separately performing an LSD radix sort on each group of keys for each length, from shortest to longest, in order to avoid processing the whole list of keys on every sorting pass.

A radix sorting algorithm was originally used to sort [[punched card]]s in several passes. A computer algorithm was invented for radix sort in 1954 at [[Massachusetts Institute of Technology|MIT]] by [[Harold H. Seward]]. In many large applications needing speed, the computer radix sort is an improvement on (slower) comparison sorts.

LSD radix sorts have resurfaced as an alternative to high performance [[comparison sort|comparison-based sorting algorithms]] (like [[heapsort]] and [[mergesort]]) that require O(''n'' · log ''n'') comparisons, where ''n'' is the number of items to be sorted. [[Comparison sort]]s can do no better than O(''n'' · log ''n'') execution time but offer the flexibility of being able to sort with respect to more complicated orderings than a lexicographic one; however, this ability is of little importance in many practical applications.

===Definition===
Each key is first figuratively dropped into one level of buckets corresponding to the value of the rightmost digit. Each bucket preserves the original order of the keys as the keys are dropped into the bucket. There is a one-to-one correspondence between the number of buckets and the number of values that can be represented by the rightmost digit. Then, the process repeats with the next neighbouring more significant digit until there are no more digits to process. In other words:
#Take the least significant digit (or group of bits, both being examples of [[radix|radices]]) of each key.
#Group the keys based on that digit, but otherwise keep the original order of keys. (This is what makes the LSD radix sort a [[stable sort]]).
#Repeat the grouping process with each more significant digit.

The sort in step 2 is usually done using [[bucket sort]] or [[counting sort]], which are efficient in this case since there are usually only a small number of digits.


===An example===

Original, unsorted list:

:170, 45, 75, 90, 802, 2,24, 66

Sorting by least significant digit (1s place) gives:

:170, 90, 802, 2, 24, 45, 75, 66

:Notice that we keep 802 before 2, because 802 occurred before 2 in the original list, and similarly for pairs 170 & 90 and 45 & 75.

Sorting by next digit (10s place) gives:

:802, 2, 24, 45, 66, 170, 75, 90

:Notice that 802 again comes before 2 as 802 comes before 2 in the previous list.

Sorting by most significant digit (100s place) gives:

:2, 24, 45, 66, 75, 90, 170, 802

It is important to realize that each of the above steps requires just a single pass over the data, since each item can be placed in its correct bucket without having to be compared with other items.

Some LSD radix sort implementations allocate space for buckets by first counting the number of keys that belong in each bucket before moving keys into those buckets. The number of times that each digit occurs is stored in an [[Array data type|array]]. Consider the previous list of keys viewed in a different way:

:170, 045, 075, 090, 002, 024, 802, 066

The first counting pass starts on the least significant digit of each key, producing an array of bucket sizes:

:2 (bucket size for digits of 0: 170, 090)
:2 (bucket size for digits of 2: 002, 802)
:1 (bucket size for digits of 4: 024)
:2 (bucket size for digits of 5: 045, 075)
:1 (bucket size for digits of 6: 066)

A second counting pass on the next more significant digit of each key will produce an array of bucket sizes:

:2 (bucket size for digits of 0: 002, 802)
:1 (bucket size for digits of 2: 024)
:1 (bucket size for digits of 4: 045)
:1 (bucket size for digits of 6: 066)
:2 (bucket size for digits of 7: 170, 075)
:1 (bucket size for digits of 9: 090)

A third and final counting pass on the most significant digit of each key will produce an array of bucket sizes:

:6 (bucket size for digits of 0: 002, 024, 045, 066, 075, 090)
:1 (bucket size for digits of 1: 170)
:1 (bucket size for digits of 8: 802)

At least one LSD radix sort implementation now counts the number of times that each digit occurs in each column for all columns in a single counting pass. (See the [[Radix sort#External links|external links]] section.) Other LSD radix sort implementations allocate space for buckets dynamically as the space is needed.

===Iterative version using queues===
A simple version of an LSD radix sort can be achieved using [[Queue (data structure)|queues]] as buckets. The following process is repeated for a number of times equal to the length of the longest key:
#The integers are enqueued into an array of ten separate queues based on their digits from right to left. Computers often represent integers internally as fixed-length binary digits. Here, we will do something analogous with fixed-length decimal digits. So, using the numbers from the previous example, the queues for the 1st pass would be:
#:0: 170, 090
#:1: none
#:2: 002, 802
#:3: none
#:4: 024
#:5: 045, 075
#:6: 066
#:7–9: none
#The queues are dequeued back into an array of integers, in increasing order. Using the same numbers, the array will look like this after the first pass:
#:170, 090, 002, 802, 024, 045, 075, 066
#For the second pass:
#:Queues:
#::0: 002, 802
#::1: none
#::2: 024
#::3: none
#::4: 045
#::5: none
#::6: 066
#::7: 170, 075
#::8: none
#::9: 090
#:Array:
#::002, 802, 024, 045, 066, 170, 075, 090 (note that at this point only 802 and 170 are out of order)
#For the third pass:
#:Queues:
#::0: 002, 024, 045, 066, 075, 090
#::1: 170
#::2–7: none
#::8: 802
#::9: none
#:Array:
#::002, 024, 045, 066, 075, 090, 170, 802 (sorted)
While this may not be the most efficient radix sort algorithm, it is relatively simple, and still quite efficient.
During all tests on 100M or fewer random 64-bit integers, qsort algorithm behaves faster.

===Example in C===
<source lang=c>
#include<stdio.h>
#define MAX 20
#define SHOWPASS
#define BASE 10
void print(int *a, int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d\t", a[i]);
}

void radixsort(int *a, int n)
{
int i, b[MAX], m = a[0], exp = 1;
for (i = 1; i < n; i++)
{
if (a[i] > m)
m = a[i];
}

while (m / exp > 0)
{
int bucket[BASE] ={ 0 };
for (i = 0; i < n; i++)
bucket[(a[i] / exp) % BASE]++;
for (i = 1; i < BASE; i++)
bucket[i] += bucket[i - 1];
for (i = n - 1; i >= 0; i--)
b[--bucket[(a[i] / exp) % BASE]] = a[i];
for (i = 0; i < n; i++)
a[i] = b[i];
exp *= BASE;

#ifdef SHOWPASS
printf("\nPASS : ");
print(a, n);
#endif
}
}

int main()
{
int arr[MAX];
int i, n;
printf("Enter total elements (n <= %d) : ", MAX);
scanf("%d", &n);
n = n < MAX ? n : MAX;

printf("Enter %d Elements : ", n);
for (i = 0; i < n; i++)
scanf("%d", &arr[i]);

printf("\nARRAY : ");
print(&arr[0], n);

radixsort(&arr[0], n);

printf("\nSORTED : ");
print(&arr[0], n);
printf("\n");

return 0;
}
</source>

===Example in Python===
This example written in the Python programming language will perform the radix sort for any radix (base) of 2 or greater. Simplicity of exposition is chosen over clever programming, and so the ''log'' function is used instead of bit shifting techniques.
<source lang=python>
#python2.6 <
from math import log

def getDigit(num, base, digit_num):
# pulls the selected digit
return (num // base ** digit_num) % base

def makeBlanks(size):
# create a list of empty lists to hold the split by digit
return [[] for _ in xrange(size)]

def split(a_list, base, digit_num):
buckets = makeBlanks(base)
for num in a_list:
# append the number to the list selected by the digit
buckets[getDigit(num, base, digit_num)].append(num)
return buckets

# concatenate the lists back in order for the next step
def merge(a_list):
new_list = []
for sublist in a_list:
new_list.extend(sublist)
return new_list

def maxAbs(a_list):
# largest abs value element of a list
return max(abs(num) for num in a_list)

def radixSort(a_list, base):
# there are as many passes as there are digits in the longest number
passes = int(round(log(maxAbs(a_list), base)) + 1)
new_list = a_list[:]
for digit_num in range(passes):
new_list = merge(split(new_list, base, digit_num))
return new_list
</source>

==Most significant digit radix sorts==
A [[most significant digit]] (MSD) radix sort can be used to sort keys in [[lexicographic order]]. Unlike a least significant digit (LSD) radix sort, a most significant digit radix sort [[Stable sort|does not necessarily preserve the original order of duplicate keys]]. An MSD radix sort starts processing the keys from the [[most significant digit]], leftmost digit, to the [[least significant digit]], rightmost digit. This sequence is opposite that of [[least significant digit]] (LSD) radix sorts. An MSD radix sort stops rearranging the position of a key when the processing reaches a unique prefix of the key. Some MSD radix sorts use one level of buckets in which to group the keys. See the [[counting sort]] and [[pigeonhole sort]] articles. Other MSD radix sorts use multiple levels of buckets, which form a [[trie]] or a path in a trie. A [[Bucket sort#Postman's sort|postman's sort / postal sort]] is a kind of MSD radix sort.

===Recursion===
A [[recursion|recursively]] subdividing MSD radix sort algorithm works as follows:
#Take the most significant digit of each key.
#Sort the list of elements based on that digit, grouping elements with the same digit into one [[bucket (computing)|bucket]].
#Recursively sort each bucket, starting with the next digit to the right.
#[[Concatenate]] the buckets together in order.

====Implementation====
A two-pass method can be used to first find out how big each bucket needs to be and then place each key (or pointer to the key) into the appropriate bucket. A single-pass system can also be used, where each bucket is dynamically allocated and resized as needed, but this runs the risk of serious memory fragmentation, discontiguous allocations of memory, which may degrade performance. This memory fragmentation could be avoided if a fixed allocation of buckets is used for all possible values of a digit, but, for an 8-bit digit, this would require 256 (28) buckets, even if not all of the buckets were used. So, this approach might use up all available memory quickly and go into paging space, where data is stored and accessed on a hard drive or some other secondary memory device instead of main memory, which would radically degrade performance. A fixed allocation approach would only make sense if each digit was very small, such as a single bit.

===Recursive forward radix sort example===
Sort the list:
 170, 045, 075, 090, 002, 024, 802, 066
#Sorting by most significant digit (100s place) gives: Zero hundreds bucket: 045, 075, 090, 002, 024, 066 One hundreds bucket: 170 Eight hundreds bucket: 802
#Sorting by next digit (10s place) is only needed for those numbers in the zero hundreds bucket (no other buckets contain more than one item): Zero tens bucket: 002 Twenties bucket: 024 Forties bucket: 045 Sixties bucket: 066 Seventies bucket: 075 Nineties bucket: 090
Sorting by least significant digit (1s place) is not needed, as there is no tens bucket with more than one number. Therefore, the now sorted zero hundreds bucket is concatenated, joined in sequence, with the one hundreds bucket and eight hundreds bucket to give: 002, 024, 045, 066, 075, 090, 170, 802

This example used [[base (exponentiation)|base]] ten digits for the sake of readability, but of course binary digits or perhaps [[byte]]s might make more sense for a binary computer to process.

===In-place MSD radix sort implementations===
Binary MSD radix sort, also called binary quicksort, can be implemented in-place by splitting the input array into two bins - the 0s bin and the 1's bin. The 0s bin is grown from the beginning of the array, whereas the 1's bin is grown from the end of the array. The 0s bin boundary is placed before the first array element. The 1's bin boundary is placed after the last array element. The most significant bit of the first array element is examined. If this bit is a 1, then the first element is swapped with the element in front of the 1's bin boundary (the last element of the array), and the 1's bin is grown by one element by decrementing the 1's boundary array index. If this bit is a 0, then the first element remains at its current location, and the 0s bin is grown by one element. The next array element examined is the one in front of the 0s bin boundary (i.e. the first element that is not in the 0s bin or the 1's bin). This process continues until the 0s bin and the 1's bin reach each other. The 0s bin and the 1's bin are then sorted recursively based on the next bit of each array element. Recursive processing continues until the least significant bit has been used for sorting.<ref>R. Sedgewick, "Algorithms in C++", third edition, 1998, p. 424-427</ref><ref>[http://www.drdobbs.com/architecture-and-design/220300654 V. J. Duvanenko, "In-Place Hybrid Binary-Radix Sort", Dr. Dobb's Journal, 1 October 2009]</ref> Handling signed integers requires treating the most significant bit with the opposite sense, followed by unsigned treatment of the rest of the bits.

In-place MSD binary-radix sort can be extended to larger radix and retain in-place capability. [[Counting sort]] is used to determine the size of each bin and their starting index. Swapping is used to place the current element into its bin, followed by expanding the bin boundary. As the array elements are scanned the bins are skipped over and only elements between bins are processed, until the entire array has been processed and all elements end up in their respective bins. The number of bins is the same as the radix used - e.g. 16 bins for 16-Radix. Each pass is based on a single digit (e.g. 4-bits per digit in the case of 16-Radix), starting from the [[most significant digit]]. Each bin is then processed recursively using the next digit, until all digits have been used for sorting.<ref>[http://www.drdobbs.com/architecture-and-design/221600153 V. J. Duvanenko, "In-Place Hybrid N-bit-Radix Sort", Dr. Dobb's Journal, November 2009]</ref><ref>[http://www.drdobbs.com/high-performance-computing/229000734 V. J. Duvanenko, "Parallel In-Place Radix Sort Simplified", Dr. Dobb's Journal, January 2011]</ref>

Neither in-place binary-radix sort nor n-bit-radix sort, discussed in paragraphs above, are [[Sorting algorithm|stable algorithms]].

===Stable MSD radix sort implementations===
MSD Radix Sort can be implemented as a stable algorithm, but requires the use of a memory buffer of the same size as the input array. This extra memory allows the input buffer to be scanned from the first array element to last, and move the array elements to the destination bins in the same order. Thus, equal elements will be placed in the memory buffer in the same order they were in the input array. The MSD-based algorithm uses the extra memory buffer as the output on the first level of recursion, but swaps the input and output on the next level of recursion, to avoid the overhead of copying the output result back to the input buffer. Each of the bins are recursively processed, as is done for the in-place MSD Radix Sort. After the sort by the last digit has been completed, the output buffer is checked to see if it is the original input array, and if it's not, then a single copy is performed. If the digit size is chosen such that the key size divided by the digit size is an even number, the copy at the end is avoided.<ref>[http://www.drdobbs.com/tools/222200161 V. J. Duvanenko, "Stable Hybrid N-bit-Radix Sort", Dr. Dobb's Journal, January 2010]</ref>

===Hybrid approaches===
Radix sort, such as two pass method where [[counting sort]] is used during the first pass of each level of recursion, has a large constant overhead. Thus, when the bins get small, other sorting algorithms should be used, such as [[insertion sort]]. A good implementation of [[Insertion sort]] is fast for small arrays, stable, in-place, and can significantly speed up Radix Sort.

===Application to parallel computing===
Note that this recursive sorting algorithm has particular application to [[parallel computing]], as each of the bins can be sorted independently. In this case, each bin is passed to the next available processor. A single processor would be used at the start (the most significant digit). By the second or third digit, all available processors would likely be engaged. Ideally, as each subdivision is fully sorted, fewer and fewer processors would be utilized. In the worst case, all of the keys will be identical or nearly identical to each other, with the result that there will be little to no advantage to using parallel computing to sort the keys.

In the top level of recursion, opportunity for parallelism is in the [[Counting sort]] portion of the algorithm. Counting is highly parallel, amenable to the parallel_reduce pattern, and splits the work well across multiple cores until reaching memory bandwidth limit. This portion of the algorithm has data-independent parallelism. Processing each bin in subsequent recursion levels is data-dependent, however. For example, if all keys were of the same value, then there would be only a single bin with any elements in it, and no parallelism would be available. For random inputs all bins would be near equally populated and a large amount of parallelism opportunity would be available.<ref>[http://www.drdobbs.com/high-performance-computing/226600004 V. J. Duvanenko, "Parallel In-Place N-bit-Radix Sort", Dr. Dobb's Journal, August 2010]</ref>

Note that there are faster sorting algorithms available, for example optimal complexity O(log(''n'')) are those of the Three Hungarians and Richard Cole<ref>A. Gibbons and [[Wojciech Rytter|W. Rytter]], "Efficient Parallel Algorithms". Cambridge University Press, 1988.</ref><ref>H. Casanova et al, "Parallel Algorithms". Chapman & Hall, 2008.</ref> and [[Batcher]]'s bitonic merge sort has an algorithmic complexity of O(log2(''n'')), all of which have a lower algorithmic time complexity to radix sort on a CREW-[[Parallel Random Access Machine|PRAM]]. The fastest known [[Parallel Random Access Machine|PRAM]] sorts were described in 1991 by David Powers with a parallelized quicksort that can operate in O(log(n)) time on a CRCW-[[Parallel Random Access Machine|PRAM]] with ''n'' processors by performing partitioning implicitly, as well as a radixsort that operates using the same trick in O(''k''), where ''k'' is the maximum keylength.<ref>David M. W. Powers, [http://citeseer.ist.psu.edu/327487.html Parallelized Quicksort and Radixsort with Optimal Speedup], ''Proceedings of International Conference on Parallel Computing Technologies''. [[Novosibirsk]]. 1991.</ref> However, neither the [[Parallel Random Access Machine|PRAM]] architecture or a single sequential processor can actually be built in a way that will scale without the number of constant [[fanout]] gate delays per cycle increasing as O(log(''n'')), so that in effect a pipelined version of Batcher's bitonic mergesort and the O(log(''n'')) [[Parallel Random Access Machine|PRAM]] sorts are all O(log2(''n'')) in terms of clock cycles, with Powers acknowledging that Batcher's would have lower constant in terms of gate delays than his Parallel [[quicksort]] and radix sort, or Cole's [[merge sort]], for a keylength-independent [[sorting network]] of O(nlog2(''n'')).<ref>David M. W. Powers, [http://david.wardpowers.info/Research/AI/papers/199501-ACAW-PUPC.pdf Parallel Unification: Practical Complexity], Australasian Computer Architecture Workshop, Flinders University, January 1995</ref>

===Incremental trie-based radix sort===
Another way to proceed with an MSD radix sort is to use more memory to create a [[trie]] to represent the keys and then traverse the trie to visit each key in order. A [[depth-first search|depth-first traversal]] of a trie starting from the [[root node]] will visit each key in order. A depth-first traversal of a trie, or any other kind of [[Directed acyclic graph|acyclic]] tree structure, is equivalent to traversing a maze via the [[Maze solving algorithm#Wall follower|right-hand rule]].

A trie essentially represents a [[set (mathematics)|set]] of strings or numbers, and a radix sort which uses a trie structure is not necessarily stable, which means that the original order of duplicate keys is not necessarily preserved, because a set does not contain duplicate elements. Additional information will have to be associated with each key to indicate the population count or original order of any duplicate keys in a trie-based radix sort if keeping track of that information is important for a particular application. It may even be desirable to discard any duplicate strings as the trie creation proceeds if the goal is to find only unique strings in sorted order. Some people sort a list of strings first and then make a separate pass through the sorted list to discard duplicate strings, which can be slower than using a trie to simultaneously sort and discard duplicate strings in one pass.

One of the advantages of maintaining the trie structure is that the trie makes it possible to determine quickly if a particular key is a member of the set of keys in a time that is proportional to the length of the key, ''k'', in O(''k'') time, that is ''independent'' of the total number of keys. Determining set membership in a plain list, as opposed to determining set membership in a trie, requires [[binary search]], O(''k log(n)'') time; [[linear search]], O(''kn'') time; or some other method whose execution time is in some way dependent on the total number, ''n'', of all of the keys in the worst case. It is sometimes possible to determine set membership in a plain list in O(''k'') time, in a time that is independent of the total number of keys, such as when the list is known to be in an [[arithmetic sequence]] or some other computable sequence.

Maintaining the trie structure also makes it possible to insert new keys into the set incrementally or delete keys from the set incrementally while maintaining sorted order in O(''k'') time, in a time that is independent of the total number of keys. In contrast, other radix sorting algorithms must, in the worst case, re-sort the entire list of keys each time that a new key is added or deleted from an existing list, requiring O(''kn'') time.

====Snow White analogy====
[[File:7dwarves.svg|center]]
If the nodes were rooms connected by hallways, then here is how Snow White might proceed to visit all of the dwarfs if the place were dark, keeping her right hand on a wall at all times:
# She travels down hall B to find Bashful.
# She continues moving forward with her right hand on the wall, which takes her around the room and back up hall B.
# She moves down halls D, O, and C to find Doc.
# Continuing to follow the wall with her right hand, she goes back up hall C, then down hall P, where she finds Dopey.
# She continues back up halls P, O, D, and then goes down hall G to find Grumpy.
# She goes back up hall G, with her right hand still on the wall, and goes down hall H to the room where Happy is.
# She travels back up hall H and turns right down halls S and L, where she finds Sleepy.
# She goes back up hall L, down hall N, where she finally finds Sneezy.
# She travels back up halls N and S to her starting point and knows that she is done.

These series of steps serve to illustrate the path taken in the trie by Snow White via a [[depth-first search|depth-first traversal]] to visit the dwarfs by the ascending order of their names, Bashful, Doc, Dopey, Grumpy, Happy, Sleepy, and Sneezy. The algorithm for performing some operation on the data associated with each node of a tree first, such as printing the data, and then moving deeper into the tree is called a [[pre-order traversal]], which is a kind of [[depth-first search|depth-first traversal]]. A pre-order traversal is used to process the contents of a trie in ascending order. If Snow White wanted to visit the dwarfs by the descending order of their names, then she could walk backwards while following the wall with her right hand, or, alternatively, walk forward while following the wall with her left hand. The algorithm for moving deeper into a tree first until no further descent to unvisited nodes is possible and then performing some operation on the data associated with each node is called [[post-order traversal]], which is another kind of depth-first traversal. A [[post-order traversal]] is used to process the contents of a trie in descending order.

The [[root node]] of the [[trie]] in the diagram essentially represents a null string, an empty string, which can be useful for keeping track of the number of blank lines in a list of words. The null string can be associated with a circularly [[linked list]] with the null string initially as its only member, with the forward and backward pointers both initially pointing to the null string. The circularly linked list can then be expanded as each new key is inserted into the [[trie]]. The circularly linked list is represented in the following diagram as thick, grey, horizontally linked lines:

[[File:7dwarvesThreaded.svg|center]]
If a new key, other than the null string, is inserted into a [[leaf node]] of the [[trie]], then the computer can go to the last preceding node where there was a key or a bifurcation to perform a [[depth-first search]] to find the lexicographic successor or predecessor of the inserted key for the purpose of splicing the new key into the circularly [[linked list]]. The last preceding node where there was a key or a bifurcation, a fork in the path, is a [[parent node]] in the type of trie shown here, where only unique string prefixes are represented as paths in the trie. If there is already a key associated with the parent node that would have been visited during a movement ''away'' from the root during a right-hand, forward-moving, depth-first traversal, then that immediately ends the depth-first search, as that key is the predecessor of the inserted key. For example, if Bashful is inserted into the trie, then the predecessor is the null string in the parent node, which is the [[root node]] in this case. In other words, if the key that is being inserted is on the leftmost branch of the parent node, then any string contained in the parent node is the lexicographic predecessor of the key that is being inserted, else the lexicographic predecessor of the key that is being inserted exists down the parent node's branch that is immediately to the left of the branch where the new key is being inserted. For example, if Grumpy were the last key inserted into the trie, then the computer would have a choice of trying to find either the predecessor, Dopey, or the successor, Happy, with a [[depth-first search]] starting from the parent node of Grumpy. With no additional information to indicate which path is longer, the computer might traverse the longer path, D, O, P. If Dopey were the last key inserted into the trie, then the depth-first search starting from the parent node of Dopey would soon find the predecessor, "Doc", because that would be the only choice.

If a new key is inserted into an [[internal node]], then a depth-first search can be started from the [[internal node]] to find the lexicographic successor. For example, if the literal string "DO" were inserted in the node at the end of the path D, O, then a depth-first search could be started from that internal node to find the successor, "DOC", for the purpose of splicing the new string into the circularly [[linked list]].

Forming the circularly linked list requires more memory but allows the keys to be visited more directly in either ascending or descending order via a linear traversal of the [[linked list]] rather than a [[depth-first search|depth-first traversal]] of the entire trie. This concept of a circularly linked trie structure is similar to the concept of a [[threaded binary tree]]. This structure will be called a circularly threaded trie.

[[File:Trie002.svg|center]]

When a [[trie]] is used to sort numbers, the number representations must all be the same length unless you are willing to perform a [[breadth-first search|breadth-first traversal]]. When the number representations will be visited via [[depth-first search|depth-first traversal]], as in the above diagram, the number representations will always be on the [[leaf node]]s of the [[trie]]. Note how similar in concept this particular example of a trie is to the [[radix sort#Recursive forward radix sort example|recursive forward radix sort example]] which involves the use of buckets instead of a trie. Performing a radix sort with the buckets is like creating a trie and then discarding the non-leaf nodes.

==See also==
* [[IBM 80 series Card Sorters]]
* [[Spaghetti sort]]

==References==
{{reflist}}

==External links==
{{wikibooks|Algorithm implementation|Sorting/Radix_sort|Radix sort}}
*[http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Radix/ Demonstration and comparison] of Radix sort with [[Bubble sort]], [[Merge sort]] and [[Quicksort]] implemented in [[JavaScript]]
*[http://www.codercorner.com/RadixSortRevisited.htm Article] about Radix sorting [[IEEE floating-point standard|IEEE floating-point]] numbers with implementation.
*:[http://www.stereopsis.com/radix.html Faster Floating Point Sorting and Multiple Histogramming] with implementation in C++
*Pointers to [http://web-cat.cs.vt.edu/AlgovizWiki/RadixSort radix sort visualizations]
*[http://bitbucket.org/ais/usort/wiki/Home USort library] contains tuned implementations of radix sort for most numerical C types (C99)

* [[Donald Knuth]]. ''The Art of Computer Programming'', Volume 3: ''Sorting and Searching'', Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 5.2.5: Sorting by Distribution, pp. 168–179.
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 8.3: Radix sort, pp. 170–173.
* [http://web.archive.org/web/20010714213118/www.chinet.com/~edlee/bradsort.c BRADSORT v1.50 source code]
* [http://goanna.cs.rmit.edu.au/~jz/fulltext/acsc03sz.pdf Efficient Trie-Based Sorting of Large Sets of Strings], by Ranjan Sinha and Justin Zobel. This paper describes a method of creating tries of buckets which figuratively burst into sub-tries when the buckets hold more than a predetermined capacity of strings, hence the name, "Burstsort".
* [http://opendatastructures.org/versions/edition-0.1e/ods-java/11_2_Counting_Sort_Radix_So.html Open Data Structures - Java Edition - Section 11.2 - Counting Sort and Radix Sort]
* [http://opendatastructures.org/ods-cpp/11_2_Counting_Sort_Radix_So.html Open Data Structures - C++ Edition - Section 11.2 - Counting Sort and Radix Sort]

{{Use dmy dates|date=January 2012}}
{{sorting}}

{{DEFAULTSORT:Radix Sort}}
[[Category:Sorting algorithms]]
[[Category:Stable sorts]]

[[no:Sorteringsalgoritme#Radix-sortering]]

Steradian

2013-12-29T10:47:08Z

91.157.210.180: Clarified the caption of the small cone section: A = r2 in the picture is correct only if the solid angle is one steradian.

In [[mathematics]], a '''symplectic manifold''' is a [[smooth manifold]], ''M'', equipped with a [[Closed and exact differential forms|closed]] [[nondegenerate form|nondegenerate]] differential [[two-form|2-form]], ω, called the [[symplectic form]]. The study of symplectic manifolds is called [[symplectic geometry]] or [[symplectic topology]]. Symplectic manifolds arise naturally in abstract formulations of [[classical mechanics]] and [[analytical mechanics]] as the [[cotangent bundle]]s of manifolds, e.g., in the [[Hamiltonian mechanics|Hamiltonian formulation]] of classical mechanics, which provides one of the major motivations for the field: The set of all possible configurations of a system is modelled as a manifold, and this manifold's [[cotangent bundle]] describes the [[phase space]] of the system.

Any real-valued [[differentiable function]], ''H'', on a symplectic manifold can serve as an '''[[energy function]]''' or '''Hamiltonian'''. Associated to any Hamiltonian is a [[Hamiltonian vector field]]; the [[integral curve]]s of the Hamiltonian vector field are solutions to [[Hamilton's equations]]. The Hamiltonian vector field defines a flow on the symplectic manifold, called a '''Hamiltonian flow''' or [[symplectomorphism]]. By [[Liouville's theorem (Hamiltonian)|Liouville's theorem]], Hamiltonian flows preserve the [[volume form]] on the phase space.

== Motivation ==

Symplectic manifolds arise from [[classical mechanics]], in particular, they are a generalization of the [[phase space]] of a closed system.<ref name="Webster">Ben Webster: ''What is a symplectic manifold, really?'' http://sbseminar.wordpress.com/2012/01/09/what-is-a-symplectic-manifold-really/</ref> In the same way the [[Hamilton equations]] allow one to derive the time evolution of a system from a set of [[differential equation]]s, the symplectic form should allow one to obtain a [[vector field]] describing the flow of the system from the differential ''dH'' of a Hamiltonian function ''H''. As [[Newton's laws of motion]] are linear differential equations, such a map should be linear as well.<ref name="Cohn">Henry Cohn: ''Why symplectic geometry is the natural setting for classical mechanics'' http://research.microsoft.com/en-us/um/people/cohn/thoughts/symplectic.html</ref> So we require a linear map ''T* M → TM'', or equivalently, an element of ''T* M'' ⊗ ''T* M''. Letting ω denote a [[Section (fiber bundle)|section]] of ''T* M'' ⊗ ''T* M'', the requirement that ω be [[Degenerate form|non-degenerate]] ensures that for every differential ''dH'' there is a unique corresponding vector field ''VH'' such that ''dH = ω(VH,· )''. Since one desires the Hamiltonian to be constant along flow lines, one should have ''dH(VH) = ω(VH, VH) = 0'', which implies that ''ω'' is [[Alternating form|alternating]] and hence a 2-form. Finally, one makes the requirement that ''ω'' should not change under flow lines, i.e. that the [[Lie derivative]] of ''ω'' along ''VH'' vanishes. Applying [[Cartan's formula]], this amounts to

:<math>\mathcal{L}_{V_H}(\omega) = d\omega(V_H) = 0</math>

which is equivalent to the requirement that ''ω'' should be [[Closed and exact differential forms|closed]].

== Definition ==

A symplectic form on a manifold ''M'' is a closed non-degenerate differential [[two-form|2-form]] ''ω''.<ref name="Gosson">Maurice de Gosson: ''Symplectic Geometry and Quantum Mechanics'' (2006) Birkhäuser Verlag, Basel ISBN 3-7643-7574-4. (page 10)
</ref><ref name="Arnold">{{Cite book|first=V. I.|last=Arnold|first2=A. N.|last2=Varchenko|first3=S. M.|last3=Gusein-Zade|title=The Classification of Critical Points, Caustics and Wave Fronts: Singularities of Differentiable Maps, Vol 1|publisher=Birkhäuser|year=1985|isbn=0-8176-3187-9|postscript=}}</ref>
Here, non-degenerate means that for all {{nowrap|1=''p'' ∈ ''M''}}, if there exists an {{nowrap|1=''X'' ∈ ''TpM''}} such that {{nowrap|1=''ω''(''X'',''Y'') = 0}} for all {{nowrap|1=''Y'' ∈ ''TpM''}}, then {{nowrap|1=''X'' = 0}}. The [[skew-symmetric]] condition (inherent in the definition of differential 2-form) means that for all {{nowrap|1=''p'' ∈ ''M''}} we have {{nowrap|1=''ω''(''X'',''Y'') = −''ω''(''Y'',''X'')}} for all {{nowrap|1=''X'',''Y'' ∈ ''TpM''.}} In odd dimensions, [[antisymmetric]] matrices are not invertible. Since ''ω'' is a differential two-form, the skew-symmetric condition implies that ''M'' has even dimension.<ref name="Gosson"/><ref name="Arnold"/> The closed condition means that the [[exterior derivative]] of ''ω ''vanishes, d''ω ''= 0. A symplectic manifold consists of a pair (''M'',''ω''), of a manifold ''M'' and a symplectic form ''ω''. Assigning a symplectic form ''ω'' to a manifold ''M'' is referred to as giving ''M'' a '''symplectic structure'''.

== Linear symplectic manifold ==

There is a standard linear model, namely a [[symplectic vector space]] '''R'''2''n''. Let '''R'''2''n'' have the basis {''v''1, ..., ''v''2''n''}. Then we define our symplectic form ''ω'' so that for all {{nowrap|1=1 ≤ ''i'' ≤ ''n''}} we have {{nowrap|1=''ω''(''v''''i'',''v''''n''+''i'') = 1,}} {{nowrap|1=''ω''(''v''''n''+''i'',''v''''i'') = −1,}} and ''ω'' is zero for all other pairs of basis vectors. In this case the symplectic form reduces to a simple [[quadratic form]]. If ''In'' denotes the {{nowrap|1=''n'' × ''n''}} [[identity matrix]] then the matrix, ''Ω'', of this quadratic form is given by the ({{nowrap|1=2''n'' × 2''n''}}) [[block matrix]]:

:<math> \Omega = \left(\begin{array}{c|c} 0 & I_n \\ \hline -I_n & 0 \end{array}\right). </math>

== Lagrangian and other submanifolds ==

There are several natural geometric notions of [[submanifold]] of a symplectic manifold.
*'''symplectic submanifolds''' (potentially of any even dimension) are submanifolds where the symplectic form is required to induce a symplectic form on them.
*'''isotropic submanifolds''' are submanifolds where the symplectic form restricts to zero, i.e. each tangent space is an isotropic subspace of the ambient manifold's tangent space. Similarly, if each tangent subspace to a submanifold is co-isotropic (the dual of an isotropic subspace), the submanifold is called '''co-isotropic'''.

The most important case of the isotropic submanifolds is that of '''Lagrangian submanifolds'''. A Lagrangian submanifold is, by definition, an isotropic submanifold of maximal dimension, namely half the dimension of the ambient symplectic manifold. One major example is that the graph of a [[symplectomorphism]] in the product symplectic manifold {{nowrap|1=(''M'' × ''M'', ω × −ω)}} is Lagrangian. Their intersections display rigidity properties not possessed by smooth manifolds; the [[Arnold conjecture]] gives the sum of the submanifold's [[Betti number]]s as a lower bound for the number of self intersections of a smooth Lagrangian submanifold, rather than the [[Euler characteristic]] in the smooth case.

== Lagrangian fibration ==

A '''Lagrangian fibration''' of a symplectic manifold ''M'' is a [[fibration]] where all of the [[Fiber_bundle#Formal_definition|fibres]] are Lagrangian submanifolds. Since ''M'' is even dimensional we can take local coordinates {{nowrap|1=(''p''1,…,''p''''n'',''q''1,…,''q''''n''),}} and by [[Darboux's theorem]] the symplectic form ''ω'' can be, at least locally, written as {{nowrap|1=''ω'' = ∑ d''p''''k'' &and; d''q''''k''}}, where d denotes the [[exterior derivative]] and ∧ denotes the [[exterior product]]. Using this set-up we can locally think of ''M'' as being the [[cotangent bundle]] T*'''R'''''n'', and the Lagrangian fibration as the trivial fibration {{nowrap|1=''π'' : T*'''R'''''n'' ↠ '''R'''''n''.}} This is the canonical picture.

== Lagrangian mapping ==
[[Image:TIKZ PICT FBN.png|thumb|<center>[[:File:TIKZ PICT FBN.png|Click to Enlarge]]</center>]]
Let ''L'' be a Lagrangian submanifold of a symplectic manifold (''K'',ω) given by an [[Immersion (mathematics)|immersion]] {{nowrap|1=''i'' : ''L'' ↪ ''K''}} (''i'' is called a '''Lagrangian immersion'''). Let {{nowrap|1=''π'' : ''K'' ↠ ''B''}} give a Lagrangian fibration of ''K''. The composite {{nowrap|1=(''π'' ○ ''i'') : ''L'' ↪ ''K'' ↠ ''B''}} is a '''Lagrangian mapping'''. The [[critical value|critical value set]] of ''π'' ○ ''i'' is called a [[Caustic (mathematics)|caustic]].

Two Lagrangian maps {{nowrap|1=(''π''1 ○ ''i''1) : ''L''1 ↪ ''K''1 ↠ ''B''1}} and {{nowrap|1=(''π''2 ○ ''i''2) : ''L''2 ↪ ''K''2 ↠ ''B''2}} are called '''Lagrangian equivalent''' if there exist [[diffeomorphism]]s σ, τ and ν such that both sides of the diagram given on the right [[commutative diagram|commute]], and τ preserves the symplectic form.<ref name="Arnold"/> Symbolically:
:<math> \tau \circ i_1 = i_2 \circ \sigma, \ \nu \circ \pi_1 = \pi_2 \circ \tau, \ \tau^*\omega_2 = \omega_1 \, , </math>
where τ*ω2 denotes the [[Pullback_(differential_geometry)#Pullback_of_differential_forms|pull back]] of ω2 by τ.

== Special cases and generalizations ==
* A symplectic manifold endowed with a [[metric tensor|metric]] that is [[Almost complex manifold#Compatible triples|compatible]] with the symplectic form is an [[almost Kähler manifold]] in the sense that the tangent bundle has an [[almost complex structure]], but this need not be [[integrability condition|integrable]].

* Symplectic manifolds are special cases of a [[Poisson manifold]]. The definition of a symplectic manifold requires that the symplectic form be non-degenerate everywhere, but if this condition is violated, the manifold may still be a Poisson manifold.

* A '''multisymplectic manifold''' of degree ''k'' is a manifold equipped with a closed nondegenerate ''k''-form.<ref>F. Cantrijn, L. A. Ibort and M. de León, J. Austral. Math. Soc. Ser. A 66 (1999), no. 3, 303-330.</ref>

* A '''polysymplectic manifold''' is a Legendre bundle provided with a polysymplectic tangent-valued <math>(n+2)</math>-form; it is utilized in Hamiltonian field theory.<ref>G. Giachetta, L. Mangiarotti and [[Sardanashvily|G. Sardanashvily]], Covariant Hamiltonian equations for field theory, Journal of Physics '''A32''' (1999) 6629-6642; [http://xxx.lanl.gov/abs/hep-th/9904062 arXiv: hep-th/9904062].</ref>

== See also ==
{{Portal|Mathematics}}
<div style="-moz-column-count:3; column-count:3;">
* [[Almost complex manifold]]
* [[Almost symplectic manifold]]
* [[Contact manifold]] − an odd-dimensional counterpart of the symplectic manifold.
* [[Fedosov manifold]]
* [[Poisson bracket]]
* [[Symplectic group]]
* [[Symplectic matrix]]
* [[Symplectic topology]]
* [[Symplectic vector space]]
* [[Symplectomorphism]]
* [[Tautological one-form]]
* [[Wirtinger inequality (2-forms)]]
* [[Covariant Hamiltonian field theory]]
</div>

==Notes==
{{Reflist}}

==References==
* [[Dusa McDuff]] and D. Salamon: ''Introduction to Symplectic Topology'' (1998) Oxford Mathematical Monographs, ISBN 0-19-850451-9.
* [[Ralph Abraham]] and [[Jerrold E. Marsden]], ''Foundations of Mechanics'', (1978) Benjamin-Cummings, London ISBN 0-8053-0102-X ''See section 3.2''.
* [[Maurice A. de Gosson]]: ''Symplectic Geometry and Quantum Mechanics'' (2006) Birkhäuser Verlag, Basel ISBN 3-7643-7574-4.
* {{cite journal |author=Alan Weinstein |title=Symplectic manifolds and their lagrangian submanifolds |authorlink=Alan Weinstein |journal=Adv Math |volume=6 |issue=3 |year=1971 |pages=329–46 |doi=10.1016/0001-8708(71)90020-X }}

== External links ==
* {{Springer|author=Ü. Lumiste|title=Symplectic Structure|id=s/s091860}}
* [[Gennadi Sardanashvily|Sardanashvily, G.]], Fibre bundles, jet manifolds and Lagrangian theory. Lectures for theoreticians,[http://xxx.lanl.gov/abs/0908.1886 arXiv: 0908.1886]
* {{planetmath reference|id=3672|title=Examples of symplectic manifolds}}

{{DEFAULTSORT:Symplectic Manifold}}
[[Category:Differential topology]]
[[Category:Symplectic geometry]]
[[Category:Hamiltonian mechanics]]
[[Category:Smooth manifolds]]

Õ

2012-08-07T16:11:20Z

91.157.13.121: Noted Saaremaa dialect

If your weight loss program is not giving we the right results, then we are reading the right article. We maybe making big strenuous efforts in purchase to get rid of weight however they may not be having a terrific impact. So now it is very the time to concentrate on little factors that go a long method in purchase to achieve efficient weight reduction. The simple strategies reported below are the tips which may function wonders for you plus they are truly easy to follow. Food is the gas of the body plus you should understand which though fasting is included inside the long list of methods to lose weight it's at the end of the day a especially unhealthy practice. Instead of getting oily and spiced up food stuffs you will want to start the consumption of cereals and foods that have a high fiber and grain content. One of the better ways to lose weight fast is the intake of 2 servings of fruit and 5 servings of veggies a day. The best foods for weight loss are fresh all-natural food, nutritionally thick, significant inside fiber, low in fat and calories, low in sodium and processed sugars. They also consist of higher amounts of complex carbohydrates, fibers, high quality proteins and significant water content. Some of the greatest foods to eat in purchase to lose weight are greens, fruits, legumes, baked potato, complete grain foods (including wholemeal pasta, oatmeal, muesli, etc), boiled brown rice, baked potato and fresh fish. Many folks join gyms as a result of the structure and atmosphere that a gym provides. There are pricey machines, advantageous classes, plus trainers available at gyms which could enable we remain on track. But if you are simply going to the gym to utilize the equipment, why not save cash plus create a gym at house? You do not have to have a treadmill plus fat machines. There are many aerobic exercises which you can do at house, and we can usually purchase dumbbells to employ. Buy some good walking shoes or a jump rope to take full benefit of the benefits of these exercises plus lose pounds. 11 Say no to white carbohydrates. This includes white rice, white flour treatments like bread, pastries plus starchy greens such as [http://safedietplansforwomen.com/how-to-lose-weight-fast how to lose weight fast] potatoes. Instead loads up the body on fiber rich foods and lean protein. The fact of the matter is the fact that even though you need to shed pounds and look better, you still have to eat. Where the problem comes in is not constantly how much you eat, but what we eat. That is the difference between burning fat or gaining more. The little secrets mentioned above are nothing however, tiny changes inside a diet that confirm to be really powerful inside terms of your fat reduction efforts. Along with implementing these changes you furthermore have to learn more about a complete weight reduction program that may promote powerful fat loss.