examples/qsort.awk

   1 #!/usr/bin/mawk -f
   2
   3 # qsort text files
   4 #
   5
   6 function middle(x,y,z)  #return middle of 3
   7 {
   8   if ( x <= y )
   9   { if ( z >= y )  return y
  10     if ( z <  x )  return x
  11     return z
  12   }
  13
  14   if ( z >= x )  return x
  15   if ( z <  y )  return y
  16   return z
  17 }
  18
  19
  20 function  isort(A , n,    i, j, hold)
  21 {
  22   # if needed a sentinal at A[0] will be created
  23
  24   for( i = 2 ; i <= n ; i++)
  25   {
  26     hold = A[ j = i ]
  27     while ( A[j-1] > hold )
  28     { j-- ; A[j+1] = A[j] }
  29
  30     A[j] = hold
  31   }
  32 }
  33
  34
  35 # recursive quicksort
  36 function  qsort(A, left, right    ,i , j, pivot, hold)
  37 {
  38
  39   pivot = middle(A[left], A[int((left+right)/2)], A[right])
  40
  41   i = left
  42   j = right
  43
  44   while ( i <= j )
  45   {
  46     while ( A[i] < pivot )  i++
  47     while ( A[j] > pivot )  j--
  48
  49     if ( i <= j )
  50     { hold = A[i]
  51       A[i++] = A[j]
  52       A[j--] = hold
  53     }
  54   }
  55
  56   if ( j - left > BLOCK )  qsort(A,left,j)
  57   if ( right - i > BLOCK )  qsort(A,i,right)
  58 }
  59
  60 BEGIN { BLOCK = 5 }
  61
  62
  63 { line[NR] = $0 ""   # sort as string
  64 }
  65
  66 END  {
  67
  68   if ( NR > BLOCK )  qsort(line, 1, NR)
  69
  70   isort(line, NR)
  71
  72   for(i = 1 ; i <= NR ; i++) print line[i]
  73 }
  74
  75
  76
  77
  78