Quicksort implemented in shell script doesn't work

Question

I am learning shell scripting and trying to implement quick sort using it. But it doesn't work, actually it acting weird.

The script:

#!/bin/bash

declare -a data=()
declare -r size=10
declare -i steps=0

for i in $(seq 0 $size); do
    data[$i]=$(expr $RANDOM % $size)
done

function partition() {
    pivot=${data[$1]}
    left=$(expr $1 + 1)
    right=$2

    while true; do
        while [[ $left -le $right && ${data[$left]} -le $pivot ]]; do
            left=$(expr $left + 1)
            steps=$(expr $steps + 1)
        done

        while [[ $right -ge $left && ${data[$right]} -ge $pivot ]]; do
            right=$(expr $right - 1)
            steps=$(expr $steps + 1)
        done

        if [[ $left -gt $right ]]; then
            break
        fi

        temp=${data[$left]}
        data[$left]=${data[$right]}
        data[$right]=$temp
    done

    temp=${data[$1]}
    data[$1]=${data[$right]}
    data[$right]=$temp

    echo $right
}

function quickSort() {
    if [[ $1 -lt $2 ]]; then
        local partitionPoint=$(partition $1 $2)
        quickSort $1 $(expr $partitionPoint - 1)
        quickSort $(expr $partitionPoint + 1) $2
    fi
}

# involve the algorithm
quickSort 0 $(expr $size - 1)

echo "Steps: $steps"
echo ${data[@]}

I tried to log some variable but it's just weird I can't figure out what's going on. When I comment out all the code in the two functions and 'manually' update elements of data variable, it did changed. I tried to log some variables and they all changing. But the final output remains untouched. Or maybe it eventually reversed all the flipping but I don't know. I can't figure it out.

At last I compare my python implementation line by line. No mistakes. But it just not working.

Am I miss something?

Variable scope or something?

Any advice will be appreciated.

Answer 1

There are several smaller issues in this code, but the biggest issue is here:

partitionPoint=$(partition $1 $2)

This is problematic because $( ... ) runs ... in a subshell -- a separate, fork()ed-off process, consequently with its own variable scope.

If you instead return your result via indirect assignment, making it:

partition "$1" "$2" partitionPoint

and inside the function using:

printf -v "$3" %s "$right"

...to assign the value to the variable so named, things work much better.

---

#!/bin/bash
PS4=':$LINENO+'; set -x

data=()
size=10
steps=0

for ((i=0; i<size; i++)); do
    data[$i]=$((RANDOM % size))
done

partition() {
    local pivot left right dest temp
    pivot=${data[$1]}
    left=$(($1 + 1))
    right=$2
    dest=$3

    while true; do
        while (( left <= right )) && (( ${data[$left]} <= pivot )); do
            left=$(( left + 1 ))
            steps=$(( steps + 1 ))
        done

        while (( right >= left )) && (( ${data[$right]} >= pivot )); do
            right=$(( right - 1 ))
            steps=$(( steps + 1 ))
        done

        (( left > right )) && break

        temp=${data[$left]}
        data[$left]=${data[$right]}
        data[$right]=$temp
    done

    : '$1='"$1" right="$right" 'data[$1]='"${data[$1]}" 'data[$right]='"${data[$right]}"
    temp=${data[$1]}
    data[$1]=${data[$right]}
    data[$right]=$temp

    printf -v "$dest" %s "$right"
}

quickSort() {
    local partitionPoint
    if (( $1 < $2 )); then
        partition "$1" "$2" partitionPoint
        quickSort "$1" "$(( partitionPoint - 1 ))"
        quickSort "$((partitionPoint + 1))" "$2"
    fi
}

# involve the algorithm
quickSort 0 "$(( size - 1 ))"

echo "Steps: $steps"
printf '%s\n' "${data[@]}"