Add Lua code for chapter 4

zhangjiongwx · egonSchiele · commit 5f2626c91b2f · 2017-08-27T14:25:58.000-04:00
diff --git a/04_quicksort/lua/01_loop_sum.lua b/04_quicksort/lua/01_loop_sum.lua
@@ -0,0 +1,11 @@
+function sum(array)
+    local total = 0
+    
+    for _, value in pairs(array) do
+        total = total + value
+    end
+    
+    return total
+end
+
+print(sum({1, 2, 3, 4})) -- => 10
diff --git a/04_quicksort/lua/02_recursive_sum.lua b/04_quicksort/lua/02_recursive_sum.lua
@@ -0,0 +1,9 @@
+function sum(array)
+    if next(array) == nil then
+        return 0;
+    end
+    
+    return array[1] + sum(table.move(array, 2, #array, 1, {}))
+end
+
+print(sum({1, 2, 3, 4})) -- => 10
diff --git a/04_quicksort/lua/03_recursive_count.lua b/04_quicksort/lua/03_recursive_count.lua
@@ -0,0 +1,9 @@
+function count(array)
+    if next(array) == nil then
+        return 0
+    end
+    
+    return 1 + count(table.move(array, 2, #array, 1, {}))
+end
+
+print(count({1, 2, 3, 4})) -- => 4
diff --git a/04_quicksort/lua/04_recursive_max.lua b/04_quicksort/lua/04_recursive_max.lua
@@ -0,0 +1,14 @@
+function max(array)
+    if next(array) == nil then
+        return nil
+    elseif #array == 1 then
+        return array[1]
+    elseif #array == 2 then
+        return array[1] > array[2] and array[1] or array[2]
+    end
+    
+    local sub_max = max(table.move(array, 2, #array, 1, {}))
+    return array[1] > sub_max and array[1] or sub_max
+end
+
+print(max({1, 2, 3, 4})) -- => 4
diff --git a/04_quicksort/lua/05_quicksort.lua b/04_quicksort/lua/05_quicksort.lua
@@ -0,0 +1,30 @@
+function concat(array1, array2)
+    for _, value in pairs(array2) do
+        table.insert(array1, value)
+    end
+    
+    return array1
+end
+
+function quicksort(array)
+    if #array < 2 then
+        -- base case, arrays with 0 or 1 element are already "sorted"
+        return array
+    else
+        -- recursive case
+        local pivot = array[1]
+        local less, greater = {}, {}
+
+        for i = 2, #array do
+            if array[i] <= pivot then
+                table.insert(less, array[i])
+            else
+                table.insert(greater, array[i])
+            end
+        end
+        
+        return concat(quicksort(less), concat({pivot}, quicksort(greater)))
+    end
+end
+
+print(table.concat(quicksort({10, 5, 2, 3}), ", "))
