How to implement merge sort on characters/string input in C#?

Question

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);
}

Please read the minimal reproducible example page and particularly the bottom section about debugging small programs. — AdrianHHH
– AdrianHHH, Commented Mar 15, 2022 at 18:02
A string is inherently a char[], for example you can forEach (char x in theString) directly. — radarbob
– radarbob, Commented Mar 15, 2022 at 18:51
@radarbob "A string is inherently a char[]" - no it isn't: Char[] is mutable, but String is immutable: so you can't set individual characters in a String value, so String is more like IReadOnlyList<Char> (or rather: ReadOnlySpan<Char>). — Dai
– Dai, Commented Mar 15, 2022 at 20:32
OOps, I mischaracterized the thing. I was going after the idea of not necessarily needing to convert a string into a char[ ] type variable. But the thing is being mutated - sorted, so yeah "strings are immutable", like, it's in the bible. FWIW here we read: A String object is a sequential collection of System.Char objects that represent a string; a System.Char object. Also,String implements IEnumerable<char> — radarbob
– radarbob, Commented Mar 16, 2022 at 2:45

SteveOhByte · Accepted Answer · 2022-03-16 03:05:20Z

1

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"

edited Mar 16, 2022 at 3:05

answered Mar 15, 2022 at 18:06

SteveOhByte

967 bronze badges

Sign up to request clarification or add additional context in comments.

10 Comments

radarbob Over a year ago

length of 13 + 1 / 2 => is 13, not 7. Integer arithmetic with operator precedence (no parenthesis) is doing this: 13 + 0.

SteveOhByte Over a year ago

Oops, thanks for catching that @radarbob, corrected my answer.

lance2k Over a year ago

ah ok, i thought it was substring(startIndex, endIndex) my original code was char[] right = input.Substring(input.Length / 2, input.Length).ToCharArray();

lance2k Over a year ago

So to get the second parameter, I have to check if its odd and add +1 to it if it is? like input.Substring(input.Length / 2, input.Length/2 +1).ToCharArray()

lance2k Over a year ago

I change add int size = (input.Length % 2 == 0) ? input.Length / 2 : (input.Length + 1) / 2; then change it to char[] right = input.Substring(input.Length / 2, size).ToCharArray(); now I'm having stack overflow

|

Collectives™ on Stack Overflow

How to implement merge sort on characters/string input in C#?

1 Answer 1

10 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

10 Comments

Your Answer

Sign up or log in

Post as a guest

Related