Array.Sort in with a nontrivial comparison function

Question

Consider the following code from C # 5.0 in a nutshell, p. 289:

int[] numbers = { 1, 2, 3, 4, 5 }; Array.Sort (numbers, (x, y) => x % 2 == y % 2 ? 0 : x % 2 == 1 ? -1 : 1); 

which gives the result {3, 5, 1, 2, 4} .

I tried this on paper and got {1, 3, 5, 2, 4} .

Why did computer sorting give 3 > 5 > 1 ?

Answer 1

Although Array.Sort indicates

If the section size is less than 16 elements, it uses an insertion sorting algorithm.

he does not indicate how he performs this insertion sort, or what flavor of insertion sort is used. As already mentioned, it further indicates

This implementation performs unstable sorting.

and, as a result, the only thing Array.Sort promises about the order of returned items is sorting them. This is true for {3, 5, 1, 2, 4} .

Note that the algorithm used by Array.Sort would be allowed to do something like this (Pseudocode):

 if sequence = {1, 2, 3, 4, 5} then sequence := {3, 5, 1, 2, 4} end if Sort(sequence); 

This, of course, will be the behavior defined by the implementation, and it may change in another version of the .NET framework.

Code change

 Array.Sort(numbers, (x, y) => { Console.WriteLine(x + ", " + y); return x % 2 == y % 2 ? 0 : x % 2 == 1 ? -1 : 1; }); 

will give you comparisons that are done using Array.Sort :

 1, 3 1, 5 3, 5 1, 3 3, 5 2, 3 3, 4 3, 3 5, 3 5, 3 5, 5 5, 3 2, 4 2, 1 4, 2 1, 4 4, 4 4, 2 1, 2 1, 2 1, 1 1, 2 1, 1 

And this, most likely, is not how you do an insertion sort on paper.

Point: Array.Sort promises to sort your sequence, but it does not promise how to do this.

Answer 2

Most likely, we are talking about the fact that Sort does not guarantee the order of elements that are equal. Unlike stable sortings, algorithms that preserve the original order of equal elements, “unstable sort” can change them. Usually, when you sort manually, you do a “stable sort”.

Array.Sort :

This implementation performs unstable sorting; that is, if two elements are equal, their order may not be preserved. In contrast, robust sorting preserves the order of equal elements.

The sorting function used in the sample makes 1 == 3, 1 == 5 , so unstable sorting is allowed to order these numbers in any way if they are in the correct order compared to others: 1,3,5 (stable - the same order as in the source) or any sequence 3,1,5 (unstable sorting).

those. OrderBy implements a "stable view" and you can see the results in the following example using the same comparison function:

 void Main() { int[] numbers = { 1, 2, 3, 4, 5 }; var result = numbers.OrderBy(x=> x, new MyComparer())); // 1, 3, 5, 2, 4 } public class MyComparer : IComparer<int> { public int Compare( int x, int y) { return x % 2 == y % 2 ? 0 : x % 2 == 1 ? -1 : 1; } } 

Answer 3

This code is equivalent to:

 static void Main(string[] args) { int[] numbers = { 1, 2, 3, 4, 5 }; Array.Sort(numbers, OnComparison); } private static int OnComparison(int x, int y) { if (x%2 == y%2) return 0; if (x%2 == 1) return 1; return -1; } 

I get:

 {3, 5, 1, 2, 4} 

The sort operation is as follows:

 0) {1,2,3,4,5} 1) {1,2,3,4,5} 2) {1,2,3,4,5} 3) {1,2,3,4,5} 4) {1,2,3,4,5} 5) {5,2,3,4,1} 6) {5,2,3,4,1} 7) {5,2,3,4,1} 8) {5,3,2,4,1} 9) {5,3,2,4,1} 10) {5,3,2,4,1} 11) {5,3,2,4,1} 12) {3,5,2,4,1} 13) {3,5,2,4,1} 14) {3,5,1,4,2} 15) {3,5,1,4,2} 16) {3,5,1,4,2} 17) {3,5,1,4,2} 18) {3,5,1,2,4} 19) {3,5,1,2,4} 20) {3,5,1,2,4} 21) {3,5,1,2,4} 22) {3,5,1,2,4} 23) Final: {3,5,1,2,4} 

So, in conclusion, it seems why the “why” is due to the fact that the problem is 0, as everyone says, but I'm still not sure.

Answer 4

Here you are not equal balances as you received in order

try the following:

 Array.Sort(numbers, (x, y) => x % 2 == y % 2 ? x < y ? 1 : -1 : x % 2 == 1 ? -1 : 1); 

Answer 5

here is how i understand it, based on the code, you can change it like:

 static void Main(string[] args) { int[] numbers = { 1, 2, 3, 4, 5 }; Array.Sort(numbers, OnComparison); } private static int OnComparison(int x, int y) { if (x%2 == y%2) return 0; if (x%2 == 1) return -1; return 1; } 

therefore arrary.sort, sorts by condition (OnComparison, which by return value), is not compared with int [] numbers. so 3 and 5 and 1 both return as -1 and as the definition of array.sort:

 This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved 

why did you get {3, 5, 1, 2, 4}