46

Which is the best sorting technique to sort the following array and if there are duplicates how to handle them:

int a= {1,3,6,7,1,2};

Also which is the best sorting technique of all?

void BubbleSort(int a[], int array_size)
{
    int i, j, temp;
    for (i = 0; i < (array_size - 1); ++i)
    {
        for (j = 0; j < array_size - 1 - i; ++j )
        {
            if (a[j] > a[j+1])
            {
                temp = a[j+1];
                a[j+1] = a[j];
                a[j] = temp;
            }
        }
    }
}
Improve this question
9
  • 1
    See: en.wikipedia.org/wiki/Sorting_algorithm Commented Oct 8, 2010 at 20:13
  • 3
    There is no "best sorting technique of all", it depends on the size of your data and if it is somewhat sorted at the beginning. I'd suggest you to read en.wikipedia.org/wiki/… and the whole Wikipedia article as well. Commented Oct 8, 2010 at 20:13
  • "best" depends on the data and other constraints: memory, speed, how mis sorted to start. quicksort is a great compromise among those. bubble sort is a best for small memory. What do you want to accomplish? Commented Oct 8, 2010 at 20:16
  • The best (if best == fastest) sorting technique would be to get the data such that it's already sorted. Commented Oct 8, 2010 at 20:17
  • 1
    "following array" = "preceding array"? If yes, the fastest is to write it down sorted. Seriously, I do this in generated code. Commented Oct 8, 2010 at 20:41

5 Answers 5

Reset to default
70

In C, you can use the built-in qsort command:

int compare( const void* a, const void* b)
{
     int int_a = * ( (int*) a );
     int int_b = * ( (int*) b );
     
     if ( int_a == int_b ) return 0;
     else if ( int_a < int_b ) return -1;
     else return 1;
}

qsort( a, 6, sizeof(int), compare )

See: https://cplusplus.com/reference/cstdlib/qsort/

To answer the second part of your question: an optimal (comparison based) sorting algorithm is one that runs with O(n log(n)) comparisons. There are several that have this property (including quick sort, merge sort, heap sort, etc.), but which one to use depends on your use case.

As a side note, you can sometime do better than O(n log(n)) if you know something about your data — see the Wikipedia article on Radix Sort.

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

19 Comments

@Alex: if you want it fast, at least provide a decent compare function! qsort does not need the returned values to be -1, 0, 1, but "any negative number", 0, "any positive number", hence you just have to do return *((int*)a)-*((int*)b); which is much faster than your proposal.
@kriss: your comparison isn't well-defined in case of integer overflow; therefore, one often sees things like return (a > b) - (a < b)
@Stephen Canon: Agreed, you should use formulas like Christoph's when you know nothing of your data range and overflow can happen. In practical case I never saw a single occurence when dealing with signed numbers dans I didn't had some rough idea of the data range (and my formulas is also fine for unsigneds). My point was mostly that compare API result type is not -1,0,1 (or we couldn't even use strcmp for comparing char*).
@kriss: This use of notation is simply wrong. Even if it's randomized, it can hit cases where it takes quadratic time. Therefore, the big O is quadratic. Big O always means worst case. Use different notations for ridiculous "average case" complexity estimates.
@kriss: If I say an algorithm is O(f(n)) in time, that means the time it takes to run is bounded by a constant multiple of f(n), where the particular constant is implementation-dependent but constant within an implementation, for all possible inputs. Claiming quicksort is O(n log n) is as absurd as claiming if (rand()==42) return find_prime_factors(n); else return NULL; is O(1) with respect to n.
|
14

In your particular case the fastest sort is probably the one described in this answer. It is exactly optimized for an array of 6 ints and uses sorting networks. It is 20 times (measured on x86) faster than library qsort. Sorting networks are optimal for sort of fixed length arrays. As they are a fixed sequence of instructions they can even be implemented easily by hardware.

Generally speaking there is many sorting algorithms optimized for some specialized case. The general purpose algorithms like heap sort or quick sort are optimized for in place sorting of an array of items. They yield a complexity of O(n.log(n)), n being the number of items to sort.

The library function qsort() is very well coded and efficient in terms of complexity, but uses a call to some comparizon function provided by user, and this call has a quite high cost.

For sorting very large amount of datas algorithms have also to take care of swapping of data to and from disk, this is the kind of sorts implemented in databases and your best bet if you have such needs is to put datas in some database and use the built in sort.

Improve this answer

Comments

9

I'd like to make some changes: In C, you can use the built in qsort command:

int compare( const void* a, const void* b)
{
   int int_a = * ( (int*) a );
   int int_b = * ( (int*) b );

   // an easy expression for comparing
   return (int_a > int_b) - (int_a < int_b);
}

qsort( a, 6, sizeof(int), compare )
Improve this answer

Comments

7

Depends

It depends on various things. But in general algorithms using a Divide-and-Conquer / dichotomic approach will perform well for sorting problems as they present interesting average-case complexities.

Basics

To understand which algorithms work best, you will need basic knowledge of algorithms complexity and big-O notation, so you can understand how they rate in terms of average case, best case and worst case scenarios. If required, you'd also have to pay attention to the sorting algorithm's stability.

For instance, usually an efficient algorithm is quicksort. However, if you give quicksort a perfectly inverted list, then it will perform poorly (a simple selection sort will perform better in that case!). Shell-sort would also usually be a good complement to quicksort if you perform a pre-analysis of your list.

Have a look at the following, for "advanced searches" using divide and conquer approaches:

And these more straighforward algorithms for less complex ones:

Further

The above are the usual suspects when getting started, but there are countless others.

As pointed out by R. in the comments and by kriss in his answer, you may want to have a look at HeapSort, which provides a theoretically better sorting complexity than a quicksort (but will won't often fare better in practical settings). There are also variants and hybrid algorithms (e.g. TimSort).

Improve this answer

5 Comments

If you provide a perfectly inverted list to quicksort it will degenerate only in the most naive implementation (allways take head of the list as pivot) and even then it won't be worse that BubbleSort. The naive Quicksort would also perform poorly with an already sorted list. But very simple changes to the algorithm are enough to avoid the problem (extract several numbers from the list as potential pivot and choose median as pivot).
@kriss: Correct. But this is a CS-learning question, and so I just talk about the theoretical and basic implementation of each of these approaches. Obviously you can tweak algorithms and minimize these side-effects, but as the OP is asking about general sorting issues, I think it's more in-line to pinpoint these issues.
@haylem: it's indeed probably a learning question, but the risk speaking about naive implementations is for the reader to believe that the library call qsort is a naive implementation of QuickSort, which it is not, and would degenerate on sorted data set. If I remember correctly it is not even a QuickSort in most implementations.
You left out heap sort, which is quite arguably the ideal sort (O(1) space and O(n log n) time).
@R.: I left out many of them I guess :) But you're right, I should have mentioned heap-sort.
4

The best sorting technique of all generally depends upon the size of an array. Merge sort can be the best of all as it manages better space and time complexity according to the Big-O algorithm (This suits better for a large array).

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.