Thread Rating:
  • 1 Vote(s) - 3 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Stupid Bash Trick: Coding a Sorting Algorithm in Bash
#1
Code:
#!/bin/bash

# Quicksort Implementation in Bash
# Author: Jamie (NGGJamie)
# Function: Sorts an array into alphabetical order. Practical? Not really.
# TODO: Possibly make this not use a static array var?

srt=(one two three four five six seven eight nine ten eleven twelve thirteen fourteen fifteen)

# Compare, return 0 if L > R, 1 if L == R, and 2 if L < R
function compare {
    if [ "$1" \> "$2" ]
    then
        return 0
    elif [ "$1" \< "$2" ]
    then
        return 2
    else
        return 1
    fi
}


# Pick a partition point for the sort
function partition {
    left="$1"
    right="$2"
    x="${srt[$right]}"
    i=$(($left-1))

    for ((j=$left; j<=$(($right-1));j++))
    do
        compare "${srt[$j]}" "$x"
        if [ "$?" -eq "2" ]
        then
            i=$(($i+1))
            buf="${srt[$j]}"
            srt[$j]="${srt[$i]}"
            srt[$i]="$buf"
        fi
    done
    i=$(($i+1))
    buf="${srt[$right]}"
    srt[$right]="${srt[$i]}"
    srt[$i]="$buf"
    return $i
}

# Main loop of the sort
function qsortstr {
    startIndex=0
    endIndex=$((${#srt[@]}-1))
    top=-1
    top=$(($top+1))
    stack[$top]=$startIndex
    top=$(($top+1))
    stack[$top]=$endIndex
    while [ $top -ge 0 ]
    do
        endIndex=${stack[$top]}
        top=$(($top-1))
        startIndex=${stack[$top]}
        top=$(($top-1))
        partition "$startIndex" "$endIndex"
        p="$?"
        if [ $((p-1)) -gt $startIndex ]
        then
            top=$(($top+1))
            stack[$top]=$startIndex
            top=$(($top+1))
            stack[$top]=$(($p-1))
        fi
        if [ $((p+1)) -lt $endIndex ]
        then
            top=$(($top+1))
            stack[$top]=$(($p+1))
            top=$(($top+1))
            stack[$top]=$endIndex
        fi
    done
}


qsortstr

echo "${srt[@]}"

Lately I've been on a binge of trying to port Quicksort into every programming language I can think of as a self-challenge. Tonight, I got the idea to try and see if an implementation would be possible in Bash. Having been somewhat inspired by Joe's recent talks about Bash, and previous mention that it is essentially a programming language itself, I got to work. I'm sure there are a few people around who could optimize this, or even make it take input from the user rather than only have one static var built in. However, that was beyond the scope of my attempt, which was essentially just a proof-of-concept.

The output of the script, once sorted, looks like this: eight eleven fifteen five four fourteen nine one seven six ten thirteen three twelve two


Edit: I just realized I posted this in the wrong section. Feel free to move it.
Reply


Forum Jump:


Users browsing this thread: 1 Guest(s)