For LINQ to Objects, it&#39;s a stable quicksort that is used. For any other kind of LINQ, it&#39;s left to the underlying implementation.

Boot up reflector, open to System.Linq.EnumerableSorter&lt;TElement&gt; reveals that Linq2Objects uses the quick sort

Quicksort is used, but the reason why it is stable is because the indices of each pair of elements are compared if all the keys test equal. 

In other words, you can make any quicksort stable by including in the comparator function a comparison of the original indices of the two elements as a fallback. 

Source: http://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs,1395017e067e5a34


I am under the understanding that `OrderBy` gets translated into SQL that performs the sort on the Database.  At least in the case of LINQ to SQL

I am pioneering unit testing efforts at my company, and need need to choose a mocking framework to use. I have never used a mocking framework before. We have already chosen Google Test, so using Google Mock would be nice. However, my initial impressions after looking at &lt;a href=&quot;http://code.google.com/p/googlemock/wiki/ForDummies&quot;&gt;Google Mock&#39;s tutorial&lt;/a&gt; are:

 - The need for re-declaring each method in the mocking class with a MOCK_METHODn macro seems unnecessary and seems to go against the DRY principle.
 - Their matchers (eg, the &#39;_&#39; in EXPECT_CALL(turtle, Forward(_));) and the order of matching seem almost too powerful. Like, it would be easy to say something you don&#39;t mean, and miss bugs that way.

I have high confidence in google&#39;s developers, and low confidence in my own ability to judge mocking frameworks, never having used them before. So my question is: **Are these valid concerns?** 

Or is there no better way to define a mock object, and are the matchers intuitive to use in practice? I would appreciate answers from anyone who has used Google Mock before, and comparisons to other C++ frameworks would be helpful.

Is Google Mock a good mocking framework?

Windows Forms&#39; `CheckBox` control implements both `CheckedChanged` and `CheckStateChanged` events. As far as I can tell, both fire when the checked status of the checkbox is changed. 

`CheckedChanged` precedes `CheckStateChanged`, but other than that I see no difference. Am I missing something? Should one be preferred over another?


Windows Forms&#39; CheckBox CheckedChanged vs. CheckStateChanged

Evidently LINQ&#39;s &quot;OrderBy&quot; had originally been specified as unstable, but by the time of Orca it was specified as stable.  Not all documentation has been updated accordingly - consider these links:

 - [Jon Skeet on OrderBy stability][1]
 - [Troy Magennis on OrderBy stability][2]

But if LINQ&#39;s OrderBy is now &quot;stable,&quot; then it means it is not using a quicksort (which is inherently unstable) even though some documentation (e.g. Troy&#39;s book) says it is.  So my question is: if not quicksort, then what is the actual algorithm LINQ&#39;s orderBy is using?

  [1]: https://stackoverflow.com/questions/1209935/orderby-and-orderbydescending-are-stable
  [2]: https://stackoverflow.com/questions/2786930/linq-quicksort-is-unstable-except-when-cascading

What Sorting Algorithm Is Used By LINQ &quot;OrderBy&quot;?

<p>Evidently LINQ's "OrderBy" had originally been specified as unstable, but by the time of Orca it was specified as stable.  Not all documentation has been updated accordingly - consider these links:</p>
<ul>
<li><a href="https://stackoverflow.com/questions/1209935/orderby-and-orderbydescending-are-stable" target="_blank" rel="noopener noreferrer">Jon Skeet on OrderBy stability</a></li>
<li><a href="https://stackoverflow.com/questions/2786930/linq-quicksort-is-unstable-except-when-cascading" target="_blank" rel="noopener noreferrer">Troy Magennis on OrderBy stability</a></li>
</ul>
<p>But if LINQ's OrderBy is now "stable," then it means it is not using a quicksort (which is inherently unstable) even though some documentation (e.g. Troy's book) says it is.  So my question is: if not quicksort, then what is the actual algorithm LINQ's orderBy is using?</p>


## Intro ##

In the application I &#39;m currently working on, there are two kinds of each business object: the &quot;ActiveRecord&quot; kind and the &quot;DataContract&quot; kind. So for example, there would be:

    namespace ActiveRecord {
        class Widget {
            public int Id { get; set; }
        }
    }

    namespace DataContract {
        class Widget {
            public int Id { get; set; }
        }
    }

The database access layer takes care of translating between families: you can tell it to update a `DataContract.Widget` and it will magically create an `ActiveRecord.Widget` with the same property values and save that instead.

The problem surfaced when attempting to refactor this database access layer.

## The Problem ##

I want to add methods like the following to the database access layer:

    // Widget is DataContract.Widget

    interface IDbAccessLayer {
        IEnumerable&lt;Widget&gt; GetMany(Expression&lt;Func&lt;Widget, bool&gt;&gt; predicate);
    }

The above is a simple general-use &quot;get&quot; method with custom predicate. The only point of interest is that I am passing in an expression tree instead of a lambda because inside `IDbAccessLayer` I am querying an `IQueryable&lt;ActiveRecord.Widget&gt;`; to do that efficiently (think LINQ to SQL) I need to pass in an expression tree so this method asks for just that.

The snag: the parameter needs to be magically transformed from an `Expression&lt;Func&lt;DataContract.Widget, bool&gt;&gt;` to an `Expression&lt;Func&lt;ActiveRecord.Widget, bool&gt;&gt;`.

## Attempted Solution ##

What I &#39;d like to do inside `GetMany` is:

    IEnumerable&lt;DataContract.Widget&gt; GetMany(
        Expression&lt;Func&lt;DataContract.Widget, bool&gt;&gt; predicate)
    {
        var lambda = Expression.Lambda&lt;Func&lt;ActiveRecord.Widget, bool&gt;&gt;(
            predicate.Body,
            predicate.Parameters);
    
        // use lambda to query ActiveRecord.Widget and return some value
    }

This won&#39;t work because in a typical scenario, for example if:

    predicate == w =&gt; w.Id == 0;

...the expression tree contains a `MemberAccessExpression` instance which has a property of type `MemberInfo` that describes `DataContract.Widget.Id`.
There are also `ParameterExpression` instances both in the expression tree and in its parameter collection (`predicate.Parameters`) that describe `DataContract.Widget`; all of this will result in errors since the queryable body does not contain that type of widget but rather `ActiveRecord.Widget`.

After searching a bit, I found [`System.Linq.Expressions.ExpressionVisitor`][1] (its source can be found [here][2] in the context of a how-to), which offers a convenient way to modify an expression tree. In .NET 4, this class is included out of the box.

Armed with this, I implemented a visitor. This simple visitor only takes care of changing the types in member access and parameter expressions, but that&#39;s enough functionality to work with the predicate `w =&gt; w.Id == 0`.

    internal class Visitor : ExpressionVisitor
    {
        private readonly Func&lt;Type, Type&gt; typeConverter;

        public Visitor(Func&lt;Type, Type&gt; typeConverter)
        {
            this.typeConverter = typeConverter;
        }

        protected override Expression VisitMember(MemberExpression node)
        {
            var dataContractType = node.Member.ReflectedType;
            var activeRecordType = this.typeConverter(dataContractType);
            
            var converted = Expression.MakeMemberAccess(
                base.Visit(node.Expression),
                activeRecordType.GetProperty(node.Member.Name));

            return converted;
        }

        protected override Expression VisitParameter(ParameterExpression node)
        {
            var dataContractType = node.Type;
            var activeRecordType = this.typeConverter(dataContractType);

            return Expression.Parameter(activeRecordType, node.Name);
        }
    }

With this visitor, `GetMany` becomes:

    IEnumerable&lt;DataContract.Widget&gt; GetMany(
        Expression&lt;Func&lt;DataContract.Widget, bool&gt;&gt; predicate)
    {
        var visitor = new Visitor(...);
        var lambda = Expression.Lambda&lt;Func&lt;ActiveRecord.Widget, bool&gt;&gt;(
            visitor.Visit(predicate.Body),
            predicate.Parameters.Select(p =&gt; visitor.Visit(p));
    
        var widgets = ActiveRecord.Widget.Repository().Where(lambda);

        // This is just for reference, see below
        Expression&lt;Func&lt;ActiveRecord.Widget, bool&gt;&gt; referenceLambda = 
            w =&gt; w.Id == 0;

        // Here we &#39;d convert the widgets to instances of DataContract.Widget and
        // return them -- this has nothing to do with the question though.
    }

## Results ##

The good news is that `lambda` is constructed just fine. The bad news is that it isn&#39;t working; it&#39;s blowing up on me when I try to use it, and the exception messages are really not helpful at all.

I have examined the lambda my code produces and a hardcoded lambda with the same expression; they look exactly the same. I spent hours in the debugger trying to find some difference, but I can&#39;t.

When the predicate is `w =&gt; w.Id == 0`, `lambda` looks exactly like `referenceLambda`. But the latter works with e.g. `IQueryable&lt;T&gt;.Where`, while the former does not; I have tried this in the immediate window of the debugger.

I should also mention that when the predicate is `w =&gt; true`, everything works fine. Therefore I am assuming that I &#39;m not doing enough work in the visitor, but I can&#39;t find any more leads to follow.

## Final Solution ##

After taking into account the correct answers to the problem (two of them below; one short, one with code) the problem was solved; I put the code along with a few important notes in a [separate answer][3] to keep this long question from becoming even longer.

Thanks to everyone for your answers and comments!


  [1]: http://msdn.microsoft.com/en-us/library/system.linq.expressions.expressionvisitor%28v=VS.100%29.aspx
  [2]: http://msdn.microsoft.com/en-us/library/bb882521%28VS.90%29.aspx
  [3]: https://stackoverflow.com/a/10467736/50079

Mutating the expression tree of a predicate to target another type

I&#39;ve recently started using LINQ quite a bit, and I haven&#39;t really seen any mention of run-time complexity for any of the LINQ methods. Obviously, there are many factors at play here, so let&#39;s restrict the discussion to the plain `IEnumerable` LINQ-to-Objects provider. Further, let&#39;s assume that any `Func` passed in as a selector / mutator / etc. is a cheap O(1) operation.  

It seems obvious that all the single-pass operations (`Select`, `Where`, `Count`, `Take/Skip`, `Any/All`, etc.) will be O(n), since they only need to walk the sequence once; although even this is subject to laziness. 

Things are murkier for the more complex operations; the set-like operators (`Union`, `Distinct`, `Except`, etc.) work using `GetHashCode` by default (afaik), so it seems reasonable to assume they&#39;re using a hash-table internally, making these operations O(n) as well, in general. What about the versions that use an `IEqualityComparer`? 

`OrderBy` would need a sort, so most likely we&#39;re looking at O(n log n). What if it&#39;s already sorted? How about if I say `OrderBy().ThenBy()` and provide the same key to both? 

I could see `GroupBy` (and `Join`) using either sorting, or hashing. Which is it? 

`Contains` would be O(n) on a `List`, but O(1) on a `HashSet` - does LINQ check the underlying container to see if it can speed things up? 

And the real question - so far, I&#39;ve been taking it on faith that the operations are performant. However, can I bank on that? STL containers, for example, clearly specify the complexity of every operation. Are there any similar guarantees on LINQ performance in the .NET library specification? 

More question (in response to comments):  
Hadn&#39;t really thought about overhead, but I didn&#39;t expect there to be very much for simple Linq-to-Objects. The CodingHorror post is talking about Linq-to-SQL, where I can understand parsing the query and making SQL would add cost - is there a similar cost for the Objects provider too? If so, is it different if you&#39;re using the declarative or functional syntax? 

What guarantees are there on the run-time complexity (Big-O) of LINQ methods?

I&#39;m trying to get the key of the maximum value in the `Dictionary&lt;string, double&gt; results`.

This is what I have so far:

    double max = results.Max(kvp =&gt; kvp.Value);
    return results.Where(kvp =&gt; kvp.Value == max).Select(kvp =&gt; kvp.Key).First();

However, since this seems a little inefficient, I was wondering whether there was a better way to do this.

Good way to get the key of the highest value of a Dictionary in C#

How do you get a list of all ModelState error messages?  I found this code to get all the keys:
( https://stackoverflow.com/questions/888521/returning-a-list-of-keys-with-modelstate-errors)

    var errorKeys = (from item in ModelState
            where item.Value.Errors.Any() 
            select item.Key).ToList();

But how would I get the error messages as a IList or IQueryable?

I could go:

    foreach (var key in errorKeys)
    {
        string msg = ModelState[error].Errors[0].ErrorMessage;
        errorList.Add(msg);
    }

But thats doing it manually - surely there is a way to do it using LINQ? The .ErrorMessage property is so far down the chain that I don&#39;t know how to write the LINQ...



ASP.NET MVC How to convert ModelState errors to json

What is the difference between returning `IQueryable&lt;T&gt;` vs. `IEnumerable&lt;T&gt;`, when should one be preferred over the other?


    IQueryable&lt;Customer&gt; custs = from c in db.Customers
    where c.City == &quot;&lt;City&gt;&quot;
    select c;

    IEnumerable&lt;Customer&gt; custs = from c in db.Customers
    where c.City == &quot;&lt;City&gt;&quot;
    select c;

Will both be deferred execution and when should one be preferred over the other?

Returning IEnumerable&lt;T&gt; vs. IQueryable&lt;T&gt;

I have a map where I&#39;d like to perform a call on every data type object member function. I yet know how to do this on any sequence but, is it possible to do it on an associative container?

The closest answer I could find was this: [Boost.Bind to access std::map elements in std::for_each][1]. But I cannot use boost in my project so, is there an STL alternative that I&#39;m missing to boost::bind?

If not possible, I thought on creating a temporary sequence for pointers to the data objects and then, call for_each on it, something like this:

    class MyClass
    {
    public:
     void Method() const;
    }
    
    std::map&lt;int, MyClass&gt; Map;
    //...
    
    std::vector&lt;MyClass*&gt; Vector;
    std::transform(Map.begin(), Map.end(), std::back_inserter(Vector), std::mem_fun_ref(&amp;std::map&lt;int, MyClass&gt;::value_type::second));
    std::for_each(Vector.begin(), Vector.end(), std::mem_fun(&amp;MyClass::Method));

It looks too obfuscated and I don&#39;t really like it. Any suggestions?

  [1]: https://stackoverflow.com/questions/2311752/boost-bind-to-access-stdmap-elements-in-stdfor-each


Use of for_each on map elements

Predominantly DFS is used to find a cycle in graphs and not BFS. Any reasons? Both can find if a node has already been
visited while traversing the tree/graph.

Why DFS and not BFS for finding cycle in graphs

Is there a difference between _genetic algorithms_ and _evolutionary algorithms_? 

I have read multiple papers, talking about genetic or evolutionary algorithms, and while very similar, I think they may not be the same thing.


What is the difference between genetic and evolutionary algorithms?

What is the effective way to replace all occurrences of a character with another character in `std::string`?

How to replace all occurrences of a character in string?

I&#39;m looking for the easiest way to sort an array that consists of numbers and text, and a combination of these.

E.g.

    &#39;123asd&#39;
    &#39;19asd&#39;
    &#39;12345asd&#39;
    &#39;asd123&#39;
    &#39;asd12&#39;

turns into

    &#39;19asd&#39;
    &#39;123asd&#39;
    &#39;12345asd&#39;
    &#39;asd12&#39;
    &#39;asd123&#39;

This is going to be used in combination with the solution to [another question I&#39;ve asked here][1].

The sorting function in itself works, what I need is a function that can say that that &#39;19asd&#39; is smaller than &#39;123asd&#39;.

I&#39;m writing this in JavaScript.

  [1]: https://stackoverflow.com/questions/2793847/sort-outer-array-based-on-values-in-inner-array-javascript

Edit: as *adormitu* pointed out, what I&#39;m looking for is a function for natural sorting

Javascript : natural sort of alphanumerical strings

How can I sort an array in NumPy by the nth column?

For example,

    a = array([[9, 2, 3],
               [4, 5, 6],
               [7, 0, 5]])

I&#39;d like to sort rows by the second column, such that I get back:

    array([[7, 0, 5],
           [9, 2, 3],
           [4, 5, 6]])


Sorting arrays in NumPy by column

I learned how to use the comparable but I&#39;m having difficulty with the Comparator. I am having a error in my code: 

    Exception in thread &quot;main&quot; java.lang.ClassCastException: New.People cannot be cast to java.lang.Comparable
     at java.util.Arrays.mergeSort(Unknown Source)
     at java.util.Arrays.sort(Unknown Source)
     at java.util.Collections.sort(Unknown Source)
     at New.TestPeople.main(TestPeople.java:18)

Here is my code:

    import java.util.Comparator;

    public class People implements Comparator {
       private int id;
       private String info;
       private double price;
     
       public People(int newid, String newinfo, double newprice) {
           setid(newid);
           setinfo(newinfo);
           setprice(newprice);
       }
     
       public int getid() {
           return id;
       }
    
       public void setid(int id) {
           this.id = id;
       }
    
       public String getinfo() {
           return info;
       }
    
       public void setinfo(String info) {
           this.info = info;
       }
    
       public double getprice() {
           return price;
       }
    
       public void setprice(double price) {
           this.price = price;
       }
    
       public int compare(Object obj1, Object obj2) {
           Integer p1 = ((People) obj1).getid();
           Integer p2 = ((People) obj2).getid();
      
           if (p1 &gt; p2) {
               return 1;
           } else if (p1 &lt; p2){
               return -1;
           } else {
               return 0;
           }
        }
    }

&lt;!-- language: lang-java --&gt;

    import java.util.ArrayList;
    import java.util.Collections;

    public class TestPeople {
        public static void main(String[] args) {
            ArrayList peps = new ArrayList();
      
            peps.add(new People(123, &quot;M&quot;, 14.25));
            peps.add(new People(234, &quot;M&quot;, 6.21));
            peps.add(new People(362, &quot;F&quot;, 9.23));
            peps.add(new People(111, &quot;M&quot;, 65.99));
            peps.add(new People(535, &quot;F&quot;, 9.23));
      
            Collections.sort(peps);
      
            for (int i = 0; i &lt; peps.size(); i++){
                System.out.println(peps.get(i));
            }
        }
    }

I believe it has to do something with the casting in the compare method but I was playing around with it and still could not find the solution

How to use Comparator in Java to sort

I have an array such as:

    Array
    (
    [0] =&gt; Array
        (
            [id] =&gt; 2
            [type] =&gt; comment
            [text] =&gt; hey
            [datetime] =&gt; 2010-05-15 11:29:45
        )
 
    [1] =&gt; Array
        (
            [id] =&gt; 3
            [type] =&gt; status
            [text] =&gt; oi
            [datetime] =&gt; 2010-05-26 15:59:53
        )
 
    [2] =&gt; Array
        (
            [id] =&gt; 4
            [type] =&gt; status
            [text] =&gt; yeww
            [datetime] =&gt; 2010-05-26 16:04:24
        )
 
    )


Can anyone suggest a way to sort/order this based on the datetime element?

PHP Sort a multidimensional array by element containing Y-m-d H:i:s date

I am trying to &#39;destructure&#39; a dictionary and associate values with variables names after its keys. Something like

    params = {&#39;a&#39;:1,&#39;b&#39;:2}
    a,b = params.values()

But since dictionaries are not ordered, there is no guarantee that `params.values()` will return values in the order of `(a, b)`. Is there a nice way to do this?

Destructuring-bind dictionary contents

Why quicksort(or introsort), or any comparison-based sorting algorithm is more common than radix-sort? Especially for sorting numbers.

Radix-sort is not comparison based, hence may be faster than O(n*logn). In fact, it is O(k*n), where k is the number of bits used to represent each item. And the memory overhead is not critical, since you may choose the number of buckets to use, and required memory may be less than mergesort&#39;s requirements.

Does it have to do with caching? Or maybe accessing random bytes of integers in the array?

Why quicksort is more popular than radix-sort?

Java 6&#39;s `Arrays.sort` method uses Quicksort for arrays of primitives and merge sort for arrays of objects. I believe that most of time Quicksort is faster than merge sort and costs less memory. My experiments support that, although both algorithms are O(n log(n)). So why are different algorithms used for different types?

Why does Java&#39;s Arrays.sort method use two different sorting algorithms for different types?

It seems Radix sort has a very good average case performance, i.e. _O(kN)_: http://en.wikipedia.org/wiki/Radix_sort

Yet it seems like most people are still using Quick Sort - why is this?


When should we use Radix sort?

I read the following in a forum :

&gt; Merge sort is very efficient for
&gt; immutable datastructures like linked
&gt; lists

and

&gt; Quick sort is typically faster than
&gt; merge sort when the data is stored in
&gt; memory. However, when the data set is
&gt; huge and is stored on external devices
&gt; such as a hard drive, merge sort is
&gt; the clear winner in terms of speed. It
&gt; minimizes the expensive reads of the
&gt; external drive

and 

&gt; when operating on linked lists, merge sort only requires a small constant amount of auxiliary storage

Can someone help me understand the above argument? why is merge sort preferred for sorting huge linked lists? and how does it minimize expensive reads to an external drive? basically i want to understand why one would choose merge sort for sorting a big linked list.


why is merge sort preferred over quick sort for sorting linked lists

Haskell&#39;s website introduces a very attractive 5-line [quicksort function](http://www.haskell.org/haskellwiki/Introduction#Quicksort_in_Haskell), as seen below.

    quicksort [] = []
    quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
        where
            lesser = filter (&lt; p) xs
            greater = filter (&gt;= p) xs

They also include a *&quot;True quicksort in C&quot;*. 

    // To sort array a[] of size n: qsort(a,0,n-1)
    
    void qsort(int a[], int lo, int hi) 
    {
      int h, l, p, t;
    
      if (lo &lt; hi) {
        l = lo;
        h = hi;
        p = a[hi];
    
        do {
          while ((l &lt; h) &amp;&amp; (a[l] &lt;= p)) 
              l = l+1;
          while ((h &gt; l) &amp;&amp; (a[h] &gt;= p))
              h = h-1;
          if (l &lt; h) {
              t = a[l];
              a[l] = a[h];
              a[h] = t;
          }
        } while (l &lt; h);
    
        a[hi] = a[l];
        a[l] = p;
    
        qsort( a, lo, l-1 );
        qsort( a, l+1, hi );
      }
    }

A link below the C version directs to a page that states *&#39;The quicksort quoted in Introduction isn&#39;t the &quot;real&quot; quicksort and doesn&#39;t scale for longer lists like the c code does.&#39;*

Why is the above Haskell function not a true quicksort? How does it fail to scale for longer lists?

Content Type	Original Author	Original Content on Stackoverflow
Question	Brent Arias	View Question on Stackoverflow
Solution 1 - Linq	Jb Evain	View Answer on Stackoverflow
Solution 2 - Linq	LorenVS	View Answer on Stackoverflow
Solution 3 - Linq	Wesner Moise	View Answer on Stackoverflow
Solution 4 - Linq	John Weldon	View Answer on Stackoverflow

What Sorting Algorithm Is Used By LINQ "OrderBy"?

Linq Problem Overview

Linq Solutions

Solution 1 - Linq

Solution 2 - Linq

Solution 3 - Linq

Solution 4 - Linq

Windows Forms' CheckBox CheckedChanged vs. CheckStateChanged

Is Google Mock a good mocking framework?

Attributions