1 files changed, 34 insertions, 0 deletions
diff --git a/awklib/eg/lib/quicksort.awk b/awklib/eg/lib/quicksort.awk
new file mode 100644
index 00000000..aa67736d
--- /dev/null
+++ b/awklib/eg/lib/quicksort.awk
@@ -0,0 +1,34 @@
+# quicksort.awk --- Quicksort algorithm, with user-supplied
+#                   comparison function
+#
+# Arnold Robbins, arnoldskeeve.com, Public Domain
+# January 2009
+# quicksort --- C.A.R. Hoare's quick sort algorithm. See Wikipedia
+#               or almost any algorithms or computer science text
+#
+# Adapted from K&R-II, page 110
+end ignore
+
+function quicksort(data, left, right, less_than,    i, last)
+{
+    if (left >= right)  # do nothing if array contains fewer
+        return          # than two elements
+
+    quicksort_swap(data, left, int((left + right) / 2))
+    last = left
+    for (i = left + 1; i <= right; i++)
+        if (@less_than(data[i], data[left]))
+            quicksort_swap(data, ++last, i)
+    quicksort_swap(data, left, last)
+    quicksort(data, left, last - 1, less_than)
+    quicksort(data, last + 1, right, less_than)
+}
+
+# quicksort_swap --- helper function for quicksort, should really be inline
+
+function quicksort_swap(data, i, j, temp)
+{
+    temp = data[i]
+    data[i] = data[j]
+    data[j] = temp
+}