Update: Thanks @AdrianHHH for the tips and @steveOh for the fix on my right array and everyone for the advice. It's running now but it is giving me a different answer. For example the Bubble Sort will sort "program" as "agmoprr" but my Merge Sort will sort it as "gpramro". The Bubble Sort was already given as a sample, and I tested the java program for input: "program" output: "program" which is not I wanted but if you put spaces in between it would sort as "agmoprr" which is the same as the bubble sort.
I'm currently debugging but I really need help, its my 2nd time debugging as we rarely do algorithms implementation. Also, thank you everyone for checking and correcting my mistakes.
String Merge Sort in Java that I'm trying to convert to C#:
public static void mergeSort(List<String> list){
// need base case - should be a single if statement
if (list.size() > 1){
List<String> left = new LinkedList<>(list.subList(0, list.size() / 2));
List<String> right = new LinkedList<>(list.subList(list.size() / 2, list.size()));
// recursively sort the two halves
mergeSort(left);
mergeSort(right);
// merge the sorted left and right subLists together
merge(list, left, right);
}
}
public static void merge(List<String> result, List<String> left, List<String> right){
int i1 = 0; // index for left
int i2 = 0; // index for right
for (int i = 0; i < result.size(); i++) {
if (i2 >= right.size() || (i1 < left.size() && left.get(i1).compareToIgnoreCase(right.get(i2)) < 0)){
result.remove(i);
result.add(i, left.get(i1));
i1++;
} else {
result.remove(i);
result.add(i, right.get(i2));
i2++;
}
}
}
Converted String Merge Sort in C#: (giving different output "gpramro")
public class MergeSort : ISortStrategy
{
public string Sort(string input)
{
var result = "";
int size = (input.Length % 2 == 0) ? input.Length / 2 : (input.Length + 1) / 2;
if (input.Length > 1)
{
char[] left = input.Substring(0, input.Length / 2).ToCharArray();
char[] right = input.Substring(input.Length / 2,input.Length - (input.Length / 2)).ToCharArray();
// recursively sort the two halves
Sort(left.Length.ToString());
Sort(right.Length.ToString());
// merge the sorted left and right subLists together
result = merge(input, left, right);
}
return result;
}
public string merge(string result, char[] left, char[] right)
{
int i1 = 0; // index for left
int i2 = 0; // index for right
var theString = result;
var aStringBuilder = new StringBuilder(theString);
for (int i = 0; i < aStringBuilder.Length; i++)
{
if (i2 >= right.Length || (i1 < left.Length && left.GetValue(i1).ToString().CompareTo(right.GetValue(i2).ToString()) < 0))
{
aStringBuilder.Remove(i, 1);
aStringBuilder.Insert(i, left.GetValue(i1).ToString());
i1++;
}
else
{
aStringBuilder.Remove(i, 1);
aStringBuilder.Insert(i, right.GetValue(i2).ToString());
i2++;
}
}
theString = aStringBuilder.ToString();
return theString;
}
}
Interface - The Interface and bubblesort is already given, so if I change the interface then I have to change the bubblesort and quicksort, but both are already implemented.
public interface ISortStrategy
{
string Sort(string input);
}
Bubblesort - Given as a sample
public string Sort(string input)
{
var result = "";
var arr = input.ToCharArray();
char temp;
for (int write = 0; write < arr.Length; write++)
{
for (int sort = 0; sort < arr.Length - 1; sort++)
{
if (arr[sort] > arr[sort + 1])
{
temp = arr[sort + 1];
arr[sort + 1] = arr[sort];
arr[sort] = temp;
}
}
}
for (int i = 0; i < arr.Length; i++)
result += arr[i];
return result;
}
Quicksort - Done using the given interface
public string Sort(string input)
{
char[] charactersToSort = input.ToCharArray();
int low = 0;
int high = charactersToSort.Length - 1;
quickSort(charactersToSort, low, high);
return new string(charactersToSort);
}
Let's take the example input string of "program" as you have provided.
The first change I made is switching from a mixutre of char arrays and strings to purely Lists of chars. One of the problems you were facing came from when you called Sort again, you passed in the length of the left and right arrays rather than the arrays themselves. This has been corrected in the provided code.
The general structure of this code was found here, I simply converted it to a strings version.
The new ISortStrategy.cs:
public interface ISortStrategy
{
List<char> Sort(List<char> input);
}
The new MergeSort.cs:
public class MergeSort : ISortStrategy
{
public List<char> Sort(List<char> unsorted)
{
if (unsorted.Count <= 1)
return unsorted;
List<char> left = new();
List<char> right = new();
int middle = unsorted.Count / 2;
for (int i = 0; i < middle; i++)
left.Add(unsorted[i]);
for (int i = middle; i < unsorted.Count; i++)
right.Add(unsorted[i]);
left = Sort(left);
right = Sort(right);
return Merge(left, right);
}
private List<char> Merge(ICollection<char> left, ICollection<char> right)
{
List<char> result = new();
while (left.Count > 0 || right.Count > 0)
{
switch (left.Count)
{
case > 0 when right.Count > 0:
{
if ((left.First() % 32) <= (right.First() % 32))
{
result.Add(left.First());
left.Remove(left.First());
}
else
{
result.Add(right.First());
right.Remove(right.First());
}
break;
}
case > 0:
result.Add(left.First());
left.Remove(left.First());
break;
default:
{
if (right.Count > 0)
{
result.Add(right.First());
right.Remove(right.First());
}
break;
}
}
}
return result;
}
}
New implementation of sorting system:
string result = new(new MergeSort().Sort("program".ToList()).ToArray());
Console.WriteLine(result);
When using this code with the input string "program" the output should be "agmoprr"