Sorting. STL (part 12)




sorting in c ++, stlIt is a special group of sorting algorithms make - in practice it is necessary to sort a variety of objects and on a variety of criteria. An analysis of sorting algorithms are well and thoroughly studied, More than any other section of Computational Mathematics. The main issue of any sorting algorithm is its computational complexity - the number of comparison-exchange operations, required for sorting a sequence of length N, so-called O( N ).

The unpleasant fact is that, that the average complexity of different algorithms for different (on most test sequences) and the maximum complexity (at worst for a method of test sequence). For several tens of sorting algorithms, offered in learning Programming, shown, that the vast majority of them (intuitive) It is the worst in terms of average and in terms of maximum complexity. As an example,, popular among students bubble sorting It is the worst of all generally known.

Effective (complexity) the entire set of methods are only a few methods of fast recursive sorting. They are then presented to the STL implementations of algorithms. Standards do not insist on a hard constraint on domestic mechanisms for their implementation, therefore it may be possible depending on the library.

Now, having some knowledge about algorithms, functor and the general state of affairs with sorting, we are ready to consider options for implementing all this in your code. To start a variety of ways we sort numeric sequence. An example is too big, but it is not only, and as, to illustrate the, for subsequent self-experimentation:

Before compiling the program, in MVS press Alt + F7 and enter command arguments ?30 +3:sorting in c ++

Some awkwardness example due to the fact, that we are in the same code and combine all provided STL sorting algorithms, and a variety of test sorted sequence, for example:

  • Several random (?) sequences of length 30, sortable using (3) functor comparison, and detailed (+) terminal input and output sequences:

    sorting in c ++

  • Inverted (reverse, decreasing) sequence, sortable (6) "Heap" using a binary tree (command arguments -30 +6 ):sorting in c ++

  • long (1000000) sequence, the same, the previous case, conditions of, but only with the conclusion of correctness of the diagnosis results (command arguments -1000000 6 ):

    sorting in c ++

The STL offers 3 Group sorting algorithms:

  • sort() – the fastest sorting on average ( O( N * log( N ) ), but which can "fall" in the worst case to O( N * N ) (and it is a very poor indicator);

  • sort_heap() – sorting "on the heap", using a binary tree, whose complexity always no worse than O( N + N * log( N ) ) (it worse sort() average, but rather the worst case);

  • stable_sort() – "Stable" merge sort, which means stability, that it maintains the relative order of equal elements after sorting. It is sometimes very important. The complexity of this algorithm is much inferior sort();

Use the algorithm, which is most consistent with the constraints of your problem.

Newsletter of programming:

Sorting. STL (part 12)
3 (60%) 2 votes

About Olej

practical experience about software development 40 years. Teacher Global Logic international software company. IBM Developer Works Permanent author of publications. Scientific editor of the computer literature publishing house "Symbol-Plus", St. Petersburg.

Leave a Reply

Your email address will not be published. Required fields are marked *