fork(1) download
copy 
  1. #!/bin/bash
  2.  
  3. array1=()
  4. qsort_rec() {
  5.   local left right i j p t
  6.   left=$1
  7.   right=$2
  8.   if [ $left -lt $right ]; then
  9.     i=$left
  10.     j=$right
  11.     p=$(($((${array1[$i]}+${array1[$j]}))/2))
  12.     while :; do
  13.       while [ ${array1[$i]} -lt $p ]; do
  14.         i=$((i+1))
  15.       done
  16.       while [ $p -lt ${array1[$j]} ]; do
  17.         j=$((j-1))
  18.       done
  19.       if [ $i -ge $j ]; then
  20.         break
  21.       fi
  22.       t=${array1[$i]}
  23.       array1[$i]=${array1[$j]}
  24.       array1[$j]=$t
  25.       i=$((i+1))
  26.       j=$((j-1))
  27.     done
  28.     qsort_rec $left $((i-1))
  29.     qsort_rec $((j+1)) $right
  30.   fi
  31. }
  32.  
  33. array2=()
  34. qsort_loop() {
  35.   local left right i j p t stack length pair
  36.   stack=($1 $2)
  37.   length=1
  38.   while [ $length -ne 0 ]; do
  39.     length=$((length-1))
  40.     left=${stack[$((length*2))]}
  41.     right=${stack[$((length*2+1))]}
  42.     stack=("${stack[@]:0:((${#stack[@]}-2))}")
  43.     if [ $left -lt $right ]; then
  44.       i=$left
  45.       j=$right
  46.       p=$(($((${array2[$i]}+${array2[$j]}))/2))
  47.       while :; do
  48.         while [ ${array2[$i]} -lt $p ]; do
  49.           i=$((i+1))
  50.         done
  51.         while [ $p -lt ${array2[$j]} ]; do
  52.           j=$((j-1))
  53.         done
  54.         if [ $i -ge $j ]; then
  55.           break
  56.         fi
  57.         t=${array2[$i]}
  58.         array2[$i]=${array2[$j]}
  59.         array2[$j]=$t
  60.         i=$((i+1))
  61.         j=$((j-1))
  62.       done
  63.       stack+=($left $((i-1)) $((j+1)) $right)
  64.       length=$((length+2))
  65.     fi
  66.   done
  67. }
  68.  
  69. for i in `seq 1 1 1000`; do
  70.   v=$RANDOM
  71.   array1+=($v)
  72.   array2+=($v)
  73. done
  74.  
  75. echo recursive
  76. time qsort_rec 0 $((${#array1[*]}-1))
  77.  
  78. echo
  79.  
  80. echo loop
  81. time qsort_loop 0 $((${#array2[*]}-1))
  82.  
Success #stdin #stdout #stderr 1.38s 5688KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
recursive

loop
stderr
copy 
real	0m0.637s
user	0m0.636s
sys	0m0.000s

real	0m0.723s
user	0m0.720s
sys	0m0.000s
https://ideone.com/b9DfXr
language:
Bash (bash 5.0.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!