C Array Sorting

Question

a=[1,3,6,7,1,2] 

What is the best sorting method for sorting the next array, and if there are duplicates, how to handle them. Also, this is the best sorting technique for 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; } } } } 

Answer 1

In C, you can use the qsort built-in 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 http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/

---

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

As a side note, you can someday do better than O (n log (n)) if you know something about your data - see the wikipedia article on Radix Sort

Answer 2

In your particular case, the fastest view is probably described in this answer . It is finely optimized for an array of 6 circuits and uses sorting networks. This is 20 times (measured on x86) faster than the qsort library. Sort nets are optimal for sorted arrays with a fixed length. Since they are a fixed sequence of instructions, they can be easily implemented using hardware.

Generally speaking, there are many sorting algorithms optimized for some specialized case. General-purpose algorithms, such as heap sorting or quick sort, are optimized for sorting an array of elements in place. They give complexity O (n.log (n)), n is the number of elements to sort.

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

To sort a very large number of data algorithms, you also need to take care of replacing the data on and off the disk, this is the type of sorting implemented in the databases, and your best choice, if you have such needs, to put the data in any database and use inline sorting.

Answer 3

According to

It depends on different things. But overall, algorithms using Divide-and-Conquer / dichotomic are suitable for sorting tasks, since they present an interesting mid-range complexity.

The basics

To understand which algorithms work best, you will need some basic knowledge of complexity algorithms and a Big-O note so that you can understand how they are evaluated in terms of average case, best case, and worst case scenarios. on the stability of the sorting algorithm .

For example, a quicksort is usually an effective algorithm. However, if you give quicksort a completely inverted list, then it will work poorly (a simple sort selection will work better in this case!). Shell-sort will also usually be a good complement to quick sort if you do a preliminary analysis of your list.

Take a look at the following: advanced searches using the split and win approaches:

• quicksort
• shellsort
• mergesort

And these are more complex algorithms for less complex ones:

• bubblesort
• sorting selection
• insert sort

Further

The above are common suspects at startup, but there are others.

As pointed out by R. in the comments and chris in his answer, you can take a look at HeapSort , which provides theoretically better sorting complexity than quicksort (but in practical settings it will not often improve). There are also options and hybrid algorithms (e.g. TimSort ).

Answer 4

The best sorting technique generally depends on the size of the array. A merge sort may be the best of all, since it manages the best complexity of space and time according to the Big-O algorithm (this works best for a large array).

Answer 5

I would like to make some changes: In C, you can use the qsort built-in 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 )