qsort.c

基于内容的多媒体数据库检索算法

/*
 * qsort.c
 *
 * utility for sorting!
 *
 * Sat Jan 13 19:34:22 EST 2001
 *
 */


#include "standard.h"




// Bubblesort in increasing order!

void
bubbleSortByIndex(int **sortList, double *value, int nTri)
{
    int i,j,anyChange,temp;

    // bubble sort
    for (i=0; i<nTri; i++) {
        anyChange = _FALSE;
        for (j=0; j<nTri-1; j++) {
            if ( value[(*sortList)[j]] > value[(*sortList)[j+1]] ) {
                // swap sortList value!
                temp             = (*sortList)[j];
                (*sortList)[j]   = (*sortList)[j+1];
                (*sortList)[j+1] = temp;
                anyChange = _TRUE;
            }
        }
        if (anyChange == _FALSE)
            break;
    }
}




/* swap x th element and i th element */

void
mySwap(int *D, double *comp,int x,int i)
{
        int    tempint;
        double tempdouble;

        tempint=D[x];
        D[x]=D[i];
        D[i]=tempint;

        tempdouble = comp[x];
        comp[x]    = comp[i];
        comp[i]    = tempdouble;
}




// Quick sort D[] 
// and the corresponding comp[] in ascending order of
// values of comp[].

void
q_sort(int *D, double *comp, int low,int high, int size)
{
        int pass;
        int highptr=high++;     /* highptr records the last element */

        /* the first element in list is always served as the pivot */
        int pivot=low;

        if(low>=highptr) return;

        do {
                /* find out 1st element value larger than the pivot's */
                pass=1;
                while(pass==1)
                {
                        if(low++<size)
                        {
                                if(comp[low]<comp[pivot])
                                        pass=1;
                                else pass=0;
                        }
                        else pass=0;
                }

                /* find out 1st element value smaller than the pivot's */
                pass=1;
                while(pass==1)
                {
                        if(high-->0)
                        {
                                if(comp[high]>comp[pivot])
                                        pass=1;
                                else pass=0;
                        }
                        else pass=0;
                }

                /* swap elements pointed by low pointer & high pointer */
                if(low<high)
                        mySwap(D, comp, low,high);

        } while(low<=high);

        mySwap(D, comp, pivot,high);


        /* divide list into two for further sorting */
        q_sort(D, comp, pivot, high-1, size);
        q_sort(D, comp, high+1, highptr, size);
}