counting sort fix

3 files changed, 9 insertions, 4 deletions

diff --git a/src/table.c b/src/table.c
index 795994d..3c023d8 100644
--- a/src/table.c
+++ b/src/table.c
@@ -358,8 +358,11 @@ int l_countingsort(lua_State* L) {
 
       lua_pop(L,1);
     }
+   
+    //required because max can be too big for the stack :c
+    int* count = malloc(sizeof *count * (max + 1));
+    //int count[max + 1];
 
-    int count[max + 1];
     for(size_t i = 0; i <= max; i++) count[i] = 0;
 
     for(size_t i = 0; i < len; i++){
@@ -381,7 +384,8 @@ int l_countingsort(lua_State* L) {
       lua_pushnumber(L,out[i]);
       lua_settable(L, -3);
     }
-
+    
+    free(count);
     return 1;
 }
 
diff --git a/src/table.h b/src/table.h
index 9f0ec63..c93bc7d 100644
--- a/src/table.h
+++ b/src/table.h
@@ -17,6 +17,7 @@ int l_bubblesort(lua_State*);   //[double+int] -> arr[N] (greatest -> least)
 int l_heapsort(lua_State*);     //[double+int] -> arr[N] (greatest -> least)
 
 //non-comparison sorts
+  //good for large arrays filled with small values
 int l_countingsort(lua_State*); //[int], arr[N] >= 0 -> arr[N] (greatest -> least)
 
 //esoteric sorts
diff --git a/t.lua b/t.lua
index 5e6dc45..2e906db 100644
--- a/t.lua
+++ b/t.lua
@@ -3,7 +3,7 @@ local a = llib.array
 
 local tab = {}
 math.randomseed(os.time())
-for i=1,19 do
+for i=1,9999 do
   table.insert(tab,math.random(1,999));-- + math.random(1,999));
 end
 
@@ -28,7 +28,7 @@ local l6 = a.countingsort(tab)
 print("counting sort took "..os.clock()-time.."s")
 
 for l,i in pairs(llib.array.reverse(l1)) do
-  print(l1[l].." "..l2[l].." "..l3[l].." "..l4[l].." "..l5[l])
+  --print(l1[l].." "..l2[l].." "..l3[l].." "..l4[l].." "..l5[l])
 end
 --print(llib.array.greatest(l1))
 --local l2 = llib.array.reverse(llib.array.bubblesort(tab))