koobas.hobune.stream
merge sort crash Unity
Basically I needed to sort a list of raycasthit base on distance, and I was gonna write my own merge sort. I tried to test the merge sort with a list of ints, and the moment i hit play, unity crashed. Heres the code:
void sort (List<int> tempH)
{
if (tempH.Count > 1) {
int mid = tempH.Count / 2;
List<int> left = new List<int> ();
popullate (0, mid-1, left, tempH);
sort (left);
List<int> right = new List<int> ();
popullate (mid, tempH.Count - 1, right, tempH);
sort (right);
tempH = merge (left, right);
} else {
return;
}
}
List<int> merge (List<int> left, List<int> right)
{
List<int> temp = null;
int i = 0;
int j = 0;
while (i < left.Count || j < right.Count) {
if (i < left.Count && j < right.Count) {
if (left [i] < right [j]) {
temp.Add (right [j]);
j++;
} else {
temp.Add (left [i]);
i++;
}
} else if (i < left.Count) {
temp.Add (left [i]);
i++;
} else if (j < right.Count) {
temp.Add (right [j]);
j++;
}
}
return temp;
}
void popullate (int leftIndex, int rightIndex, List<int> list, List<int> oList)
{
for (int i = leftIndex; i <= rightIndex; i++) {
list.Add (oList [i]);
}
}
To sort the list you could also use the BinarySearch function:
void sort (List<int> tempH)
{
List<int>sorted = new List<int>(tempH.Count);
for (int i = 0; i < tempH.Count; i++)
{
int index = sorted.BinarySearch(tempH[i]);
// is not in the list
if (index < 0 )
{
sorted.Insert(~index, tempH[i]); // the sign is supposed to be a swung dash (tilde)
}
// is already in the list (double entries possible)
else
{
sorted.Insert(index, tempH[i];
}
}
}
Sorry for any typos.
I don't understand the difference between ~index and index.
Also, I am more interested in making my own sort. Although things are working with the list.sort() method from .Net, I much rather try to code my own sort :)
That's why I added this as a comment and not an answer :)
About ~index (msdn):
"Taking the bitwise complement (the ~ operator in C#) of this negative number produces the index of the first element in the list that is larger than the search string, and inserting at this location preserves the sort order."
It looks like your problem is at line 27. You set your temp list to null, but then never initialize it before trying to add elements to it on line 35. Change it to List<int> temp = new List<int>(); and that should solve your problem.
yeah, I saw an obvious error and stopped looking further. I took a second look and your sort function and saw another problem. Look at the case where the List you're sending in has 2 elements. Subdividing into the left side will work, with 0 sent as the starting point and 1 sent as the mid point. This should run fine.
But When it tries to do the right side, it will send 2 as the starting point, which is already beyond the length of the list.
Actually since his two int values are indices he want to pass 0 and 0 in the case of two elements. So it should be either something like that:
popullate (0, mid-1, left, tempH); // "right" needs to be inclusive
// ...
popullate (mid, tempH.Count - 1, right, tempH); // "right" needs to be inclusive
Or the limit of the loop inside "popullate" need to be adjusted and then you have to use:
popullate (0, mid, left, tempH); // "right" needs to be exclusive
// ...
popullate (mid, tempH.Count, right, tempH); // "right" needs to be exclusive
so for the first case the original code of "popullate" will work if the calls are changed like this. For the second case the for loop would look like this:
for (int i = leftIndex; i < rightIndex; i++) {
Anyways, using arrays will be much more efficient. btw: You know that the List class already has a quicksort method? You can sort a list with RaycaseHit values like this:
List<RaycastHit> list = new List<RaycastHit>();
Vector3 refPos = transform.position;
list.Sort((a, b) => (a.point- refPos).sqr$$anonymous$$agnitude.CompareTo((b.point - refPos).sqr$$anonymous$$agnitude));
If you don't like lambda expressions you could also use
Vector3 refPos; // class variable
int CompareToRef(RaycastHit a, RaycastHit b)
{
float distA = (a - refPos).sqr$$anonymous$$agnitude;
float distB = (b - refPos).sqr$$anonymous$$agnitude;
return distA.CompareTo(distB);
}
// ...
List<RaycastHit> list = new List<RaycastHit>();
refPos = transform.position; // set the class variable
list.Sort(CompareToRef);
http://www.codeproject.com/Articles/79040/Sorting-Algorithms-Codes-in-C-NET Unless you're deter$$anonymous$$ed to do it yourself, this page lists the merge sort algorithm in c# using a generic list.
Here is my final code, turns out when I assigned tempH = merge(left, right), I wasn't changing the list but rather the parameter passed on. $$anonymous$$ade the sort function return the list now and things work out :) Here is the code, it is meant be raycasthit distance sorting, but it should work for other stuff too:
List<RaycastHit> sort (List<RaycastHit> tempH)
{
if (tempH.Count > 1) {
int mid = tempH.Count / 2;
List<RaycastHit> left = new List<RaycastHit> ();
for (int i = 0; i < mid; i++)
left.Add (tempH [i]);
left = sort (left);
List<RaycastHit> right = new List<RaycastHit> ();
for (int i = mid; i < tempH.Count; i++)
right.Add (tempH [i]);
right = sort (right);
tempH = merge (left, right);
}
return tempH;
}
List<RaycastHit> merge (List<RaycastHit> left, List<RaycastHit> right)
{
List<RaycastHit> temp = new List<RaycastHit> ();
int i = 0;
int j = 0;
while (i < left.Count || j < right.Count) {
if (i < left.Count && j < right.Count) {
if (left [i].distance < right [j].distance) {
temp.Add (right [j]);
j++;
} else {
temp.Add (left [i]);
i++;
}
} else if (i < left.Count) {
temp.Add (left [i]);
i++;
} else if (j < right.Count) {
temp.Add (right [j]);
j++;
}
}
return temp;
}
You have an infinite recursion due to a wrong limit in line 58:
for (int i = leftIndex; i <= rightIndex; i++) {
In case there are two elements in your list mid will be 1 ( == 2 / 2). For your left list your leftIndex is 0 and rightIndex is 1. Therefore you copy both elements to the new list and doing that until you get a stackoverflow.
LazyElephant is right about your temp list, however that would just raise a null reference exception and terminate the execution. I haven't checked if the rest of your implementation is "correct". However what i can say is that it's going to be very inefficient. You create a lot of garbage
The first implementation on the wiki will be much faster and doesn't create as much garbage. It only requires a single temp array which has the same size as the source array.
Apart from creating way too much temp lists, each of those temp lists will have to resize when you add elements. So the first lists which contains many elements will resize a couple of times. Each resize will create additional garbage and the temp list might even be larger than necessary.
