Merge pull request algorithm-visualizer#190 from jarettgross/bucket-sort

TornjV · web-flow · commit e3e017e13500 · 2016-06-22T00:13:30.000+02:00
Implemented bucket sort
diff --git a/algorithm/category.json b/algorithm/category.json
@@ -69,6 +69,7 @@
    },
    "sorting": {
       "list": {
+         "bucket": "Bucket Sort",
          "bubble": "Bubble Sort",
          "comb": "Comb Sort",
 		 "counting": "Counting Sort",
diff --git a/algorithm/sorting/bucket/basic/code.js b/algorithm/sorting/bucket/basic/code.js
@@ -0,0 +1,34 @@
+//place numbers into appropriate buckets
+for (let i = 0; i < array.length; i++) {
+	var bucketPos = Math.floor(numBuckets * (array[i] / maxValue));
+	buckets[bucketPos].push(array[i]);
+	bucketsCount[bucketPos]++;
+	tracer._select(0, i)._wait();
+	tracer._notify(1, bucketPos, D[1][bucketPos])._wait();
+	tracer._deselect(0, i);
+	tracer._denotify(1, bucketPos, D[1][bucketPos]);
+}
+
+var sortLocation = 0;
+for (let k = 0; k < buckets.length; k++) {
+	//do insertion sort
+	for (let i = 1; i < buckets[k].length; i++) {
+		var key = buckets[k][i];
+		var j;
+		for (j = i - 1; (j >= 0) && (buckets[k][j] > key); j--) {
+			buckets[k][j + 1] = buckets[k][j];
+		}
+		buckets[k][j + 1] = key;
+	}
+	
+	//place ordered buckets into sorted array
+	for (let i = 0; i < buckets[k].length; i++) {
+		sortedArray[sortLocation] = buckets[k][i];
+		bucketsCount[k]--;
+		tracer._notify(1, k, D[1][k]);
+        tracer._notify(2, sortLocation, D[2][sortLocation])._wait();
+		tracer._denotify(1, k, D[1][k]);
+        tracer._denotify(2, sortLocation, D[2][sortLocation]);
+		sortLocation++;
+	}
+}
diff --git a/algorithm/sorting/bucket/basic/data.js b/algorithm/sorting/bucket/basic/data.js
@@ -0,0 +1,24 @@
+var maxValue = 100;
+var arraySize = 10;
+var numBuckets = 5;
+
+//initialize array values
+var array = Array1D.random(arraySize, 0, maxValue - 1);
+var buckets = [];
+var bucketsCount = [];
+var sortedArray = [];
+for (let i = 0; i < arraySize; i++) {
+    if (i < numBuckets) {
+		buckets[i] = [];
+		bucketsCount[i] = 0;
+	}
+    sortedArray[i] = 0;
+}	
+var D = [
+    array,
+    bucketsCount,
+    sortedArray
+];
+
+var tracer = new Array2DTracer();
+tracer._setData(D);
diff --git a/algorithm/sorting/bucket/desc.json b/algorithm/sorting/bucket/desc.json
@@ -0,0 +1,13 @@
+{
+  "Bucket Sort": "Bucket sort, or bin sort, is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm.",
+  "Complexity": {
+    "time": "worst O(n<sup>2</sup>), best O(n+k), average O(n+k) where n is the number of buckets and k is the range of the input",
+    "space": "worst O(n*k)"
+  },
+  "References": [
+    "<a href='https://en.wikipedia.org/wiki/Bucket_sort'>Wikipedia</a>"
+  ],
+  "files": {
+    "basic": "Bucket sort"
+  }
+}
