adding quick sort to bash

Shehani009 · Oct 14, 2019 · 2318f87 · 2318f87
1 parent dd8b2d9
commit 2318f87
Show file tree

Hide file tree

Showing 2 changed files with 45 additions and 0 deletions.
diff --git a/archive/b/bash/README.md b/archive/b/bash/README.md
@@ -16,6 +16,7 @@ Welcome to Sample Programs in Bash!
 - [Hello World in Bash][2]
 - [Reverse String in Bash][3]
 - [ROT13 in Bash][11]
+- [Quick Sort in Bash][14]
 
 ## Fun Facts
 
@@ -39,3 +40,4 @@ Welcome to Sample Programs in Bash!
 [11]: https://github.com/TheRenegadeCoder/sample-programs/issues/1231
 [12]: https://www.log2base2.com/shell-script-examples/loop/shell-script-to-find-factorial-of-a-number.html
 [13]: https://github.com/TheRenegadeCoder/sample-programs/issues/1219
+[14]: https://github.com/TheRenegadeCoder/sample-programs/issues/1228
diff --git a/archive/b/bash/quicksort.sh b/archive/b/bash/quicksort.sh
@@ -0,0 +1,43 @@
+#!/bin/bash
+
+# based on https://stackoverflow.com/questions/7442417/how-to-sort-an-array-in-bash
+
+# quicksorts positional arguments
+# return is in array qsort_ret
+# Note: iterative, NOT recursive! :)
+# First argument is a function name that takes two arguments and compares them
+qsort_iter() {
+   (($#<=1)) && return 0
+   local compare_fun=$1
+   shift
+   local stack=( 0 $(($#-1)) ) beg end i pivot smaller larger
+   qsort_ret=("$@")
+   while ((${#stack[@]})); do
+      beg=${stack[0]}
+      end=${stack[1]}
+      stack=( "${stack[@]:2}" )
+      smaller=() larger=()
+      pivot=${qsort_ret[beg]}
+      for ((i=beg+1;i<=end;++i)); do
+         if "$compare_fun" "${qsort_ret[i]}" "$pivot"; then
+            smaller+=( "${qsort_ret[i]}" )
+         else
+            larger+=( "${qsort_ret[i]}" )
+         fi
+      done
+      qsort_ret=( "${qsort_ret[@]:0:beg}" "${smaller[@]}" "$pivot" "${larger[@]}" "${qsort_ret[@]:end+1}" )
+      if ((${#smaller[@]}>=2)); then stack+=( "$beg" "$((beg+${#smaller[@]}-1))" ); fi
+      if ((${#larger[@]}>=2)); then stack+=( "$((end-${#larger[@]}+1))" "$end" ); fi
+   done
+}
+
+# compare function
+compare_str() { [[ $1 < $2 ]]; }
+
+# main
+array=( "$@" )
+qsort_iter compare_str "${array[@]}"
+echo "${qsort_ret[@]}"
+
+# example run:
+#  quicksort.sh 5 4 3 2 1 4 4