Added Comb Sort

Hui Chen · Hui Chen · commit a810eb962c4d · 2016-05-28T11:08:58.000-06:00
diff --git a/algorithm/category.json b/algorithm/category.json
@@ -42,7 +42,8 @@
       "quick": "Quicksort",
       "heap" : "Heapsort",
       "shell": "Shellsort",
-      "cycle": "Cycle Sort"
+      "cycle": "Cycle Sort",
+      "comb": "Comb Sort"
     }
   },
   "string": {
diff --git a/algorithm/sorting/comb/basic/code.js b/algorithm/sorting/comb/basic/code.js
@@ -0,0 +1,31 @@
+logger._print('original array = [' + D.join(', ') + ']');
+var N = D.length;
+var swapped;
+var gap = N;            // initialize gap size
+var shrink = 1.3;       // set the gap shrink factor
+
+do{
+    // update the gap value for the next comb.
+    gap = Math.floor( gap/shrink );
+    if( gap < 1 ){
+        // minimum gap is 1
+        gap = 1;
+    }
+
+    swapped = false;    // initialize swapped
+    // a single comb over the input list
+    for( var i=0; i+gap < N; i++ ){
+        if( D[i] > D[i+gap] ){
+            logger._print('swap ' + D[i] + ' and ' + D[i+gap]);     // log swap event
+            
+            var temp = D[i];
+            D[i] = D[i+gap];
+            D[i+gap] = temp;
+
+            tracer._notify(i, D[i])._notify(i+gap, D[i+gap])._wait();
+            tracer._denotify(i)._denotify(i+gap);
+
+            swapped = true;     // Flag swapped has happened and list is not guaranteed sorted
+        }
+    } // End of combing
+} while( gap!=1 || swapped  )
diff --git a/algorithm/sorting/comb/basic/data.js b/algorithm/sorting/comb/basic/data.js
@@ -0,0 +1,4 @@
+var tracer = new Array1DTracer();
+var logger = new LogTracer();
+var D = Array1D.random(15);
+tracer._setData(D);
diff --git a/algorithm/sorting/comb/desc.json b/algorithm/sorting/comb/desc.json
@@ -0,0 +1,13 @@
+{
+  "Comb Sort": "Comb sort is a relatively simple sorting algorithm originally designed by W&#322;odzimierz Dobosiewicz in 1980. Later it was rediscovered by Stephen Lacey and Richard Box in 1991. Comb sort improves on bubble sort. <br /><br />The basic idea is to eliminate turtles, or small values near the end of the list, since in a bubble sort these slow the sorting down tremendously. Rabbits, large values around the beginning of the list, do not pose a problem in bubble sort.",
+  "Complexity": {
+    "time": "worst O(n<sup>2</sup>), best O(n log n), average O(n<sup>2</sup>/2<sup>p</sup>, where p is the number of increment)",
+    "space": "worst O(1) auxiliary"
+  },
+  "References": [
+    "<a href='https://en.wikipedia.org/wiki/Comb_sort'>Wikipedia</a>"
+  ],
+  "files": {
+    "basic": "Bubble sort"
+  }
+}
