home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume8 / graph+ / part03 / sort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1987-03-01  |  1.7 KB  |  97 lines
  1. /*
  2.  * Copyright (C) 1986   Alan Kent
  3.  *
  4.  * Permission is granted to freely distribute part or
  5.  * all of this code as long as it is not for profit
  6.  * and this message is retained in the code.
  7.  *
  8.  * No resposibility is taken for any damage or incorect
  9.  * results this program generates.
  10.  * 
  11.  */
  12.  
  13.  
  14. #include <stdio.h>
  15. #include "graph.h"
  16.  
  17.  
  18. table_st *
  19. sort ( table , attr )
  20. table_st *table;
  21. int attr;
  22. {
  23.     int i , j;
  24.     table_st *pcol , *p;
  25.     double min;
  26.     int min_index;
  27.     double temp;
  28.  
  29.     if ( attr < 1 )
  30.     return ( table );
  31.     for ( pcol = table , i = 1; pcol != NULL && i < attr; pcol = pcol->next , i++ );
  32.     if ( pcol == NULL )
  33.     abort ( "SORT by non-existant column" );
  34.  
  35.     /* quick sort */
  36.  
  37.     quick ( table , pcol->data , 0 , table->size - 1 );
  38.  
  39.     return ( table );
  40. }
  41.  
  42.  
  43. static
  44. quick ( table , data , low , high )
  45. table_st *table;
  46. double *data;
  47. int low , high;
  48. {
  49.     int i , j;
  50.     double sample , temp;
  51.     register table_st *p;
  52.  
  53.     if ( low == high )
  54.     return;
  55.     i = low + 1;
  56.     j = high;
  57.     sample = data[ low ];
  58.     while ( i < j ) {
  59.     while ( i < j  &&  data[ i ] <= sample )
  60.         i++;
  61.     while ( j > i  &&  data[ j ] > sample )
  62.         j--;
  63.     
  64.     if ( i < j ) {
  65.  
  66.         /* swap ith and jth entry */
  67.  
  68.         for ( p = table; p != NULL; p = p->next ) {
  69.         temp = p->data[i];
  70.         p->data[i] = p->data[j];
  71.         p->data[j] = temp;
  72.         }
  73.     }
  74.     }
  75.  
  76.     if ( data[i] > sample )
  77.     i--;
  78.     else
  79.     j++;
  80.     if ( data[i] < sample ) {    /* sample is data[low] */
  81.     for ( p = table; p != NULL; p = p->next ) {
  82.         temp = p->data[i];
  83.         p->data[i] = p->data[low];
  84.         p->data[low] = temp;
  85.     }
  86.     }
  87.     i--;
  88.  
  89.     /* sort the new halves of the array */
  90.  
  91.     if ( i > low )
  92.     quick ( table , data , low , i );
  93.     if ( j < high )
  94.     quick ( table , data , j , high );
  95. }
  96.  
  97.