home *** CD-ROM | disk | FTP | other *** search
-
-
- # qsort text files
- #
-
- function middle(x,y,z) #return middle of 3
- {
- if ( x <= y )
- { if ( z >= y ) return y
- if ( z < x ) return x
- return z
- }
-
- if ( z >= x ) return x
- if ( z < y ) return y
- return z
- }
-
-
- function isort(A , n, i, j, hold)
- {
- # if needed a sentinal at A[0] will be created
-
- for( i = 2 ; i <= n ; i++)
- {
- hold = A[ j = i ]
- while ( A[j-1] > hold )
- { j-- ; A[j+1] = A[j] }
-
- A[j] = hold
- }
- }
-
-
- # recursive quicksort
- function qsort(A, left, right ,i , j, pivot, hold)
- {
-
- pivot = middle(A[left], A[int((left+right)/2)], A[right])
-
- i = left
- j = right
-
- while ( i <= j )
- {
- while ( A[i] < pivot ) i++
- while ( A[j] > pivot ) j--
-
- if ( i <= j )
- { hold = A[i]
- A[i++] = A[j]
- A[j--] = hold
- }
- }
-
- if ( j - left > BLOCK ) qsort(A,left,j)
- if ( right - i > BLOCK ) qsort(A,i,right)
- }
-
- BEGIN { BLOCK = 5 }
-
-
- { line[NR] = $0 "" # sort as string
- }
-
- END {
-
- if ( NR > BLOCK ) qsort(line, 1, NR)
-
- isort(line, NR)
-
- for(i = 1 ; i <= NR ; i++) print line[i]
- }
-
-
-
-
-
-