DataMuseum.dk

top - download

    Length: 1757 (0x6dd)
    Types: TextFile
    Names: »sort.c«

└─⟦a0efdde77⟧ Bits:30001252 EUUGD11 Tape, 1987 Spring Conference Helsinki
    └─ ⟦this⟧ »EUUGD11/euug-87hel/sec1/graph/sort.c« 

TextFile

/*
 * Copyright (C) 1986   Alan Kent
 *
 * Permission is granted to freely distribute part or
 * all of this code as long as it is not for profit
 * and this message is retained in the code.
 *
 * No resposibility is taken for any damage or incorect
 * results this program generates.
 * 
 */


#include <stdio.h>
#include "graph.h"


table_st *
sort ( table , attr )
table_st *table;
int attr;
{
    int i , j;
    table_st *pcol , *p;
    double min;
    int min_index;
    double temp;

    if ( attr < 1 )
	return ( table );
    for ( pcol = table , i = 1; pcol != NULL && i < attr; pcol = pcol->next , i++ );
    if ( pcol == NULL )
	abort ( "SORT by non-existant column" );

    /* quick sort */

    quick ( table , pcol->data , 0 , table->size - 1 );

    return ( table );
}


static
quick ( table , data , low , high )
table_st *table;
double *data;
int low , high;
{
    int i , j;
    double sample , temp;
    register table_st *p;

    if ( low == high )
	return;
    i = low + 1;
    j = high;
    sample = data[ low ];
    while ( i < j ) {
	while ( i < j  &&  data[ i ] <= sample )
	    i++;
	while ( j > i  &&  data[ j ] > sample )
	    j--;
	
	if ( i < j ) {

	    /* swap ith and jth entry */

	    for ( p = table; p != NULL; p = p->next ) {
		temp = p->data[i];
		p->data[i] = p->data[j];
		p->data[j] = temp;
	    }
	}
    }

    if ( data[i] > sample )
	i--;
    else
	j++;
    if ( data[i] < sample ) {	/* sample is data[low] */
	for ( p = table; p != NULL; p = p->next ) {
	    temp = p->data[i];
	    p->data[i] = p->data[low];
	    p->data[low] = temp;
	}
    }
    i--;

    /* sort the new halves of the array */

    if ( i > low )
	quick ( table , data , low , i );
    if ( j < high )
	quick ( table , data , j , high );
}