How to quick sort characters/string input in C#?

Question

I was tasked in implementing the different Sorting Algorithms: Quick Sort and Merge Sort.

I manage to get Quick Sort but I noticed that it is giving me a different answer. For example the Bubble Sort will sort "program" as "agmoprr" but my Quick Sort will sort it as "agomprr". The Bubble Sort was already given, so i think I missed something with Quick Sort.

Can someone help me check where did I went wrong? Thank you

    public class QuickSort : ISortStrategy
{
    char[] myArray;

    public string Sort(string input)
    {

        if (input == null || input.Length == 0 || input.Length == 1)
        {
            return null;
        }
        int length = input.Length;
        int low = 0, high = length - 1;
        this.myArray = input.ToCharArray();

        quickSort(low, high);
        return new string(myArray);

    }

    public void quickSort(int low, int high)
    {

        int i = low;
        int j = high;
        char tmp;

        int pivot = (low + high) / 2;

        while (i <= j)
        {
            while (myArray[i] < myArray[pivot])
            {
                i++;
            }
            while (myArray[j] > myArray[pivot])
            {
                j--;
            }

            if (i <= j)
            {
                tmp = myArray[i];
                myArray[i] = myArray[j];
                myArray[j] = tmp;
                i++;
                j--;
            }
        }

        if (low < j)
        {
            quickSort(low, j);
        }
        if (i < high)
        {
            quickSort(i, high);
        }
    }
}

Interface

    public interface ISortStrategy
{
    string Sort(string input);
}

Main Class

  using System;

/**
 * Instructions:
 * Use the Strategy Pattern to implement the different Sorting Algorithms: BubbleSort (given as an example), Quick Sort and Merge Sort
 */
class Program
{
    static void Main(string[] args)
    {
        Console.WriteLine("Enter Sort Strategy (bubblesort, quicksort, mergesort). Defaults to bubblesort");
        ISortStrategy strategy = default;

        var input = Console.ReadLine();
        input = input.ToLower();

        if (input == "bubblesort")
        {
            strategy = new BubbleSort();
        }

        // Implement other strategies here based on the strategy inputted by the user
        if (input == "quicksort")
        {
            strategy = new QuickSort();
        }

        if (input == "mergesort")
        {
            strategy = new MergeSort();
        }

        Console.WriteLine("Enter String to Sort");
        var value = Console.ReadLine();

        Console.Write("The sorted string is: " + strategy.Sort(value));

        Console.ReadKey();
    }
}

You know how to debug code? Currently it feels like you are just guessing how your code works. You should try to debug it and check what is happening against your expectation. A good starter for your debugging session to look at would be the two inner while loops in the quickSort method. What should happen if the value you are looking at is equal to the pivot value? — Ralf
– Ralf, Commented Mar 14, 2022 at 18:21
Thanks will do, actually I haven't tried debugging codes before since we rarely use algorithms and most of it is already given in java. I usually translate algorithm from java to the required language. — lance2k
– lance2k, Commented Mar 15, 2022 at 13:07

Nicholas Carey · Accepted Answer · 2022-03-14 19:05:33Z

1

If you look at the Quicksort algorithm, you're not actually implementing it. Try something like this:

public class QuickSort : ISortStrategy
{

  public string Sort(string input)
  {
    if (string.IsNullOrEmpty(input)) return input;
    
    char[] chars = input.ToCharArray();
    this.Sort(chars, 0, unsorted.Length - 1);
    
    string output = new string(chars);
    return output;
  }
  
  private void Sort(char[] A, int lo, int hi)
  {
    if (lo >= 0 && hi >= 0 && lo < hi)
    {
      int p = partition(A, lo, hi);
      this.Sort(A, lo, p); // note: the pivot is now included
      this.Sort(A, p + 1, hi);
    }
    return;
  }
  
  private int partition(char[] A, int lo, int hi)
  {
    char pivot = A[ (lo+hi) / 2 ]; // integer division instead of floor(): we know that lo+hi is never negative.
    int i = lo - 1;
    int j = hi + 1;
    
    // loop forever
    while (true)
    {
      // Move the left index to the right at least once,
      // and while the element at the left index is less than the pivot.
      do
      {
        ++i;
      } while ( A[i] < pivot );
      
      // Move the right index to the left at least once,
      // and while the element at the right index is greater than the pivot
      do
      {
        ++j;
      } while ( A[j] > pivot );
      
      // if the indices converged (or crossed) return
      if (i >= j) return j;
      
      // swap A[i] and A[j]
      char temp = A[i];
      A[i] = A[j];
      A[j] = temp;
      
    }
    
  }
  
}

answered Mar 14, 2022 at 19:05

Nicholas Carey

75.1k16 gold badges96 silver badges138 bronze badges

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

1 Comment

lance2k Over a year ago

Thank you, but I'm having IndexOutOfRangeException on: while (A[j] > pivot); debugging shows that j=8 so I change it to while (A[j-2] > pivot); since A[] only has [0-6] index. But it will still become OutOfRange after the next iteration. I also change unsorted.Length - 1 to input.Length -1.

blepsters · Accepted Answer · 2022-08-09 04:23:41Z

0

it should be

 if (low < j)
        {
            quickSort(low, i-1);
        }

answered Aug 9, 2022 at 4:23

blepsters

32 bronze badges

Collectives™ on Stack Overflow

How to quick sort characters/string input in C#?

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related