sorting the co-ordinates

[nitin1]

actually , I am working on a project and i need to sort the co-ordinates in the increasing y value.

input: 1 2
3 4
5 6
6 6
7 8
4 5

like this, and i need to sort them in the increasing y value.

my approach: i think that i should store them in a struture having memebers x and y and sort them. but problem is i wana do this in nlogn by using quick sort or merge sort. and for quick making the code, i wana use the qsort() function already defined in the C. this function needs a compare() and array which we nned to sort. but problem is that i want to sort the array of structures on the basis of its one member which is y in this case. can you help me a little bit? thanks in advance.

[nitin1]

what is this ? is there any relevenace to the topic ?

[deceptikon]

but problem is i wana do this in nlogn by using quick sort or merge sort. and for quick making the code, i wana use the qsort() function already defined in the C.

Just because it's called qsort() doesn't mean that it's implemented as quicksort. There's no requirement in the C standard that qsort() meet or exceed any time complexity minimum, so a truly horrid implementation could use bubblesort (or even bogosort).

Of course, any reasonable implementation will use an O(nlogn) algorithm, so the lack of a guarantee is mostly just academic. But it's good to be aware of it.

but problem is that i want to sort the array of structures on the basis of its one member which is y in this case.

That's not a problem at all. The comparison function qsort() expects takes two pointers to const void as arguments. All you need to do is cast to the structure type and compare the members:

int compare(const void *a, const void *b)
{
    struct my_struct *pa = a;
    struct my_struct *pb = b;

    if (pa->y == pb->y)
        return 0;

    return pa->y < pb->y ? -1 : +1;
}

[nitin1]

what ? qsort() doesn't mean it is qsort() ? really ? don't it take nlogn time to sort the arrray ? please clearify.

secondly, ** any reasonable implementation will use an O(nlogn) algorithm, so the lack of a guarantee is mostly just academic. But it's good to be aware of it** will you please xplain this line ? thanks in advance.

[deceptikon]

qsort() doesn't mean it is qsort() ?

qsort() is misnamed because it implies quicksort. qsort() could be implemented as heapsort, or mergesort, or bubble sort, or any other sorting algorithm.

will you please xplain this line ?

qsort() is highly likely to be O(nlogn), but there's no hard guarantee in the standard. That's really all it means.

[nitin1]

so , in which case i can't rely on it ? is there any cases in which i must not reply on this function ? thanks for this great info

[deceptikon]

When I said the issue is academic, it means you can always rely on qsort() being reasonably efficient in practice. I'm regretting even mentioning the name being a misnomer now. :(

[nitin1]

why are you regretting now ? what happenned if you have mentioned that ? @deceptikon

[deceptikon]

why are you regretting now ?

Because you latched onto it and that apparently stopped your progress in writing a program until I clarified that it's okay to use qsort(). :P

[nitin1]

don't think this stupid thing ever! it's good to tell something may be that is not asked by me. it's better to tell some important things. and please i feel very low as you saying that you regret after telling me something! I am not so bad, my highness! sometimes, my questions are so bad that you wil laugh but still you must bot regret that. thanks