fork 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 < right )); then
  9.     i=$left
  10.     j=$right
  11.     p=$(( (${array1[$i]} + ${array1[$j]}) / 2 ))
  12.     while :; do
  13.       while (( ${array1[$i]} < p )); do
  14.         i=$((i+1))
  15.       done
  16.       while (( p < ${array1[$j]} )); do
  17.         j=$((j-1))
  18.       done
  19.       (( i >= j )) && break
  20.       t=${array1[$i]}
  21.       array1[$i]=${array1[$j]}
  22.       array1[$j]=$t
  23.       i=$((i+1))
  24.       j=$((j-1))
  25.     done
  26.     qsort_rec $left $((i-1))
  27.     qsort_rec $((j+1)) $right
  28.   fi
  29. }
  30.  
  31. array2=()
  32. qsort_loop() {
  33.   local left right i j p t sp left_stack right_stack
  34.  
  35.   left=$(($1))
  36.   right=$(($2))
  37.   sp=0
  38.  
  39.   while :; do
  40.     if (( right <= left )); then
  41.       (( ! sp )) && break
  42.       sp=$((sp-1))
  43.       left=${left_stack[$sp]}
  44.       right=${right_stack[$sp]}
  45.     else
  46.       i=$left
  47.       j=$right
  48.       p=${array2[$(( (left + right) / 2 ))]}
  49.       while :; do
  50.         while (( ${array2[$i]} < p )); do
  51.           i=$((i+1))
  52.         done
  53.         while (( ${array2[$j]} > p )); do
  54.           j=$((j-1))
  55.         done
  56.         (( i >= j )) && break
  57.         t=${array2[$i]}
  58.         array2[$i]=${array2[$j]}
  59.         array2[$j]=$t
  60.         i=$((i+1))
  61.         j=$((j-1))
  62.       done
  63.  
  64.       if (( i - left < right - j )); then
  65.         left_stack[$sp]=$left
  66.         right_stack[$sp]=$((i-1))
  67.         sp=$((sp+1))
  68.         left=$((j+1))
  69.       else
  70.         left_stack[$sp]=$((j+1))
  71.         right_stack[$sp]=$right
  72.         sp=$((sp+1))
  73.         right=$((i-1))
  74.       fi
  75.     fi
  76.   done
  77. }
  78.  
  79. for i in {1..1000}; do
  80.   v=$RANDOM
  81.   array1+=($v)
  82.   array2+=($v)
  83. done
  84.  
  85. #echo "${array1[@]}"
  86.  
  87. echo recursive
  88. time qsort_rec 0 $((${#array1[*]}-1))
  89.  
  90. echo
  91.  
  92. echo loop
  93. time qsort_loop 0 $((${#array2[*]}-1))
  94.  
  95. #echo "${array1[@]}"
  96. #echo "${array2[@]}"
  97.  
Success #stdin #stdout #stderr 1s 5652KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
recursive

loop
stderr
copy 
real	0m0.550s
user	0m0.548s
sys	0m0.000s

real	0m0.439s
user	0m0.436s
sys	0m0.000s
https://ideone.com/KmmnH7
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!