Order by pair comparisons: Difference between revisions

Content added Content deleted

Inline

@@ Line 28: / Line 28: @@
 * A routine that does not ask the user "too many" comparison questions should be used.
+=={{header|C++}}==
+<lang cpp>#include <algorithm>
+#include <iostream>
+#include <vector>
+using namespace std;
+bool InteractiveCompare(const string& s1, const string& s2)
+{
+    if(s1 == s2) return false;  // don't ask to compare items that are the same
+    static int count = 0;
+    string response;
+    cout << "(" << ++count << ") Is " << s1 << " < " << s2 << "? ";
+    getline(cin, response);
+    return !response.empty() && response.front() == 'y';
+}
+void PrintOrder(const vector<string>& items)
+{
+    cout << "{ ";
+    for(auto& item : items) cout << item << " ";
+    cout << "}\n";
+}
+int main()
+{
+    const vector<string> items
+    {
+        "violet", "red", "green", "indigo", "blue", "yellow", "orange"
+    };
+    vector<string> sortedItems;
+    // Use a binary insertion sort to order the items.  It should ask for
+    // close to the minimum number of questions reqired
+    for(auto& item : items)
+    {
+        cout << "Inserting '" << item << "' into ";
+        PrintOrder(sortedItems);
+        // lower_bound performs the binary search using InteractiveCompare to
+        // rank the items
+        auto spotToInsert = lower_bound(sortedItems.begin(),
+                                        sortedItems.end(), item, InteractiveCompare);
+        sortedItems.insert(spotToInsert, item);
+    }
+    PrintOrder(sortedItems);
+}
+</lang>
+{{out}}
+<pre>
+Inserting 'violet' into { }
+Inserting 'red' into { violet }
+(1) Is violet < red? n
+Inserting 'green' into { red violet }
+(2) Is violet < green? n
+(3) Is red < green? y
+Inserting 'indigo' into { red green violet }
+(4) Is green < indigo? y
+(5) Is violet < indigo? n
+Inserting 'blue' into { red green indigo violet }
+(6) Is indigo < blue? n
+(7) Is green < blue? y
+Inserting 'yellow' into { red green blue indigo violet }
+(8) Is blue < yellow? n
+(9) Is green < yellow? n
+(10) Is red < yellow? y
+Inserting 'orange' into { red yellow green blue indigo violet }
+(11) Is blue < orange? n
+(12) Is yellow < orange? n
+(13) Is red < orange? y
+{ red orange yellow green blue indigo violet }
+</pre>