Thread: Problems with Quicksort and Pointers

  1. #1
    Registered User
    Join Date
    Apr 2007
    Posts
    6

    Problems with Quicksort and Pointers

    So, here's what's my program is supposed to be doing in a nutshell:

    > First it opens a file, and each time a set of 4 numbers is read (4 numbers representing points of a rectangle) and stored unsorted in a double-linked list, until the file is read.
    > Then the list is sorted using each dimension, so first the x-min, then y-min, x-max and y-max. The original order of the double-list must not be changed, so a list (using only the pointers) for each dimension is created.

    My problem is with the quicksort, I have created a quicksort but it's not working correctly, I've been trying to fix it with debugging but even that is crashing, any help? Currently I am using bubblesort but obviously it is super-slow!

    Any help with the quicksort function please?

    The function is this:
    Code:
    void quickSort(struct nodes *left, struct nodes *right, int which)
    Thanks.

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    I can't see anything obviously wrong. Do you know if it crashes in quicksort itself or the nodeSwap function?

    There is some un-necessarily complex code in nodeSwap:
    Code:
    	if (nt1->x[j]->prev!=NULL)
    		nt1_prev = nt1->x[j]->prev;
    	else nt1_prev = NULL;
    is identical to
    Code:
    	nt1_prev = nt1->x[j]->prev;
    The same sort of code is repeated 4 times.

    I'll have another look at it in a bit.

    --
    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.

  3. #3
    Registered User
    Join Date
    Apr 2007
    Posts
    6
    Yes I have to arrange the swap function, actually I have to re-visit the whole code to optimise it. I think it actually crashes in the swap section because last time I commented the last part and it did not crash (although obviously it didn't work).

    Cheers

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Well, before you optimize it, try to re-arrange the code - I think the entire function can be almost removed, and remaining code will be the final ELSE - but I haven't gone through all the cases yet - it is very complicated for what it does [obviously, you'll still need a few if-statements to fill in the dimHead array, but I think all the other checking for is this or that NULL, is this NT2 or that NT1 can be pretty much eliminated - even if that leads to a few more writes to memory, it will be much shorter code with fewer branches, which should end up running faster.

    Edit: Ah, the lightbulb over my head just went on, and I can see why my suggestion above won't work - although I still think the code is far to complicated, and I'm pretty sure it's possible to reduce the amount of "almost identical but not quite" pieces of code into a more manageble set of code.

    --
    Mats
    Last edited by matsp; 10-10-2007 at 04:48 AM.
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Suggestions on how to better write a quicksort function?
    By shiverbug in forum C Programming
    Replies: 2
    Last Post: 05-12-2009, 02:19 PM
  2. Quicksort problem, now with clear code
    By rvanbeusichem in forum C Programming
    Replies: 1
    Last Post: 11-25-2004, 01:54 PM