Merge pull request algorithm-visualizer#199 from archie94/pigeonhole-sort

TornjV · web-flow · commit b0c446ce9c58 · 2016-06-28T21:36:30.000+02:00
Implemented Pigeonhole Sort
diff --git a/algorithm/category.json b/algorithm/category.json
@@ -73,11 +73,12 @@
          "bucket": "Bucket Sort",
          "bubble": "Bubble Sort",
          "comb": "Comb Sort",
-		 "counting": "Counting Sort",
+         "counting": "Counting Sort",
          "cycle": "Cycle Sort",
          "heap": "Heapsort",
          "insertion": "Insertion Sort",
          "merge": "Merge Sort",
+         "pigeonhole": "Pigeonhole Sort",
          "quick": "Quicksort",
          "radix": "Radix Sort",
          "selection": "Selection Sort",
diff --git a/algorithm/sorting/pigeonhole/basic/code.js b/algorithm/sorting/pigeonhole/basic/code.js
@@ -0,0 +1,42 @@
+var min = A[0];
+var max = A[0];
+
+for( var  i = 1; i < N; i++ ) {
+	if( A[i] < min ) {
+		min = A[i];
+	}
+	if( A[i] > max ) {
+		max = A[i];
+	}
+}
+var range = max - min + 1;
+
+var holes = new Array ( range );
+for ( var i = 0; i < range; i++ ) {
+	holes[i] = [];
+}
+tracer2._setData( holes );
+
+logTracer._print ( 'Filling up holes' );
+for ( var i = 0; i < N ; i++ ) {
+	tracer1._select ( i )._wait ();
+
+	holes[ A[i] - min ].push( A[i] );
+	
+	tracer2._setData( holes );
+	tracer1._deselect ( i );
+}
+
+logTracer._print ( 'Building sorted array' );
+var k = 0;
+for ( var i = 0; i < range ; i++ ) {
+	for (var j = 0; j < holes[i].length; j++ ) {
+		tracer2._select ( i, j )._wait ();
+		A[k++] = holes[i][j];
+		tracer1._notify ( k-1, A[k-1] )._wait ();
+		tracer2._deselect ( i, j );
+		tracer1._denotify ( k-1 );
+	}
+}
+
+logTracer._print ( 'Sorted array is ' + A );
diff --git a/algorithm/sorting/pigeonhole/basic/data.js b/algorithm/sorting/pigeonhole/basic/data.js
@@ -0,0 +1,6 @@
+var A = Array1D.random(7);
+var N = A.length;
+
+var tracer1 = new Array1DTracer ( 'Array' )._setData ( A );
+var tracer2 = new Array2DTracer ( 'Holes' );
+var logTracer = new LogTracer ( 'Console' );
diff --git a/algorithm/sorting/pigeonhole/desc.json b/algorithm/sorting/pigeonhole/desc.json
@@ -0,0 +1,13 @@
+{
+  "Pigeonhole Sort": "Pigeonhole sorting is a sorting algorithm that is suitable for sorting lists of elements where the number of elements (n) and the number of possible key values (N) are approximately the same.",
+  "Complexity": {
+    "time": " O(n + N)",
+    "space": "O(n)"
+  },
+  "References": [
+    "<a href='https://en.wikipedia.org/wiki/Pigeonhole_sort'>Wikipedia</a>"
+  ],
+  "files": {
+    "basic": "Pigeonhole Sort"
+  }
+}
