Doing a Binary Insertion Sort and my recursion is backfiring on me when I return my array. When I use the array : { 3, 1, 2, 4 } I get back 1,2,3,4. When I use the array : { 3, 7, 2, 4 } the recursion causes a StackOverflow.
Where am I going wrong? p.s Sorry about the console.writelines in my code it helps me check whats going on as I develop
The C# code is per the following snippet:
int[] a = new int[] { 3, 1, 2, 4 }; //Array to be sorted
int MiddlePointer = 0;
int LeftPointer = 0;
int RightPointer = 0;
int i = 1; //First number is 'sorted' so focus on second number
BinaryInsertSort(a, MiddlePointer, LeftPointer, RightPointer, i);
void BinaryInsertSort(int[] a, int MiddlePointer, int LeftPointer, int RightPointer, int i)
{
if (i == a.Length) //This should EXIT the algorithm once all of the numbers are sorted
{
return;
}
if (MiddlePointer == 0 & LeftPointer == 0 & RightPointer == 0) //If this is the first iteration, only the first number is 'sorted' and all of the pointers are the same
{
if (a[i] > a[MiddlePointer]) //If the next number is higher then just raise the RightPointer
{
RightPointer = i;
}
else //If the next number is lower, the 'sorted' values need to be 'shifted' one place to the right
{
RightPointer = i;
int temp = a[i];
for (int j = RightPointer; j > LeftPointer; j--)
{
a[j] = a[j - 1];
}
a[LeftPointer] = temp;
}
// i++; //At this point one number has been sorted
}
else
{
a = Testing(a, MiddlePointer, LeftPointer, RightPointer, i);
}
foreach (int x in a)
{
Console.WriteLine(x);
}
Console.ReadLine();
i++;
BinaryInsertSort(a, MiddlePointer, LeftPointer, RightPointer, i);
}
int[] Testing(int[] a, int MiddlePointer, int LeftPointer, int RightPointer,int i) //This method should find the space where the number should be inserted and return the updated array
{
if(MiddlePointer == RightPointer & RightPointer == LeftPointer)
{
Console.WriteLine($"{a[i]} has not been found");
if (a[i] > a[MiddlePointer])
{
RightPointer = i;
}
else
{
RightPointer = i;
int temp = a[i];
for (int j = RightPointer; j > 0; j--)//move up values
{
a[j] = a[j - 1];
}
a[LeftPointer] = temp;
}
}
else if (a[i] > a[MiddlePointer])
{
Console.WriteLine($"{a[i]} is greater than {a[MiddlePointer]}");
LeftPointer = MiddlePointer + 1;
MiddlePointer = (LeftPointer + RightPointer) / 2;
Testing(a, MiddlePointer, LeftPointer, RightPointer, i);
}
else if (a[i] < a[MiddlePointer])
{
Console.WriteLine($"{a[i]} is less than {a[MiddlePointer]}");
RightPointer = MiddlePointer - 1;
MiddlePointer = (LeftPointer + RightPointer) / 2;
Testing(a, MiddlePointer, LeftPointer, RightPointer, i);
}
return a;
}
Basically I went back to scratch and did a binary search first. This really helped in my previous attempt so I really made sure this worked before moving onto binary insertion sort. From this point I modified the code bit by bit and tried loads of different data sets to see if anything changed. Using breakpoints really helped. I needed to go through and 'follow' the changing variables to see where errors were being made. I also used Console.ReadLine and Console.WriteLine to follow where my logic was ending up. There are many loops in this code and the biggest problem was when I was using the recursion. I was using the recursion to find the 'gap' were the number should be inserted, this was the moment all of the pointers were the same. These pointers needed to constantly be updated and changed at the right moments. This was the most challenging part of the sort.
int i = 1;
int MiddlePointer = 0;
int LeftPointer = 0;
int RightPointer = 0;
BinaryInsertionSort.SortList(UnsortedNumberList, MiddlePointer, LeftPointer, RightPointer, i);
public void SortList(int[] a, int MiddlePointer, int LeftPointer, int RightPointer, int i)
{
if (i == a.Length)
{
Console.Write("Sorted list: ");
for (int x = 0; x < a.Length; x++) //output sorted list
{
if (x == a.Length - 1)
{
Console.Write($"{a[x]}");
}
else
{
Console.Write($"{a[x]}, ");
}
}
return;
}
if (a[MiddlePointer] == a[i])
{
RightPointer = i;
int temp = a[i];
for (int j = i; j > MiddlePointer + 1; j--)
{
a[j] = a[j - 1];
}
a[MiddlePointer + 1] = temp;
LeftPointer = 0;
MiddlePointer = i / 2;
i++;
SortList(a, MiddlePointer, LeftPointer, RightPointer, i);
}
else if (MiddlePointer == RightPointer & RightPointer == LeftPointer)
{
if (a[i] > a[MiddlePointer])
{
RightPointer = i;
int temp = a[i];
for (int j = i; j > MiddlePointer + 1; j--)
{
a[j] = a[j - 1];
}
a[MiddlePointer + 1] = temp;
}
else //If the next number is lower, the 'sorted' values need to be 'shifted' one place to the right
{
RightPointer = i;
int temp = a[i];
for (int j = i; j > MiddlePointer; j--)
{
a[j] = a[j - 1];
}
a[MiddlePointer] = temp;
}
LeftPointer = 0;
MiddlePointer = i / 2;
i++;
SortList(a, MiddlePointer, LeftPointer, RightPointer, i);
}
else if (a[i] > a[MiddlePointer])
{
LeftPointer = MiddlePointer + 1;
if (LeftPointer > RightPointer)
{
LeftPointer = RightPointer;
}
MiddlePointer = (LeftPointer + RightPointer) / 2;
SortList(a, MiddlePointer, LeftPointer, RightPointer, i);
}
else if (a[i] < a[MiddlePointer])
{
RightPointer = MiddlePointer - 1;
if (RightPointer < 0)
{
RightPointer = 0;
}
MiddlePointer = (LeftPointer + RightPointer) / 2;
SortList(a, MiddlePointer, LeftPointer, RightPointer, i);
}
}
}
UnsortedNumberList is an array of numbers. At first the pointers point at the first number at Array position 0. When the pointers are equal to each other then the position where the number is inserted has been found. From this point evaluate if the next number is higher or lower that this optimum position. Numbers will have to be juggled about hence the for loops with int j and variable temp. I hope this helps anyone else doing merge sort in the future.