Quicksort Shell Script

   
   Quicksort is a good example of the divide and conquer strategy for
solving problems.  In quicksort,  we divide the array of items to be
sorted into two partitions and then call the quicksort procedure recu-
rsively to sort the two partitions, ie we divide the problem into two
smaller ones and conquer by solving the smaller ones

Quicksort recursive algorithm:

1 Select an element (called as pivot) x(p) of x .
2 Divide x into two batches x1 and x2 so that
  all entries of x1 are < x(p) and
  all entries of x2 are > x(p).
  all entries of x3 are == x(p)
  for each recursive call x3 will be placed to its sorted position.
  To finish sorting we must sort x1 and x2.
3 Apply steps 1 and 2 again to each of x1
  and x2, using further subdivision.
4 Repeat (recursively) until the sets to be
  sorted have no more than one element.

#!/bin/bash
# SCRIPT : quicksort.sh
# USAGE  : quicksort.sh
# PURPOSE: Sorts the list using quicksort algorithm.
#                         \\\\ ////
#                         \\ - - //
#                            @ @
#                    ---oOOo-( )-oOOo---
#
#####################################################################
#                      Define Functions Here                        #
#####################################################################

printnumbers()
{
   echo ${ARRAY[*]}
}

sortnumbers()
{

    local array=( `echo "$@"` )
    local -a l
    local -a g
    local -a e
    local x=

    if [ ${#array[@]} -lt 2 ]; then
        echo -n ${array[@]}
    else
        local pivot=${array[0]}

        for x in ${array[@]}
        do

          if [ $x -lt $pivot ]
          then
              l=( ${l[@]} $x )
          elif [ $x -gt $pivot ]
          then
              g=( ${g[@]} $x )
          else
              e=(${e[@]} $x)
          fi

        done

      echo "`sortnumbers "${l[@]}"` ${e[@]} `sortnumbers "${g[@]}"`"

    fi
}

#####################################################################
#                       Variable Declaration                       #
#####################################################################

clear

echo "Enter Numbers to be Sorted : "

read -a ARRAY

count=${#ARRAY[@]}

#####################################################################
#                       Main Script Starts Here                     #
#####################################################################

echo "--------------------------------------------------------------"

echo "Numbers Before Sort:"

printnumbers

echo "Numbers After Sort: "

sortnumbers "${ARRAY[@]}"

echo "--------------------------------------------------------------"


OUTPUT:

[venu@localhost shell]$ sh quicksort.sh
Enter Numbers to be Sorted :
12 54 32 90 76 54 -11 5 0 222 -46 32 -8 33 87 21 84 321 9
---------------------------------------------------------------
Numbers Before Sort:
12 54 32 90 76 54 -11 5 0 222 -46 32 -8 33 87 21 84 321 9
Numbers After Sort:
-46 -11 -8 0  5 9 12 21 32 32 33 54 54  76 84 87  90  222 321
---------------------------------------------------------------