Merge branch 'gh-pages' of https://github.com/parkjs814/AlgorithmVisualizer into gh-pages

64json · 64json · commit 0f883f755dc0 · 2016-05-25T00:02:17.000-05:00
diff --git a/README.md b/README.md
@@ -1,11 +1,83 @@
 # Algorithm Visualizer
 
 [![Join the chat at https://gitter.im/parkjs814/AlgorithmVisualizer](https://badges.gitter.im/parkjs814/AlgorithmVisualizer.svg)](https://gitter.im/parkjs814/AlgorithmVisualizer?utm_source=badge&utm_medium=badge&utm_campaign=pr-badge&utm_content=badge)
+[![OpenCollective](https://opencollective.com/algorithmvisualizer/backers/badge.svg)](#backers) 
+[![OpenCollective](https://opencollective.com/algorithmvisualizer/sponsors/badge.svg)](#sponsors)
+
 http://parkjs814.github.io/AlgorithmVisualizer
 
 ![Algorithm Visualizer](http://i.giphy.com/3o6EhJFgsyShX6MHeM.gif)
 
-Check out [**Wiki**](https://github.com/parkjs814/AlgorithmVisualizer/wiki) to add more algorithms!
+### Contributing
+If you run _Algorithm Visualizer_ locally and files are not loaded because Cross-Origin Requests are blocked, use [http-server](https://github.com/indexzero/http-server) or [SimpleHTTPServer](https://docs.python.org/2/library/simplehttpserver.html) to resolve the issue. [(Issue #2)](https://github.com/parkjs814/AlgorithmVisualizer/issues/2)
+
+If in need of any help check out or [**Wiki**](https://github.com/parkjs814/AlgorithmVisualizer/wiki) or join our [Gitter](https://gitter.im/parkjs814/AlgorithmVisualizer?utm_source=share-link&utm_medium=link&utm_campaign=share-link) chatroom!
+### Backers
+
+Support us with a monthly donation and help us continue our activities. [[Become a backer](https://opencollective.com/algorithmvisualizer#backer)]
+
+<a href="https://opencollective.com/algorithmvisualizer/backer/0/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/backer/0/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/backer/1/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/backer/1/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/backer/2/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/backer/2/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/backer/3/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/backer/3/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/backer/4/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/backer/4/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/backer/5/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/backer/5/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/backer/6/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/backer/6/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/backer/7/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/backer/7/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/backer/8/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/backer/8/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/backer/9/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/backer/9/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/backer/10/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/backer/10/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/backer/11/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/backer/11/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/backer/12/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/backer/12/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/backer/13/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/backer/13/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/backer/14/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/backer/14/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/backer/15/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/backer/15/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/backer/16/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/backer/16/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/backer/17/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/backer/17/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/backer/18/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/backer/18/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/backer/19/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/backer/19/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/backer/20/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/backer/20/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/backer/21/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/backer/21/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/backer/22/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/backer/22/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/backer/23/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/backer/23/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/backer/24/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/backer/24/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/backer/25/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/backer/25/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/backer/26/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/backer/26/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/backer/27/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/backer/27/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/backer/28/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/backer/28/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/backer/29/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/backer/29/avatar.svg"></a>
+
+### Sponsors
+
+Become a sponsor and get your logo on our README on Github with a link to your site. [[Become a sponsor](https://opencollective.com/algorithmvisualizer#sponsor)]
 
-### Run it locally
-If you run _Algorithm Visualizer_ locally and files are not loaded because Cross-Origin Requests are blocked, use [http-server](https://github.com/indexzero/http-server) to resolve the issue. [(Issue #2)](https://github.com/parkjs814/AlgorithmVisualizer/issues/2)
+<a href="https://opencollective.com/algorithmvisualizer/sponsor/0/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/sponsor/0/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/sponsor/1/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/sponsor/1/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/sponsor/2/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/sponsor/2/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/sponsor/3/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/sponsor/3/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/sponsor/4/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/sponsor/4/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/sponsor/5/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/sponsor/5/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/sponsor/6/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/sponsor/6/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/sponsor/7/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/sponsor/7/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/sponsor/8/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/sponsor/8/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/sponsor/9/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/sponsor/9/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/sponsor/10/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/sponsor/10/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/sponsor/11/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/sponsor/11/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/sponsor/12/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/sponsor/12/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/sponsor/13/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/sponsor/13/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/sponsor/14/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/sponsor/14/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/sponsor/15/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/sponsor/15/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/sponsor/16/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/sponsor/16/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/sponsor/17/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/sponsor/17/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/sponsor/18/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/sponsor/18/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/sponsor/19/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/sponsor/19/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/sponsor/20/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/sponsor/20/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/sponsor/21/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/sponsor/21/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/sponsor/22/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/sponsor/22/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/sponsor/23/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/sponsor/23/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/sponsor/24/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/sponsor/24/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/sponsor/25/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/sponsor/25/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/sponsor/26/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/sponsor/26/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/sponsor/27/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/sponsor/27/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/sponsor/28/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/sponsor/28/avatar.svg"></a>
+<a href="https://opencollective.com/algorithmvisualizer/sponsor/29/website" target="_blank"><img src="https://opencollective.com/algorithmvisualizer/sponsor/29/avatar.svg"></a>
diff --git a/algorithm/category.json b/algorithm/category.json
@@ -30,7 +30,8 @@
       "bubble": "Bubble Sort",
       "quick": "Quicksort",
       "merge": "Mergesort",
-      "heap" : "Heap Sort"
+      "heap" : "Heap Sort",
+      "radix" : "Radix Sort"
     }
   },
   "string": {
diff --git a/algorithm/etc/dp/desc.json b/algorithm/etc/dp/desc.json
@@ -11,6 +11,7 @@
     "fibonacci": "Fibonacci Sequence",
     "sliding_window": "Finding the largest sum of three contiguous number",
     "max_sum_path": "Finding the maximum sum in a path from (0, 0) to (N-1, M-1) when can only move to right or down",
-    "longest_increasing_subsequence": "Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order"
+    "longest_increasing_subsequence": "Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order",
+    "max_subarray": "Find the sum of the maximum Subarray in the given Array"
   }
 }
diff --git a/algorithm/etc/dp/longest_increasing_subsequence/code.js b/algorithm/etc/dp/longest_increasing_subsequence/code.js
@@ -1,11 +1,11 @@
 // Initialize LIS values for all indexes
-for (var i = 0; i < 20; i++) {
+for (var i = 0; i < A.length; i++) {
     LIS[i] = 1;
 }
 
 logger._print('Calculating Longest Increasing Subsequence values in bottom up manner ');
 // Compute optimized LIS values in bottom up manner
-for (var i = 1; i < 10; i++) {
+for (var i = 1; i < A.length; i++) {
     tracer._select(i);
     logger._print(' LIS[' + i + '] = ' + LIS[i]);
     for (var j = 0; j < i; j++) {
@@ -22,9 +22,9 @@ for (var i = 1; i < 10; i++) {
 // Pick maximum of all LIS values
 logger._print('Now calculate maximum of all LIS values ');
 var max = LIS[0];
-for (var i = 1; i < 10; i++) {
-    if (max < LIS[i]) {
-        max = LIS[i];
-    }
+for (var i = 1; i < A.length; i++) {
+	if (max < LIS[i]) {
+		max = LIS[i];
+	}
 }
 logger._print('Longest Increasing Subsequence = max of all LIS = ' + max);
diff --git a/algorithm/etc/dp/longest_increasing_subsequence/data.js b/algorithm/etc/dp/longest_increasing_subsequence/data.js
@@ -1,5 +1,5 @@
 var tracer = new Array1DTracer();
 var logger = new LogTracer();
 var A = Array1D.random(10, 0, 10);
-var LIS = new Array(10);
+var LIS = new Array(A.length);
 tracer._setData(A);
diff --git a/algorithm/etc/dp/max_subarray/code.js b/algorithm/etc/dp/max_subarray/code.js
@@ -0,0 +1,29 @@
+var maxSubarraySum = (function maxSubarray (array) {
+	var maxSoFar = 0,
+		maxEndingHere = 0;
+
+	tracer._print ('Initializing maxSoFar = 0 & maxEndingHere = 0');
+
+	for (var i = 0; i < array.length; i++) {
+		tracer._select (i);
+		tracer._print (maxEndingHere + ' + ' + array [i]);
+		maxEndingHere += array [i];
+		tracer._print ('=> ' + maxEndingHere);
+
+		if (maxEndingHere < 0) {
+			tracer._print ('maxEndingHere is negative, set to 0');
+			maxEndingHere = 0;
+		}
+
+		if (maxSoFar < maxEndingHere) {
+			tracer._print ('maxSoFar < maxEndingHere, setting maxSoFar to maxEndingHere (' + maxEndingHere + ')');
+			maxSoFar = maxEndingHere;
+		}
+		
+		tracer._deselect (i);
+	}
+
+	return maxSoFar;
+}) (D);
+
+tracer._print ('Maximum Subarray\'s Sum is: ' + maxSubarraySum);
diff --git a/algorithm/etc/dp/max_subarray/data.js b/algorithm/etc/dp/max_subarray/data.js
@@ -0,0 +1,4 @@
+var tracer = new Array1DTracer ();
+var D = [-2, -3, 4, -1, -2, 1, 5, -3];
+
+tracer._setData (D);
diff --git a/algorithm/sorting/heap/basic/code.js b/algorithm/sorting/heap/basic/code.js
@@ -51,6 +51,6 @@ function heapify(array, size, root) {
     }
 }
 
-heapSort(D, 10);
+heapSort(D, D.length);
 
 logger._print('Final array = [' + D.join(', ') + ']');
diff --git a/algorithm/sorting/radix/desc.json b/algorithm/sorting/radix/desc.json
@@ -0,0 +1,13 @@
+{
+  "Radix LSD Sort": "Radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value.",
+  "Complexity": {
+    "time": "worst O(n), best O(n), average O(n)",
+    "space": "always O(n)"
+  },
+  "References": [
+    "<a href='https://en.wikipedia.org/wiki/Radix_sort'>Wikipedia</a>"
+  ],
+  "files": {
+    "lsd": "LSD Radix sort"
+  }
+}
diff --git a/algorithm/sorting/radix/lsd/code.js b/algorithm/sorting/radix/lsd/code.js
@@ -0,0 +1,44 @@
+tracer._print('original array = [' + D[0].join(', ') + ']');
+tracer._sleep(1000);
+tracer._pace(300);
+function pow(base, expo){
+	var ans = 1;
+	for(var i = 0; i < expo;i++){
+		ans *= base;
+	}
+	return ans;
+}
+for(var exp = 0; exp < 3;exp ++){
+	tracer._print("Digit: "+exp);
+	for(var i = 0; i < D[0].length; i++){
+		tracer._select(0, i);
+		D[2][ parseInt( D[0][i] / pow(10, exp)  % 10) ] += 1;
+		tracer._notify(2, parseInt( D[0][i] / pow(10, exp)  % 10) );
+		tracer._deselect(0, i);
+	}
+	for(var i = 1; i < 10; i++){
+		tracer._select(2, i - 1);
+		D[2][i] += D[2][i - 1];
+		tracer._notify(2, i);
+		tracer._deselect(2, i - 1);
+	}
+	for(var i = D[0].length - 1; i >= 0; i--){
+		tracer._select(0, i);
+		D[2][parseInt( D[0][i] / pow(10, exp)  % 10) ] -= 1;
+		tracer._notify(2, parseInt( D[0][i] / pow(10, exp)  % 10) );
+		D[1][ D[2][ parseInt( D[0][i] / pow(10, exp)  % 10) ] ] = D[0][i];
+		tracer._notify(1, D[2][ parseInt( D[0][i] / pow(10, exp)  % 10) ] );
+		tracer._deselect(0, i);
+	}
+	for(var i = 0; i < D[0].length; i++){
+		tracer._select(1, i);
+		D[0][i] = D[1][i];
+		tracer._notify(0, i);
+		tracer._deselect(1, i);
+	}
+	for(var i = 0; i < 10; i++){
+		D[2][i] = 0;
+		tracer._notify(2, i);
+	}	
+}
+tracer._print('sorted array = [' + D[0].join(', ') + ']');
diff --git a/algorithm/sorting/radix/lsd/data.js b/algorithm/sorting/radix/lsd/data.js
@@ -0,0 +1,8 @@
+var tracer = new Array2DTracer();
+var k = Array1D.random(10, 1, 999);
+var D = [
+  k,
+  [0,0,0,0,0,0,0,0,0,0],
+  [0,0,0,0,0,0,0,0,0,0]
+];
+tracer._setData(D);
diff --git a/algorithm/sorting/selection/basic/code.js b/algorithm/sorting/selection/basic/code.js
@@ -3,11 +3,13 @@ for (var i = 0; i < D.length - 1; i++) {
     var minJ = i;
     tracer._select(i)._wait();
     for (var j = i + 1; j < D.length; j++) {
+    	tracer._select(j)._wait();
         if (D[j] < D[minJ]) {
-            tracer._select(j)._wait();
             minJ = j;
-            tracer._deselect(j);
+            tracer._notify(j)._wait();
+            tracer._denotify(j);
         }
+        tracer._deselect(j);
     }
     if (minJ != i) {
         logger._print('swap ' + D[i] + ' and ' + D[minJ]);

Original file line number	Diff line number	Diff line change
`@@ -11,6 +11,7 @@`
`11`	`11`	`"fibonacci": "Fibonacci Sequence",`
`12`	`12`	`"sliding_window": "Finding the largest sum of three contiguous number",`
`13`	`13`	`"max_sum_path": "Finding the maximum sum in a path from (0, 0) to (N-1, M-1) when can only move to right or down",`
`14`		`- "longest_increasing_subsequence": "Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order"`
	`14`	`+ "longest_increasing_subsequence": "Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order",`
	`15`	`+ "max_subarray": "Find the sum of the maximum Subarray in the given Array"`
`15`	`16`	`}`
`16`	`17`	`}`
Original file line number	Diff line number	Diff line change
`@@ -51,6 +51,6 @@ function heapify(array, size, root) {`
`51`	`51`	`}`
`52`	`52`	`}`
`53`	`53`
`54`		`-heapSort(D, 10);`
	`54`	`+heapSort(D, D.length);`
`55`	`55`
`56`	`56`	`logger._print('Final array = [' + D.join(', ') + ']');`