use heap over stack

3 files changed, 43 insertions, 36 deletions

diff --git a/src/table.c b/src/table.c
index 3c023d8..06e368f 100644
--- a/src/table.c
+++ b/src/table.c
@@ -10,7 +10,7 @@ int l_len(lua_State* L) {
 int l_reverse(lua_State* L) {
     luaL_checktype(L, 1, LUA_TTABLE);
     size_t len = lua_objlen(L,1);
-    double nums[len];
+    double* nums = malloc(sizeof * nums * len);
     for(size_t i = 0; i <= len-1; i++){
 
       lua_pushinteger(L,i+1);
@@ -27,6 +27,7 @@ int l_reverse(lua_State* L) {
       lua_settable(L, -3);
     }
 
+    free(nums);
     return 1;
 }
 
@@ -81,7 +82,7 @@ void i_shuffle(double* arr, size_t len){
 int l_shuffle(lua_State* L) {
     luaL_checktype(L, 1, LUA_TTABLE);
     size_t len = lua_objlen(L,1);
-    double nums[len];
+    double* nums = malloc(sizeof * nums * len);
     for(int i = 0; i <= len-1; i++){
 
       lua_pushinteger(L,i+1);
@@ -100,6 +101,7 @@ int l_shuffle(lua_State* L) {
       lua_settable(L, -3);
     }
 
+    free(nums);
     return 1;
 }
 
@@ -130,7 +132,7 @@ void i_quicksort(double* arr, int low, int high){
 int l_quicksort(lua_State* L) {
     luaL_checktype(L, 1, LUA_TTABLE);
     size_t len = lua_objlen(L,1); 
-    double nums[len];
+    double* nums = malloc(sizeof * nums * len);
     for(size_t i = 0; i <= len-1; i++){
 
       lua_pushinteger(L,i+1);
@@ -149,6 +151,7 @@ int l_quicksort(lua_State* L) {
       lua_settable(L, -3);
     }
 
+    free(nums);
     return 1;
 }
 
@@ -156,8 +159,8 @@ void i_merge(double* arr, int b, int m, int e){
     int n1 = m - b + 1;
     int n2 = e - m;
 
-    double left[n1];
-    double right[n2];
+    double* left = malloc(sizeof * left * n1);
+    double* right = malloc(sizeof * right * n2);
 
     for(int i = 0; i < n1; i++) left[i] = arr[b + i];
     for(int i = 0; i < n2; i++) right[i] = arr[m + 1 + i];
@@ -184,6 +187,9 @@ void i_merge(double* arr, int b, int m, int e){
       arr[k] = right[r_ind];
       r_ind++;
     }
+
+    free(left);
+    free(right);
 }
 
 void i_mergesort(double* arr, int b, int e){
@@ -198,7 +204,7 @@ void i_mergesort(double* arr, int b, int e){
 int l_mergesort(lua_State* L) {
     luaL_checktype(L, 1, LUA_TTABLE);
     size_t len = lua_objlen(L,1); 
-    double nums[len];
+    double* nums = malloc(sizeof * nums * len);
     for(size_t i = 0; i <= len-1; i++){
 
       lua_pushinteger(L,i+1);
@@ -217,6 +223,7 @@ int l_mergesort(lua_State* L) {
       lua_settable(L, -3);
     }
 
+    free(nums);
     return 1;
 }
 
@@ -240,7 +247,7 @@ void i_heapify(double* arr, int n, int i){
 int l_heapsort(lua_State* L) {
     luaL_checktype(L, 1, LUA_TTABLE);
     size_t len = lua_objlen(L,1); 
-    double nums[len];
+    double* nums = malloc(sizeof * nums * len);
     for(size_t i = 0; i <= len-1; i++){
 
       lua_pushinteger(L,i+1);
@@ -262,14 +269,14 @@ int l_heapsort(lua_State* L) {
       lua_pushnumber(L,nums[i]);
       lua_settable(L, -3);
     }
-
+    free(nums);
     return 1;
 }
 
 int l_shellsort(lua_State* L) {
     luaL_checktype(L, 1, LUA_TTABLE);
     size_t len = lua_objlen(L,1);
-    double nums[len];
+    double* nums = malloc(sizeof * nums * len);
     for(size_t i = 0; i <= len-1; i++){
 
       lua_pushinteger(L,i+1);
@@ -297,13 +304,14 @@ int l_shellsort(lua_State* L) {
       lua_settable(L, -3);
     }
 
+    free(nums);
     return 1;
 }
 
 int l_bubblesort(lua_State* L) {
     luaL_checktype(L, 1, LUA_TTABLE);
     size_t len = lua_objlen(L,1);
-    double nums[len];
+    double* nums = malloc(sizeof * nums * len);
     for(size_t i = 0; i <= len-1; i++){
 
       lua_pushinteger(L,i+1);
@@ -336,14 +344,16 @@ int l_bubblesort(lua_State* L) {
       lua_pushnumber(L,nums[i]);
       lua_settable(L, -3);
     }
-
+    
+    free(nums);
     return 1;
 }
 
 int l_countingsort(lua_State* L) {
     luaL_checktype(L, 1, LUA_TTABLE);
     size_t len = lua_objlen(L,1);
-    int nums[len], out[len];
+    int* nums = malloc(sizeof * nums * len);
+    int* out = malloc(sizeof * nums * len);
     int max = 0;
     for(int i = 0; i <= len-1; i++){
 
@@ -359,11 +369,9 @@ 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];
-
-    for(size_t i = 0; i <= max; i++) count[i] = 0;
+    //int* count = malloc(sizeof *count * (max + 1));
+    int* count = calloc(max + 1, sizeof * count);
+    //for(size_t i = 0; i <= max; i++) count[i] = 0;
 
     for(size_t i = 0; i < len; i++){
       count[nums[i]]++;
@@ -386,6 +394,8 @@ int l_countingsort(lua_State* L) {
     }
     
     free(count);
+    free(nums);
+    free(out);
     return 1;
 }
 
@@ -398,7 +408,7 @@ int i_sorted(double* arr, size_t len){
 int l_miraclesort(lua_State* L) {
     luaL_checktype(L, 1, LUA_TTABLE);
     size_t len = lua_objlen(L,1);
-    double nums[len];
+    double* nums = malloc(sizeof * nums * len);
     for(size_t i = 0; i <= len-1; i++){
 
       lua_pushinteger(L,i+1);
@@ -416,7 +426,8 @@ int l_miraclesort(lua_State* L) {
       lua_pushnumber(L,nums[i]);
       lua_settable(L, -3);
     }
-
+    
+    free(nums);
     return 1;
 }
 
@@ -424,7 +435,7 @@ int l_stalinsort(lua_State* L) {
     luaL_checktype(L, 1, LUA_TTABLE);
     size_t len = lua_objlen(L,1);
     size_t rlen = 0;
-    double nums[len];
+    double* nums = malloc(sizeof * nums * len);
     for(size_t i = 0; i <= len-1; i++){
 
       lua_pushinteger(L,i+1);
@@ -447,6 +458,7 @@ int l_stalinsort(lua_State* L) {
       lua_settable(L, -3);
     }
 
+    free(nums);
     return 1;
 }
 
@@ -468,7 +480,7 @@ void i_slowsort(double* arr, int i, int j){
 int l_slowsort(lua_State* L) {
     luaL_checktype(L, 1, LUA_TTABLE);
     size_t len = lua_objlen(L,1);
-    double nums[len];
+    double* nums = malloc(sizeof * nums * len);
     for(int i = 0; i <= len-1; i++){
 
       lua_pushinteger(L,i+1);
@@ -487,13 +499,14 @@ int l_slowsort(lua_State* L) {
       lua_settable(L, -3);
     }
 
+    free(nums);
     return 1;
 }
 
 int l_bogosort(lua_State* L) {
     luaL_checktype(L, 1, LUA_TTABLE);
     size_t len = lua_objlen(L,1);
-    double nums[len];
+    double* nums = malloc(sizeof * nums * len);
     for(size_t i = 0; i <= len-1; i++){
 
       lua_pushinteger(L,i+1);
@@ -514,5 +527,6 @@ int l_bogosort(lua_State* L) {
       lua_settable(L, -3);
     }
 
+    free(nums);
     return 1;
 }
diff --git a/src/table.h b/src/table.h
index c93bc7d..25c51fa 100644
--- a/src/table.h
+++ b/src/table.h
@@ -18,7 +18,7 @@ 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)
+int l_countingsort(lua_State*); //[int], arr[N] >= 0 -> arr[N] (least -> greatest)
 
 //esoteric sorts
 int l_miraclesort(lua_State*);  //[double+int] -> arr[-∞<=N<=∞] (greatest -> least)
diff --git a/t.lua b/t.lua
index 2e906db..aef5ad1 100644
--- a/t.lua
+++ b/t.lua
@@ -3,8 +3,8 @@ local a = llib.array
 
 local tab = {}
 math.randomseed(os.time())
-for i=1,9999 do
-  table.insert(tab,math.random(1,999));-- + math.random(1,999));
+for i=1,19 do
+  table.insert(tab,math.random(1,99999));-- + math.random(1,999));
 end
 
 print("length of 99999 :\n")
@@ -17,9 +17,9 @@ print("merge sort took "..os.clock()-time.."s")
 time = os.clock()
 local l3 = a.shellsort(tab)
 print("shell sort took "..os.clock()-time.."s")
-time = os.clock()
-local l4 = a.bubblesort(tab)
-print("bubble sort took "..os.clock()-time.."s")
+--time = os.clock()
+--local l4 = a.bubblesort(tab)
+--print("bubble sort took "..os.clock()-time.."s")
 time = os.clock()
 local l5 = a.heapsort(tab)
 print("heap sort took "..os.clock()-time.."s")
@@ -27,14 +27,7 @@ time = os.clock()
 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])
-end
---print(llib.array.greatest(l1))
---local l2 = llib.array.reverse(llib.array.bubblesort(tab))
---[[ aa 
 for l,i in pairs(l1) do
-  print(l1[l].." "..l2[l])
+  print(l1[l].." "..l2[l].." "..l3[l].." "..l5[l].." "..l6[l])
 end
 
-print(table.concat(l1) == table.concat(l2)) ]]--