qsort question

This is a discussion on qsort question within the C Programming forums, part of the General Programming Boards category; Hello all - Is there any way to pass a parameter to the comparison function with qsort without using a ...

  1. #1
    Registered User
    Join Date
    Apr 2009
    Posts
    5

    qsort question

    Hello all -

    Is there any way to pass a parameter to the comparison function with qsort without using a global variable?

    My goal is to sort the rows of a 2-D matrix based on a particular column. I have a working version that does use globals:
    Code:
    static int nSortColumn = 0; /* global column index used by sortrows */
    void sortrows(double** pMatrix,int nStartRow, int nStopRow, int nColumn)
    {
    	nSortColumn = nColumn;
    	qsort((void*) (pMatrix+nStartRow),nStopRow-nStartRow+1,sizeof(double*),&sortrowsCompareFcn);
    }
    
    int sortrowsCompareFcn(const void * a,const void * b)
    {
    	double** val1 = (double**) a;
    	double** val2 = (double**) b;
    
    	if(val1[0][nSortColumn] < val2[0][nSortColumn]  )
    	{
    		return -1;
    	}
    	else if(val1[0][nSortColumn] > val2[0][nSortColumn]  )
    	{
    		return 1;
    	}
    	else
    	{
    		return 0;
    	}
    }
    Is a better way to tell the comparison function which column to sort by?

    Thanks!

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,295
    Quote Originally Posted by Hops View Post
    Is [there] a better way to tell the comparison function which column to sort by?
    In C? Nope not really, assuming you're not willing to make one comparison function for each possible sort column, or store a pointer to the sort column in the matrix itself.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    For small numbers of sorting, it could be done pretty easily this way:
    Code:
    inline int sortrowsCompareFcn(const void * a,const void * b, int nSortColumn)
    {
    	double** val1 = (double**) a;
    	double** val2 = (double**) b;
    
    	if(val1[0][nSortColumn] < val2[0][nSortColumn]  )
    	{
    		return -1;
    	}
    	else if(val1[0][nSortColumn] > val2[0][nSortColumn]  )
    	{
    		return 1;
    	}
    	else
    	{
    		return 0;
    	}
    }
    
    #define SORTNAME(n) sortrowsCompareFcn##n
    #define SORTN(n) int SORTNAME(n)(const void * a,const void * b) { sortrowsCompareFcn(a, b, n); }
    
    SORTN(0)
    SORTN(1)
    SORTN(2)
    SORTN(3)
    SORTN(4)
    SORTN(5)
    SORTN(6)
    SORTN(7)
    SORTN(8)
    SORTN(9)
    SORTN(10)
    
    typedef int (*SortFunc)(void *a, void *b);
    SortFunc sortFunctions[11] = {
       SORTNAME(0),
       SORTNAME(1),
       SORTNAME(2),
       SORTNAME(3),
       SORTNAME(4),
       SORTNAME(5),
       SORTNAME(6),
       SORTNAME(7),
       SORTNAME(8),
       SORTNAME(9),
       SORTNAME(10),
    }
    
    void sortrows(double** pMatrix,int nStartRow, int nStopRow, int nColumn)
    {
    	qsort((void*) (pMatrix+nStartRow),nStopRow-nStartRow+1,sizeof(double*), sortFunctions[n]);
    }
    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  4. #4
    Registered User
    Join Date
    Apr 2009
    Posts
    5
    Quote Originally Posted by iMalc View Post
    In C? Nope not really, assuming you're not willing to make one comparison function for each possible sort column, or store a pointer to the sort column in the matrix itself.
    How would one store a pointer in the matrix itself? Does that mean that I would need a copy of the pointer for each row of the matrix?

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Hops View Post
    How would one store a pointer in the matrix itself? Does that mean that I would need a copy of the pointer for each row of the matrix?
    I don't know what iMalc was trying to say, but whatever it was, I'm sure it would require some change to your datastructure itself.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,295
    Quote Originally Posted by matsp View Post
    I don't know what iMalc was trying to say, but whatever it was, I'm sure it would require some change to your datastructure itself.

    --
    Mats
    Yes, the data structure would have to be changed to some struct instead of just a double**. Of course being C you lose the ability to use the [] operator then. Or you could be really evil and cast the pointer to a double or something horrid.

    I had thought of the array of function pointers, but hadn't thought of the macro trickery to make it easier to produce the array of them.

    By the way, I just thought of another trick that will do it:
    Code:
    void sortrows(double** pMatrix,int nStartRow, int nStopRow, int nColumn)
    {
    	sortrowsCompareFcn(NULL, &nColumn);  // Set up our sort column.
    	qsort((void*) (pMatrix+nStartRow), nStopRow-nStartRow+1, sizeof(double*), &sortrowsCompareFcn);
    }
    
    int sortrowsCompareFcn(const void * a, const void * b)
    {
    	static int nSortColumn= 0;
    	if (a == NULL)
    	{
    		nSortColumn = *(int*)b;
    		return 0;
    	}
    
    	double** val1 = (double**) a;
    	double** val2 = (double**) b;
    
    	if (val1[0][nSortColumn] < val2[0][nSortColumn])
    		return -1;
    	if (val1[0][nSortColumn] > val2[0][nSortColumn])
    		return 1;
    	return 0;
    }
    static != global
    This works since the params can never be NULL during the sort.

    So yeah I take back what I said about it not being possible.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. An interesting problem of qsort()
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 03-05-2008, 11:09 AM
  2. C++ link error with qsort
    By bvnorth in forum C++ Programming
    Replies: 7
    Last Post: 10-24-2003, 02:22 AM
  3. Question...
    By TechWins in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 07-28-2003, 09:47 PM
  4. Replies: 7
    Last Post: 04-13-2003, 10:53 PM
  5. opengl DC question
    By SAMSAM in forum Game Programming
    Replies: 6
    Last Post: 02-26-2003, 08:22 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21