CODEWITHSUNDEEP
c#algorithmsortingdesign-patternslogic
Khalil Khalaf
Khalil Khalaf

Reputation: 9407

Why I am getting two different results for the same design?

Quick question:

I have a bunch (cloud) of coordinates and I tend to find the four corner coordinates of the whole bunch. And by corner I mean:

MyDesiredResult = { SmallestX, BiggestY, BiggestX, SmallestY }

I use this Old Routine to get my values and it is the CORRECT ONE:

double smallestX = MyCloud[0].X;       // assing X of first element to my result controller
var tempCoordPoint = MyCloud[0];       // assign first element to my result controller

for (int i = 0; i < MyCloud.Count; i++)
{
    if (smallestX > MyCloud[i].X)      // find minimum X
    {
        smallestX = MyCloud[i].X;
        tempCoordPoint = MyCloud[i];
    }
}

MyResult.Add(tempCoordPoint);           // add to my list

However, I would need to do that Four Times (for the Four results). So I am trying to optimize my code by changing it to this New Routine which I use only once:

List<CoordPoint> MySortedList = MyCloud.Select(c => new CoordPoint { X = c.X, Y = c.Y, Z = c.Z, Color = c.Color }).ToList();

MySortedList.Sort((c1, c2) => c1.X.CompareTo(c2.X));     // sort on X
var temp = MySortedList[MySortedList.Count - 1];         // hold biggest X in a temp variable
MyResult.Add(MySortedList[0]);                           // add smallest X to my result

MySortedList.Sort((c1, c2) => c1.Y.CompareTo(c2.Y)); ;   // sort on Y
MyResult.Add(MySortedList[MySortedList.Count - 1]);      // add biggest Y to my result 
MyResult.Add(temp);                                      // add biggest X to my result
MyResult.Add(MySortedList[0]);                           // add smallest Y to my result

But it gives different results. I would want to show a sample input, current output and a desired output. I can skip the sample input (huge load) and show the results. Could anyone point me towards what I am doing wrong?

For the same input:

Result From Old Routine:

(0, 4), (15, 12), (23, 6), (19, 0)

Result From New Routine:

(0, 4), (18, 12), (23, 6), (18, 0)

enter image description here

Upvotes: 2

Views: 93

Answers (1)

Kyle
Kyle

Reputation: 6684

I will answer your question with another question:

What happens if two points have the same Y coordinate and that Y coordinate happens to be the minimum or maximum? Likewise for the X coordinate?

Let me illustrate with an example. Let's say you had these 4 points:

(0, 0), (1, 0), (0, 1), (1, 1)

Your original algorithm would return:

(0, 0), (0, 1), (1, 0), (0, 0)

Now let's say we took those original 4 points and shuffled them:

(1, 1), (0, 1), (1, 0), (0, 0)

If you run your original algorithm on that, you'll get this:

(0, 1), (1, 1), (1, 1), (1, 0)

According to you, the original algorithm is correct, but I've just given it the same set of points in two different orders and gotten two different answers. So which of the answers is correct? What is the actual expected result?

Now, there's a reason I didn't provide the results of your new algorithm and that's because I don't know what your new algorithm would produce. The reason why I don't know is that List<T>.Sort performs an unstable sort. That means that two elements that compare "equal" will not necessarily be left in order. So, if our input was (0, 0), (1, 0), (0, 1), (1, 1) all of the following are valid possibilities after trying to sort by X coordinate:

(0, 0), (0, 1), (1, 0), (1, 1)

(0, 1), (0, 0), (1, 0), (1, 1)

(0, 1), (0, 0), (1, 1), (1, 0)

(0, 0), (0, 1), (1, 1), (1, 0)

List<T>.Sort could produce any one of those. If you have more duplicate X coordinates, you'll have even more possible orderings. The reason this is called unstable is because the relative order of two equal elements (e.g. (0, 0) and (0, 1)) is not preserved after sorting. The sorting algorithm might swap their positions.

Upvotes: 2

Related Questions