1- /**
2- * Bucketsort. This algorithm has complexity O(n) but it's not
3- * correct for every input.
4- *
5- *@public
6- */
7- var bucketSort = ( function ( ) {
1+ ( function ( exports ) {
2+
3+ 'use strict' ;
84
95/**
10- * Insertionsort.
6+ * Bucketsort. This algorithm has complexity O(n) but it's not
7+ * correct for every input.
118 *
12- *@private
13- *@param {array } array Input array
14- *@returns {array } array Sorted input array
9+ *@public
1510 */
16- function insertionSort ( array ) {
17- var current ,
18- j ;
19- for ( var i = 1 ; i < array . length ; i += 1 ) {
20- current = array [ i ] ;
21- j = i - 1 ;
22- while ( j >= 0 && current < array [ j ] ) {
23- array [ j + 1 ] = array [ j ] ;
24- j -= 1 ;
11+ var bucketSort = ( function ( ) {
12+
13+ /**
14+ * Insertionsort.
15+ *
16+ *@private
17+ *@param {array } array Input array
18+ *@returns {array } array Sorted input array
19+ */
20+ function insertionSort ( array ) {
21+ var current ,
22+ j ;
23+ for ( var i = 1 ; i < array . length ; i += 1 ) {
24+ current = array [ i ] ;
25+ j = i - 1 ;
26+ while ( j >= 0 && current < array [ j ] ) {
27+ array [ j + 1 ] = array [ j ] ;
28+ j -= 1 ;
29+ }
30+ array [ j + 1 ] = current ;
2531}
26- array [ j + 1 ] = current ;
32+ return array ;
2733}
28- return array ;
29- }
3034
31- /**
32- * Creates buckets for given array
33- *
34- *@private
35- *@param {array } array Input array
36- *@returns {array } buckets Array whith array for each bucket.
37- * Each bucket contains an array with all elements from the input which are with suitable size.
38- */
39- function createBuckets ( array ) {
40- var buckets = [ ] ,
41- currentBucket ,
42- current ,
43- sectorSize = 1 / array . length ;
44- for ( var i = 0 ; i < array . length ; i += 1 ) {
45- current = array [ i ] ;
46- currentBucket = Math . floor ( current / sectorSize ) ;
47- if ( buckets [ currentBucket ] === undefined ) {
48- buckets [ currentBucket ] = [ ] ;
35+ /**
36+ * Creates buckets for given array
37+ *
38+ *@private
39+ *@param {array } array Input array
40+ *@returns {array } buckets Array whith array for each bucket.
41+ * Each bucket contains an array with all elements from the input which are with suitable size.
42+ */
43+ function createBuckets ( array ) {
44+ var buckets = [ ] ,
45+ currentBucket ,
46+ current ,
47+ sectorSize = 1 / array . length ;
48+ for ( var i = 0 ; i < array . length ; i += 1 ) {
49+ current = array [ i ] ;
50+ currentBucket = Math . floor ( current / sectorSize ) ;
51+ if ( buckets [ currentBucket ] === undefined ) {
52+ buckets [ currentBucket ] = [ ] ;
53+ }
54+ buckets [ currentBucket ] . push ( current ) ;
4955}
50- buckets [ currentBucket ] . push ( current ) ;
56+ return buckets ;
5157}
52- return buckets ;
53- }
5458
55- /**
56- * Sorts the arrays from each bucket.
57- *
58- *@private
59- *@param {array } buckets Given buckets
60- *@returns {array } buckets Buckets with sorted arrays for each bucket
61- */
62- function sortBuckets ( buckets ) {
63- for ( var i = 0 ; i < buckets . length ; i += 1 ) {
64- if ( buckets [ i ] !== undefined ) {
65- insertionSort ( buckets [ i ] ) ;
59+ /**
60+ * Sorts the arrays from each bucket.
61+ *
62+ *@private
63+ *@param {array } buckets Given buckets
64+ *@returns {array } buckets Buckets with sorted arrays for each bucket
65+ */
66+ function sortBuckets ( buckets ) {
67+ for ( var i = 0 ; i < buckets . length ; i += 1 ) {
68+ if ( buckets [ i ] !== undefined ) {
69+ insertionSort ( buckets [ i ] ) ;
70+ }
6671}
72+ return buckets ;
6773}
68- return buckets ;
69- }
7074
71- /**
72- * Unions all buckets' arrays
73- *
74- *@private
75- *@param {array } buckets Input buckets
76- *@returns {array } result Sorted array which contains all elements form each bucket
77- */
78- function unionBuckets ( buckets ) {
79- var result = [ ] ,
80- currentBucket ;
81- for ( var i = 0 ; i < buckets . length ; i += 1 ) {
82- currentBucket = buckets [ i ] ;
83- if ( currentBucket !== undefined ) {
84- for ( var j = 0 ; j < currentBucket . length ; j += 1 ) {
85- result . push ( currentBucket [ j ] ) ;
75+ /**
76+ * Unions all buckets' arrays
77+ *
78+ *@private
79+ *@param {array } buckets Input buckets
80+ *@returns {array } result Sorted array which contains all elements form each bucket
81+ */
82+ function unionBuckets ( buckets ) {
83+ var result = [ ] ,
84+ currentBucket ;
85+ for ( var i = 0 ; i < buckets . length ; i += 1 ) {
86+ currentBucket = buckets [ i ] ;
87+ if ( currentBucket !== undefined ) {
88+ for ( var j = 0 ; j < currentBucket . length ; j += 1 ) {
89+ result . push ( currentBucket [ j ] ) ;
90+ }
8691}
8792}
93+ return result ;
8894}
89- return result ;
90- }
9195
92- /**
93- * Sorts given array with bucketsort
94- *
95- *@public
96- *@param {array } array Input array which should be sorted
97- *@returns {array } Sorted array
98- */
99- return function ( array ) {
100- var buckets = createBuckets ( array ) ;
101- sortBuckets ( buckets ) ;
102- return unionBuckets ( buckets ) ;
103- } ;
104- } ( ) ) ;
96+ /**
97+ * Sorts given array with bucketsort
98+ *
99+ *@public
100+ *@param {array } array Input array which should be sorted
101+ *@returns {array } Sorted array
102+ */
103+ return function ( array ) {
104+ var buckets = createBuckets ( array ) ;
105+ sortBuckets ( buckets ) ;
106+ return unionBuckets ( buckets ) ;
107+ } ;
108+ } ( ) ) ;
109+
110+ exports . bucketSort = bucketSort ;
111+
112+ } ( typeof exports === 'undefined' ?window :exports ) ) ;