Bubblesort/Quicksort in AWK

[Mike Sanders]

Well, disappearing (again) for awhile folks. Earnestly appreciate
everyone's patience while I've been bludgeoning the group with all
this code the last few days (dozens of projects I've had laying
around in various states of confusion - chuckle).

At any rate, catch up with you all down the road.
Work hard & make your mother proud =)

# Bubblesort/Quicksort in AWK: Michael Sanders 2024
#
# heads up! gawk already has asort()
#
# see also...
#
# https://en.wikipedia.org/wiki/Bubble_sort
# https://en.wikipedia.org/wiki/Quicksort
#
# setup...
#
# 1. select either bubblesort or quicksort in END{}
# 2. specify column/field to sort data by
# 3. specify sort order 0=A-Z, 1=Z-A
# 4. plugin your data
#
# usage examples...
#
# sort data on 2nd column ascending:
#
# awk -f sort.awk -v COLUMN=2 -v ORDER=0 < old.csv > new.csv
#
# sort data on 3rd column descending:
#
# #!/bin/sh
#
# awk -f sort.awk -v COLUMN=3 -v ORDER=1 <<!
# moe apples 2
# larry oranges 1
# curly bananas 3
# !

BEGIN {
if (!COLUMN) COLUMN = 1 # default column 1
if (ORDER != 0 && ORDER != 1) ORDER = 0 # default order A-Z
}

{
array[NR] = $COLUMN # populate array with specified column
lines[NR] = $0 # store entire line for sorting
}

END {
n = length(array) # get array size
bubble_sort(n, ORDER, COLUMN, array, lines) # call bubble sort
#quick_sort(1, n, ORDER, array, lines) # call quick sort
for (i = 1; i <= n; i++) print lines[i] # print sorted lines
}

function bubble_sort(n, order, column, array, lines, i, j, tmp, tmpLine) {
for (i = 1; i <= n; i++) {
for (j = 1; j <= n - i; j++) {
if ((order == 0 && array[j] > array[j + 1]) ||
(order == 1 && array[j] < array[j + 1])) {
# swap array values
tmp = array[j]
array[j] = array[j + 1]
array[j + 1] = tmp
# swap corresponding lines
tmpLine = lines[j]
lines[j] = lines[j + 1]
lines[j + 1] = tmpLine
}
}
}
}

function quick_sort(left, right, order, array, lines, i, j, tmp, pivot, pivotLine) {
if (left >= right) return
pivot = array[right]
pivotLine = lines[right]
i = left - 1

for (j = left; j < right; j++) {
if ((order == 0 && array[j] <= pivot) ||
(order == 1 && array[j] >= pivot)) {
i++
# swap array values
tmp = array[i]
array[i] = array[j]
array[j] = tmp

# swap corresponding lines
tmpLine = lines[i]
lines[i] = lines[j]
lines[j] = tmpLine
}
}

# place pivot in correct position
i++
array[right] = array[i]
array[i] = pivot
lines[right] = lines[i]
lines[i] = pivotLine

# recursively sort left & right partitions
quick_sort(left, i - 1, order, array, lines)
quick_sort(i + 1, right, order, array, lines)
}

# eof

[Ed Morton]

On 8/23/2024 2:03 PM, Mike Sanders wrote:
<snip>

Post by Mike Sanders
# awk -f sort.awk -v COLUMN=2 -v ORDER=0 < old.csv > new.csv

Don't use all upper-case variable names so they can't clash with builtin
variables now or in future and so it doesn't look like you're using
builtin variables and so obfuscate your code.

Ed.