Added shell and counting sort in Ruby (thuva4#478) (thuva4#480) (thuva4#479)

sahupankaj10 · thuva4 · commit 458568519b6b · 2017-10-30T21:05:26.000+05:30
* Create ShellSort.rb * Update Readme.md for thuva4#478 -- shell sort in Ruby * Create CountingSort.rb * added Counting Sort in Ruby
diff --git a/CountingSort/Ruby/CountingSort.rb b/CountingSort/Ruby/CountingSort.rb
@@ -0,0 +1,46 @@
+=begin  
+#Counting Sort is a linear time sort used when range of keys is already known.
+    #Algorithm
+    1. Take a count array to store the frequency of each value in given range
+    2. change count[i] to count[i]+count[i-1],i.e each element now stores the prefix sum of counts.
+    3. take each value from the array and put it at the correct index in output array using count, decrement value of count! (correct index of a[i] will be count[a[i]-1])
+    4. Finally copy the values of output array to array.
+    
+# n is the size of array and k is the range of input
+#Time-complexity: O(n+k), Auxiliary-space:O(n+k), Not In-place, Not stable    
+=end    
+
+
+def counting_sort(a=[9,8,7,6],min=0,max=10)
+    if min>max
+      return "invalid range"
+    end
+    
+  	n=max-min+1
+	count=Array.new(n,0)
+	len=a.length
+	output=Array.new(len)
+  
+  	for i in 0...len
+		count[a[i]-min]+=1
+	end
+	
+  	for i in 1...n
+		count[i]+=count[i-1]
+	end
+		
+	
+	for i in 0...len
+		output[count[a[i]-min]-1]=a[i]
+		count[a[i]-min]-=1
+	end
+	
+	for i in 0...len
+		a[i]=output[i]
+	end
+	
+	return a
+	
+end
+
+puts(counting_sort([9,8,1,2,3,7],-3,10))
diff --git a/README.md b/README.md
@@ -18,7 +18,7 @@ BreadthFirstSearch | :+1: | :+1: |  | :+1: |  |  |  |  |
 Borwein's Algorithm | :+1: |  |  |  | :+1: |  |  |  | ||
 BubbleSort | :+1: | :+1: | :+1: | :+1: | :+1:  | :+1: | :+1:  | :+1: | :+1: | | | :+1:
 Conjugate Gradient |  |  |  |  | :+1: |  |  |  | ||
-CountingSort | :+1: | :+1: |  |  | :+1: |  |  |  | |
+CountingSort | :+1: | :+1: |  |  | :+1: |  |  |  | :+1: |
 CycleSort | :+1: | :+1: |  |  | :+1: |  |  |  | |
 DepthFirstSearch | :+1: | :+1: |  |  | :+1: | :+1: |  |  | |
 Dijkstra's  | :+1: | :+1: |  |  | :+1: | | :+1: |  | |
@@ -55,7 +55,7 @@ Uniform-cost search | :+1: |  |  |  |  | :+1: | :+1: |  |
 RadixSort | :+1: | :+1: |  |  | :+1: |  |  |  |
 RobinCarp | :+1: |  |  |  |  |  |  |  |
 SelectionSort | :+1: | :+1: | :+1: | :+1: | :+1: | :+1: | :+1: | :+1: | :+1:
-ShellSort | :+1: | :+1: |  |  | :+1: |  |  |  |
+ShellSort | :+1: | :+1: |  |  | :+1: |  |  |  | :+1: |
 Sieve of Eratosthenes | :+1: | :+1: |  |  | :+1: | :+1: | :+1: |  |
 UnaryCoding | :+1: | :+1: |  |  |  | :+1: |  |  |
 VEGAS Algorithm |  |  |  |  | :+1: |  |  |  | ||
diff --git a/ShellSort/Ruby/ShellSort.rb b/ShellSort/Ruby/ShellSort.rb
@@ -0,0 +1,33 @@
+#Shell Sort implementation(Diminishing Increment Sort)
+#Time-complexity: O(n^2), In-place
+#will be using Knuth series :3n+1
+
+def shell_sort(a)
+    n=a.length
+    h=1
+    
+    while (h<n/3)  #for computing increment factor "h"
+        h= (3*h)+1
+    end
+    
+    while h>=1
+    # Logic of insertion sort with inrement steps of "h"
+        for i in h...n
+            j=i
+            while j>=h
+                if a[j-h]>a[j]
+                    temp=a[j]
+                    a[j]=a[j-h]
+                    a[j-h]=temp
+                end
+                j-=h
+            end
+        end
+        h/=3
+    end
+    
+    return a
+    
+end
+
+puts(shell_sort([0,5,4,7,1,8,9,3,7,1,4,2,8,6]))
