Sorting Algorithm in C with qsort or alternate swap method to sort array of pointers to struct objects

Question

void sort_vector ()
    {
        int i, j;

        for ( i = 0; i < _num_vrsVector; ++i )
        {
            for ( j = i+1; j < _num_vrsVector; ++j )
            {
                if ( _vrsVector[i]->_phase > _vrsVector[j]->_phase ) {
                    swap_vector ( &_vrsVector[i], &_vrsVector[j] );
                }
            }
        }
    }
void swap_vector (struct vrsVector **p, struct vrsVector **q )
{
    struct vrsVector *temp;

    temp = *p;
    *p = *q;
    *q = temp;
}

My question is which method is better to do sorting for an array of pointers to structs object in C. The above code is doing comparison and then do swaping.Another way i know is to use "QSORT".I would like to know that which methods that I just mentioned is better for doing sorting for an array of pointers to objects?

Create an array with 1000000 elements and try the two methods. Then you will find out. — Johan Råde
– Johan Råde, Commented Jul 29, 2013 at 6:10
@DavidSchwartz In term of speed to execute sorting which one is better? And which one would be more safer to use without popping out abnormal error? — user2609443
– user2609443, Commented Jul 29, 2013 at 6:33

LoztInSpace · Accepted Answer · 2013-07-29 06:21:49Z

2

I'd use something from the library unless you need a reason not to. Generally that's a good rule to follow for sorting or anything else. If you find it is not meeting your requirements then find alternatives but your default stance should be "someone else has done this better than I will ever do". (or, if your ego can't take that, "my job is provide X to my business/users. I am in the business of "X", not writing sort routines no matter how good at it I am").

TL;DR: qsort is "the best"

answered Jul 29, 2013 at 6:21

LoztInSpace

5,6971 gold badge17 silver badges29 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Øystein Schønning-Johansen · Accepted Answer · 2013-07-29 09:44:21Z

-1

I would also like to comment your question from an the algorithmic viewpoint. The sorting algorithm using swapping you provide is called bubble sort. The runtime for bubble sort is said to O(n^2). A bit simplified this means that the runtime of the sorting algorithm square if you double the size of the input array.

qsort(), which is the standard C libraries implementation of C.A.R Hoare's or quicksort algorithm has a run time complexity if O(n lg n). This means (a bit simplified) that the runtime will increase runtime n lg n which will save a lot of time when n get big. (As commented, qsort() can be implemented with an other sort algorithm.)

Please note that a quicksort does not always beat a bubble sort just because quicksort O(n lg n) and bubble sort is O(n^2). This is because the O(n^2) real runtime can be less than O(n lg n) for small values of n. However there will always an n that is so big that quicksort will beat bubble sort no matter what.

I recommend a basic book on algorithms, data structures, algorithm design and runtime analysis. Robert Sedgwick has written some good books on the topic. Highly recommended.

edited Jul 29, 2013 at 9:44

answered Jul 29, 2013 at 7:34

Øystein Schønning-Johansen

5481 gold badge8 silver badges17 bronze badges

3 Comments

user4815162342 Over a year ago

Note that the qsort library function is not necessarily an implementation of the quicksort algorithm, it is allowed to use any sorting method, as long as it's no worse than O(n log n). For example, the Linux implementation of qsort uses mergesort.

Øystein Schønning-Johansen Over a year ago

@user4815162342 Interesting comment. Is this stated in WG14? I guess you mean that glibc implementation of qsort uses mergesort. This can actually be useful in the occasions you need a stable sort algorithm. Thanks for the additional information.

user4815162342 Over a year ago

The standard doesn't mandate the use of any particular sorting algorithm, so what glibc does is allowed. But that doesn't mean that you can ever rely on qsort being stable, even if you know that your program will only run under glibc! The use of mergesort is an implementation detail and glibc will happily switch back to quicksort if the array is excessively large or if allocation of the temporary array fails for any reason.

Collectives™ on Stack Overflow

Sorting Algorithm in C with qsort or alternate swap method to sort array of pointers to struct objects

2 Answers 2

Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related