Binsort algoritmo

BIN SORT ALGORITHM (Also called Radix Sort & Bucket Sort)

The algorithm below requires an array of linked lists. Assume DLLs are used for all the linked lists in this description. All the examples below use positive data. A mix of positive and negative data seriously complicates the task of writing a correct Bin Sort.

The program begins with the unsorted data in a linked list. In thisdescription, this will be called the master list. In Java, this could be an array of a reference type instead. Copies of the pointers in the array could be stored in the bins. Thus the data would never be moved.

There will also be an array of ten bins 0..9. Each bin will be the head pointer of a linked list. Thus there are eleven lists in all, the master list and the lists in the 10 bins.

Theprogram begins by breaking apart the master list, and placing each node at the rear of one of the bin lists. The master list is then reassembled from the 10 bins by linking them head to tail. This breakdown and reassembly is guided by the data in the nodes, and continues until the list is sorted.

Assume this is the initial content of the master list with 52 at the head and 40 at the tail.Master: 52, 94, 56, 32, 78, 3, 17, 92, 47, 39, 8, 28, 80, 53, 25, 58, 82, 21, 12, 40

Part 1. While the master list is not empty:
Detach the head node from the master list.
Attach this node to the tail of the bin corresponding to the ones digit. (%10)
(Move 52 to the 2 bin, then 94 to the 4 bin, and so on.)

Producing: Bin List
[0] 80, 40[1] 21
[2] 52, 32, 92, 82, 12
[3] 3, 53
[4] 94
[5] 25
[6] 56
[7] 17, 47
[8] 78, 8, 28, 58
[9] 39

Part 2. Rebuild the master list by attaching the bins head to tail producing:
Master: 80, 40, 21, 52, 32, 92, 82, 12, 3, 53, 94,25, 56, 17, 47, 78, 8, 28, 58, 39
Master: 80, 40, 21, 52, 32, 92, 82, 12, 3, 53, 94, 25, 56, 17, 47, 78, 8, 28, 58, 39

Repeat Parts 1 & 2 on this list, but use the tens digit (/10 then %10):

After part 1: Bin List
[0] 3, 8
[1] 12, 17
[2] 21, 25, 28
[3] 32, 39
[4] 40, 47
[5] 52, 53, 56, 58
[6][7] 78
[8] 80, 82
[9] 92, 94

And after part 2:

Master: 3, 8, 12, 17, 21, 25, 28, 32, 39, 40, 47, 52, 53, 56, 58, 78, 80, 82, 92, 94

Clearly for three digit numbers we would make three passes, etc. Inserting at the rear of the bin maintains the ones digit ordering while imposing tens digit ordering.

Analysis of the Algorithm: (First, realize this is anaddress calculation sort.)
Part 1 - filling the bins while breaking apart the master list, takes time O(N) assuming N items in the master list.
Part 2 - reassembling the master list from the bins, takes time O(B) assuming B bins, as we do not have to scan the contents of the bins to re-link them. Watch out for empty bins.

The width of the key determines the number of times parts 1 and 2 must beperformed. Let us call it the number of passes (P). Thus the total time required for the Bin Sort is:

O { P(N+B) } The list of N items is divided into B bins ( O(N) ), then reassembled into one list ( O(B) ). These two steps are repeated P times.

The speed of the sort is dependent upon the sizes of P and B relative to N. Remember the fast comparison sorts are O{ N * log(N) }, so if B isrelatively small and P is on the order of log(N) this sort can be very fast.

How many bins should you use? P( N +B ) can be your guide.
Notice first, there is a tradeoff between the number of bins and the number of passes. Suppose you are writing a bin sort of 500 positive integers all less than 1,000,000. You could use 6 passes and 10 bins or perhaps 3 passes and 100...