git.iko.soy/bat
on bce304a help sign in
bat/tests/syntax-tests/source/AWK/quicksort.awk
35 lines 1.0 kB history raw
1# quicksort.awk --- Quicksort algorithm, with user-supplied
2# comparison function
3#
4# Arnold Robbins, arnold@skeeve.com, Public Domain
5# January 2009
8# quicksort --- C.A.R. Hoare's quicksort algorithm. See Wikipedia
9# or almost any algorithms or computer science text.
11# Adapted from K&R-II, page 110
13function quicksort(data, left, right, less_than, i, last)
15 if (left >= right) # do nothing if array contains fewer
16 return # than two elements
18 quicksort_swap(data, left, int((left + right) / 2))
19 last = left
20 for (i = left + 1; i <= right; i++)
21 if (@less_than(data[i], data[left]))
22 quicksort_swap(data, ++last, i)
23 quicksort_swap(data, left, last)
24 quicksort(data, left, last - 1, less_than)
25 quicksort(data, last + 1, right, less_than)
28# quicksort_swap --- helper function for quicksort, should really be inline
30function quicksort_swap(data, i, j, temp)
32 temp = data[i]
33 data[i] = data[j]
34 data[j] = temp