Terms 31: Understand your sorting
How can I sort thee? Let me count the ways.
When many programmers think of the sort object, only one algorithm appears in the mind: sort. (Some of the programmers think of QSort, but once they look at the terms 46, they will give up QSort's ideas and replace them with the idea of sort.)
Now, Sort is a pleasant algorithm, but if you don't need you, there is no need to waste expression. Sometimes you don't need to be completely sorted. For example, if you have a Widget's Vector, you want to choose 20 quality widgets to send to your most loyal customers, you need to do just sort to identify 20 best widgets, the remaining can remain unordered . What you need is part sorting, there is an algorithm called Partial_Sort, which accurately completes its name:
Bool QualityCompare (Const Widget & lh, Const Widget & RHS)
{
// Returns the quality of LHS is not better than RHS.
}
...
Partial_sort (widgets.begin (), // Put the best 20 elements
Widgets.begin () 20, // (in order) placed on the front end of Widgets
Widgets.end (),
Qualitycompare);
... // Use widgets ...
After calling Partial_Sort, the top 20 elements of Widgets are the best in the container and they are arranged in order, that is, the highest quality widget is widgets [0], the second high is widgets [1], etc.. This is what you are easy to send the best Widget to your best customer, the second good widget gives you the second good customer.
If you care about it, you can give you 20 best customers, but you don't care which customer gives you, Partial_sort gives you more than needed. In that case, you need only 20 best Widgets in any order. STL has an algorithm to complete you need, although the name is unlikely to be built from your brain. It is called NTH_EEMENT.
Nth_element Sort a range, the element in the RI position (you specified) is that if the interval is completely sorted, there will be elements there. Further, when NTH_Element returns, the elements above N are not after the elements of position N, and the elements in n or less are not before the elements of the position N below. If this sounds very complicated, it's just because I have to choose my language. I will explain why, but let's take a look at how to use nth_element to ensure the best 20 widgets at the front end of the Widgets Vector:
nth_element (widgets.begin (), // Put the best 20 elements
Widgets.begin () 20, // is placed at the front of the widgets,
Widgets.end (), / / don't worry
QualityCompare); // their order
As you can see, call NTH_ELEMENT to be equivalent to calling Partial_Sort. The only difference between them is that Partial_Sort sorts the elements in position 1-20, while nth_element is not. However, both algorithms move 20 quality widgets to the front end of the Vector.
That leads to an important issue. What should these algorithms do these algorithms when there is an element? For example, there is a grade 1 (probably the best), 15 element qualities are level 2 (second good). In this case, choosing 20 best Widgets is to select 8 levels in 12 and 15 in 15. How does Partial_Sort and NTH_EEMENT judge what is the best 20 in 15? For this problem, how does Sort determines the order of elements when multiple elements have an equivalent value? Partial_sort and nth_element sorted the value equivalent elements in any way, and you can't control them in this area. (Terms 19 can tell you what two values are equivalent.) In our example, when you need to set the quality of the Qidget, you can choose to choose them. Any one you want. This is not no reason. If you need 20 best widgets and some very good widgets, you shouldn't complain that you have 20 at least as you retrieved.
For complete sorting, you have a little more control. Some sorting algorithms are stable. In stable sorting, if two elements in one interval have an equivalent value, their relative positions do not change after sorting. Therefore, if Widget A before (not sorted) Widget A before Widget B, and both have the same quality level, the stable sorting calculation guarantees that the Widget A is still before Widget B after this Vector sort. Unstable algorithms did not do this guarantee.
Partial_sort is unstable. Nth_Element, Sort did not provide stability, but there is an algorithm --stable_sort - it completes its name. If you need stability when you sort, you may have to use Stable_Sort. The STL does not contain a stable version of Partial_Sort and Nth_Element.
Talk now about nth_element, this name is strange algorithm is a piercer multi-face. In addition to helping you find N elements at the top of the interval, it can also be used to find the median of the interval or find the element in the specified percentage point:
Vector
Vector
// Variable of iterator
Vector
// The following code is looking for
/ / Medium quality level Widget
// s position
Goalposition = Begin widgets.size () / 2; // Interest Widget
/ / Will be the middle of an orderly vector
Nth_Element (begin, goalposition, end, // find widgets in widgets
Qualitycompare); // Quality rating value
... // GoalPosition Now points
/ / Medium quality level Widget
// The following code can be found
// WIDGET with a quality grade of 75%
Vector
0.25 * widgets.size (); // How far is the start
Nth_Element (Begin, Begin Goaloffset, End, // Find the quality value
QualityCompare); // 75% Widget
... // GoalPosition now pointing to // Widget with a quality level of 75%
If you really need to place something in order, sort, stable_sort and partial_sort are excellent, when you need to identify the N elements of the top or Nth_Element when you need the element in a specified location. But sometimes you need something like nth_element, but not exactly the same. For example, it is assumed that you don't need to identify 20 quality widgets. Instead, you need to identify the quality level of 1 or 2. Of course, you can sort this vector according to quality, then search the first quality level ratio of 2 poor. Then you can identify the range of Widgets in the quality of the Widget.
But completely sorting requires a lot of work, and many unnecessary work is made for this task. A better strategy is to use the Partition algorithm that rearranges the elements in the interval to start all the elements that satisfy a standard in the range.
For example, moving all the quality grades of 2 or better widget to the front of the widgets, we define a function to identify which widget is this level.
Bool Hasacceptablequality (const widget & w)
{
/ / Returns whether the W quality level is 2 or higher;
}
This function is sent to Partition:
Vector
Partition (widgets.begin (), //'s widgets move to the front of the widgets,
Widgets.end (), / / and return a point to the first
Hasacceptablequality); // Not satisfied with Widget iterator
After this call is completed, all the quality is 1 or 2 widget from widgets.begin () to Goodend, which contains all the quality levels of widgets from Goodend to Widgets.end (). If the relative position of the Widget that maintains the same quality grade is important, we will naturally use Stable_Partition instead of Partition.
Algorithm sort, stable_sort, partial_sort, and nth_element requires random access iterators, so they may only be used for Vector, String, Deque, and arrays. Sorting elements of standard associated containers is meaningless, as such containers use their comparison functions to remain in an order at any time. The only container that we may but cannot use sort, stable_sort, partial_sort, or nth_element is List, and list has made some compensation by providing the Sort member function. (Interestingly, List :: Sort provides stable sort.) So if you want to sort a list, you can, but if you want to perform partial_sort or nth_element on the object in List, you must be done indirectly. An indirect method is to copy the elements into a container that supports random access iterators, and then applies the algorithms you need. Another method is to create a List :: Iterator container, use the algorithm for that container, and then access the list element through the iterator. The third method is to use the information of an orderly iterator container to iterate to join the elements of the List to you want to let them. As you can see, there are a lot of choices.
Partition and Stable_Partition are different from sort, stable_sort, partial_sort, and nth_element, they only need a two-way iterator. So you can use Partition and Stable_Partition on any standard sequence iterator.
We summarize your sort selection:
If you need to be completely sorted on the Vector, String, Deque, or arrays, you can use sort or stable_sort. If you have a Vector, String, Deque or array, you only need to sort N elements, you should use partial_sort. If you have a Vector, String, Deque, or array, you need to identify the nth element or you need to identify the first n elements, don't know their order, nth_element is you should pay attention to and call. If you need to separate the element or array of standard sequence containers to meet and don't satisfy a standard, you probably find partition or stable_partition. If your data is in List, you can use Partition and Stable_Partition directly, you can use List's sort instead of sort and stable_sort. If you need the effect of partial_sort or nth_element, you must complete this task indirectly, but as I have ticked it on it, there will be a lot of choices. In addition, you can keep the data in a standard related container to keep at all times ordered. You may also consider standard non-STL container priority_queue, which can always keep it in order. (Priority_Queue is traditionally considering part of STL, but as I showed it in the introduction, I defined "STL" is required to support iterators, and priority_queue does not have iterators.)
"But how do you?", You want to know. This is an excellent problem. In general, more work algorithms are more than doing less, and the algorithm that must be stabilized is longer than ignoring the stability algorithm. We can order our algorithms discussed in this Terms as follows, and require fewer resources (time and space) algorithm that require more front:
1. Partition4. Partial_sort2. Stable_partition5. Sort3. Nth_element6. Stable_sort
I have selected the choice between these sort algorithms to make your choice based on the tasks you need to complete, not considering performance. If your algorithm completes you need (for example, using partition instead of complete sorting), you can get the code you want to do, but also use STL's most efficient way to complete it.
