Hi CNK
Here are a couple of quicksort examples for busybox awk:
# http://www.victor-notes.com/qppro/awk.html
BEGIN { RS = ""; FS = "\n" }
{ A[NR] = $0 }
END {
qsort(A, 1, NR)
for (i = 1; i <= NR; i++) {
print A[i]
if (i == NR) break
print ""
}
}
# QuickSort
# Source: "The AWK Programming Language", by Aho, et.al., p.161
function qsort(A, left, right, i, last) {
if (left >= right)
return
swap(A, left, left+int((right-left+1)*rand()))
last = left
for (i = left+1; i <= right; i++)
if (A[i] < A[left])
swap(A, ++last, i)
swap(A, left, last)
qsort(A, left, last-1)
qsort(A, last+1, right)
}
function swap(A, i, j, t) {
t = A[i]; A[i] = A[j]; A[j] = t
}
Timing:
tc@E310:~/awksort$ time /usr/bin/awk -f quicksort.sh provides-10.x-x86.db > sorted.txt
real 0m 1.74s
user 0m 1.22s
sys 0m 0.52s
And a faster version:
# http://www.victor-notes.com/qppro/awk.html
BEGIN { RS = ""; FS = "\n" }
{ A[NR] = $0 }
END {
qsort(A, 1, NR)
for (i = 1; i <= NR; i++) {
print A[i]
if (i == NR) break
print ""
}
}
# https://community.hpe.com/t5/languages-and-scripting/sort-in-awk-is-very-slow/m-p/2720834#M2904
# qsort expects 3 arguments
# 1 - the array to be sorted
# 2 - the array lower bound (1)
# 3 - the number of elements in the array
# Note : The other arguments are local variables
# and are not passed as parameters
function qsort(arry,lo,hi, i,j,tmp_x,tmp_x2)
{
i = lo + 0
j = hi + 0
tmp_x = arry[int(int(lo + hi) / 2)]
do
{
while (arry[i] < tmp_x) ++i
while (tmp_x < arry[j]) --j
if (i <= j)
{
tmp_x2 = arry[i]
arry[i] = arry[j]
arry[j] = tmp_x2
++i
--j
}
}
while (i <= j)
if (lo < j) qsort(arry,lo,j)
if (i < hi) qsort(arry,i,hi)
return(0)
} # qsort
And timing:
tc@E310:~/awksort$ time /usr/bin/awk -f quicksort2.sh provides-10.x-x86.db > sorted2.txt
real 0m 1.03s
user 0m 0.76s
sys 0m 0.27s