diff options
author | sharkdp <davidpeter@web.de> | 2020-09-14 10:43:44 +0200 |
---|---|---|
committer | David Peter <sharkdp@users.noreply.github.com> | 2020-09-30 19:50:19 +0200 |
commit | c9237cccab7c86c246fc435aaa151729754045ff (patch) | |
tree | 6e5ac6ccffb31b7bebd0e7845cad9b839d06ad0d | |
parent | 02cd68db3788775ee3fb45054cf6576c145f1d2a (diff) |
Add AWK file for syntax tests
-rw-r--r-- | tests/syntax-tests/highlighted/AWK/quicksort.awk | 35 | ||||
-rw-r--r-- | tests/syntax-tests/source/AWK/quicksort.awk | 35 |
2 files changed, 70 insertions, 0 deletions
diff --git a/tests/syntax-tests/highlighted/AWK/quicksort.awk b/tests/syntax-tests/highlighted/AWK/quicksort.awk new file mode 100644 index 00000000..66e8df97 --- /dev/null +++ b/tests/syntax-tests/highlighted/AWK/quicksort.awk @@ -0,0 +1,35 @@ +[38;2;117;113;94m#[0m[38;2;117;113;94m quicksort.awk --- Quicksort algorithm, with user-supplied[0m +[38;2;117;113;94m#[0m[38;2;117;113;94m comparison function[0m +[38;2;117;113;94m#[0m +[38;2;117;113;94m#[0m[38;2;117;113;94m Arnold Robbins, arnold@skeeve.com, Public Domain[0m +[38;2;117;113;94m#[0m[38;2;117;113;94m January 2009[0m + + +[38;2;117;113;94m#[0m[38;2;117;113;94m quicksort --- C.A.R. Hoare's quicksort algorithm. See Wikipedia[0m +[38;2;117;113;94m#[0m[38;2;117;113;94m or almost any algorithms or computer science text.[0m +[38;2;117;113;94m#[0m +[38;2;117;113;94m#[0m[38;2;117;113;94m Adapted from K&R-II, page 110[0m + +[3;38;2;102;217;239mfunction[0m[38;2;248;248;242m [0m[38;2;166;226;46mquicksort[0m[38;2;248;248;242m([0m[3;38;2;253;151;31mdata[0m[38;2;248;248;242m, [0m[3;38;2;253;151;31mleft[0m[38;2;248;248;242m, [0m[3;38;2;253;151;31mright[0m[38;2;248;248;242m, [0m[3;38;2;253;151;31mless_than[0m[38;2;248;248;242m, [0m[3;38;2;253;151;31mi[0m[38;2;248;248;242m, [0m[3;38;2;253;151;31mlast[0m[38;2;248;248;242m)[0m +[38;2;248;248;242m{[0m +[38;2;248;248;242m [0m[38;2;249;38;114mif[0m[38;2;248;248;242m [0m[38;2;255;255;255m([0m[38;2;255;255;255mleft[0m[38;2;248;248;242m [0m[38;2;249;38;114m>=[0m[38;2;248;248;242m [0m[38;2;255;255;255mright[0m[38;2;255;255;255m)[0m[38;2;248;248;242m [0m[38;2;117;113;94m#[0m[38;2;117;113;94m do nothing if array contains fewer[0m +[38;2;248;248;242m [0m[38;2;255;255;255mreturn[0m[38;2;248;248;242m [0m[38;2;117;113;94m#[0m[38;2;117;113;94m than two elements[0m + +[38;2;248;248;242m [0m[38;2;166;226;46mquicksort_swap[0m[38;2;255;255;255m([0m[38;2;255;255;255mdata[0m[38;2;248;248;242m,[0m[38;2;248;248;242m [0m[38;2;255;255;255mleft[0m[38;2;248;248;242m,[0m[38;2;248;248;242m [0m[38;2;102;217;239mint[0m[38;2;255;255;255m([0m[38;2;255;255;255m([0m[38;2;255;255;255mleft[0m[38;2;248;248;242m [0m[38;2;249;38;114m+[0m[38;2;248;248;242m [0m[38;2;255;255;255mright[0m[38;2;255;255;255m)[0m[38;2;248;248;242m [0m[38;2;249;38;114m/[0m[38;2;248;248;242m [0m[38;2;190;132;255m2[0m[38;2;255;255;255m)[0m[38;2;255;255;255m)[0m +[38;2;248;248;242m [0m[38;2;255;255;255mlast[0m[38;2;248;248;242m [0m[38;2;249;38;114m=[0m[38;2;248;248;242m [0m[38;2;255;255;255mleft[0m +[38;2;248;248;242m [0m[38;2;166;226;46mfor[0m[38;2;248;248;242m [0m[38;2;255;255;255m([0m[38;2;255;255;255mi[0m[38;2;248;248;242m [0m[38;2;249;38;114m=[0m[38;2;248;248;242m [0m[38;2;255;255;255mleft[0m[38;2;248;248;242m [0m[38;2;249;38;114m+[0m[38;2;248;248;242m [0m[38;2;190;132;255m1[0m[38;2;248;248;242m; [0m[38;2;255;255;255mi[0m[38;2;248;248;242m [0m[38;2;249;38;114m<=[0m[38;2;248;248;242m [0m[38;2;255;255;255mright[0m[38;2;248;248;242m; [0m[38;2;255;255;255mi[0m[38;2;249;38;114m++[0m[38;2;255;255;255m)[0m +[38;2;248;248;242m [0m[38;2;166;226;46mif[0m[38;2;248;248;242m [0m[38;2;255;255;255m([0m[38;2;248;248;242m@[0m[38;2;166;226;46mless_than[0m[38;2;255;255;255m([0m[38;2;255;255;255mdata[0m[38;2;249;38;114m[[0m[38;2;255;255;255mi[0m[38;2;249;38;114m][0m[38;2;248;248;242m,[0m[38;2;248;248;242m [0m[38;2;255;255;255mdata[0m[38;2;249;38;114m[[0m[38;2;255;255;255mleft[0m[38;2;249;38;114m][0m[38;2;255;255;255m)[0m[38;2;255;255;255m)[0m +[38;2;248;248;242m [0m[38;2;166;226;46mquicksort_swap[0m[38;2;255;255;255m([0m[38;2;255;255;255mdata[0m[38;2;248;248;242m,[0m[38;2;248;248;242m [0m[38;2;249;38;114m+[0m[38;2;249;38;114m+[0m[38;2;255;255;255mlast[0m[38;2;248;248;242m,[0m[38;2;248;248;242m [0m[38;2;255;255;255mi[0m[38;2;255;255;255m)[0m +[38;2;248;248;242m [0m[38;2;166;226;46mquicksort_swap[0m[38;2;255;255;255m([0m[38;2;255;255;255mdata[0m[38;2;248;248;242m,[0m[38;2;248;248;242m [0m[38;2;255;255;255mleft[0m[38;2;248;248;242m,[0m[38;2;248;248;242m [0m[38;2;255;255;255mlast[0m[38;2;255;255;255m)[0m +[38;2;248;248;242m [0m[38;2;166;226;46mquicksort[0m[38;2;255;255;255m([0m[38;2;255;255;255mdata[0m[38;2;248;248;242m,[0m[38;2;248;248;242m [0m[38;2;255;255;255mleft[0m[38;2;248;248;242m,[0m[38;2;248;248;242m [0m[38;2;255;255;255mlast[0m[38;2;248;248;242m [0m[38;2;249;38;114m-[0m[38;2;248;248;242m [0m[38;2;190;132;255m1[0m[38;2;248;248;242m,[0m[38;2;248;248;242m [0m[38;2;255;255;255mless_than[0m[38;2;255;255;255m)[0m +[38;2;248;248;242m [0m[38;2;166;226;46mquicksort[0m[38;2;255;255;255m([0m[38;2;255;255;255mdata[0m[38;2;248;248;242m,[0m[38;2;248;248;242m [0m[38;2;255;255;255mlast[0m[38;2;248;248;242m [0m[38;2;249;38;114m+[0m[38;2;248;248;242m [0m[38;2;190;132;255m1[0m[38;2;248;248;242m,[0m[38;2;248;248;242m [0m[38;2;255;255;255mright[0m[38;2;248;248;242m,[0m[38;2;248;248;242m [0m[38;2;255;255;255mless_than[0m[38;2;255;255;255m)[0m +[38;2;248;248;242m}[0m + +[38;2;117;113;94m#[0m[38;2;117;113;94m quicksort_swap --- helper function for quicksort, should really be inline[0m + +[3;38;2;102;217;239mfunction[0m[38;2;248;248;242m [0m[38;2;166;226;46mquicksort_swap[0m[38;2;248;248;242m([0m[3;38;2;253;151;31mdata[0m[38;2;248;248;242m, [0m[3;38;2;253;151;31mi[0m[38;2;248;248;242m, [0m[3;38;2;253;151;31mj[0m[38;2;248;248;242m, [0m[3;38;2;253;151;31mtemp[0m[38;2;248;248;242m)[0m +[38;2;248;248;242m{[0m +[38;2;248;248;242m [0m[38;2;255;255;255mtemp[0m[38;2;248;248;242m [0m[38;2;249;38;114m=[0m[38;2;248;248;242m [0m[38;2;255;255;255mdata[0m[38;2;249;38;114m[[0m[38;2;255;255;255mi[0m[38;2;249;38;114m][0m +[38;2;248;248;242m [0m[38;2;255;255;255mdata[0m[38;2;249;38;114m[[0m[38;2;255;255;255mi[0m[38;2;249;38;114m][0m[38;2;248;248;242m = [0m[38;2;255;255;255mdata[0m[38;2;249;38;114m[[0m[38;2;255;255;255mj[0m[38;2;249;38;114m][0m +[38;2;248;248;242m [0m[38;2;255;255;255mdata[0m[38;2;249;38;114m[[0m[38;2;255;255;255mj[0m[38;2;249;38;114m][0m[38;2;248;248;242m = [0m[38;2;255;255;255mtemp[0m +[38;2;248;248;242m}[0m diff --git a/tests/syntax-tests/source/AWK/quicksort.awk b/tests/syntax-tests/source/AWK/quicksort.awk new file mode 100644 index 00000000..e0ed8bc7 --- /dev/null +++ b/tests/syntax-tests/source/AWK/quicksort.awk @@ -0,0 +1,35 @@ +# quicksort.awk --- Quicksort algorithm, with user-supplied +# comparison function +# +# Arnold Robbins, arnold@skeeve.com, Public Domain +# January 2009 + + +# quicksort --- C.A.R. Hoare's quicksort algorithm. See Wikipedia +# or almost any algorithms or computer science text. +# +# Adapted from K&R-II, page 110 + +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 +} |