Реализация MergeSort (), возвращающая исходный несортированный массив - PullRequest
Новая
       4

Реализация MergeSort (), возвращающая исходный несортированный массив

0 голосов
/ 29 августа 2018

Каждый раз, когда я запускаю это, он возвращает несортированный массив. Я поместил некоторый код, чтобы сигнализировать мне, где что-то происходит, а что нет, но он выглядит и ВИДИТСЯ, как будто все работает нормально, но на самом деле он ничего не сортирует. 

 public static int[] MergeSort(int[] array)
    {
        if(array.Length <= 1)
        {
            return array;
        }
        (int[], int[]) p = SplitArray(array);
        int[] left = MergeSort(p.Item1);
        int[] right = MergeSort(p.Item2);
        return Merge(left, right);


    }



    public static int[] Merge(int[] low, int[] high)
    {
        int[] middle = new int[(low.Length + high.Length + 1)];
        int count = 0;
        foreach (int item in low)
        {
            Console.WriteLine("low: " + item + ',');
        }
        foreach (int item in high)
        {
            Console.WriteLine("high: " + item + ',');
        }
        int low_index = 0;
        int high_index = 0;
        while (low_index < low.Length && high_index < high.Length)
        {
            if(low[low_index] < high[high_index])
            {
                middle.SetValue(low[low_index], count);
                low_index++;
                count++;
                Console.WriteLine("Low inserted.");
            }
            else
            {
                middle.SetValue(high[high_index], count);
                high_index++;
                count++;
                Console.WriteLine("High inserted.");
            }

        }
        if (low_index == low.Length)
        {
            high.CopyTo(middle, high_index);
        }
        else
        {
            low.CopyTo(middle, low_index);
        }

        return middle;
    }


    public static (int[], int[]) SplitArray(int[] k)
    {
        int MAXINDEX = k.Length - 1;
        int count = 0;
        int[] a = new int[(MAXINDEX / 2)];
        int[] b = new int[(MAXINDEX / 2)];

        for (int i = 0; i < (MAXINDEX / 2); i++)
        {
            a[i] = k[i];
        }
        for (int i = ((MAXINDEX / 2) + 1); i < MAXINDEX; i++)
        {
            b[count] = k[i];
            count++;

        }
        return (a, b);

    }

Я понятия не имею, где я иду не так. Я мог бы просто упускать из виду что-то очень усталое каждый раз, когда возвращаюсь к этому. Я в основном распечатываю кучу вещей, которые ДОЛЖНЫ происходить с помощью консоли, и все это кажется правильным, и я схожу с ума.

Ответы [ 2 ]

0 голосов
/ 29 августа 2018

Вот, пожалуйста: код был полон ошибок, длина массивов не совпадала, и вы каждый раз переопределяли свой средний массив. 

namespace MainClass
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] array = { 3, 5, 15, 22, 12, 15, 23 };

            int[] x = MergeSort(array);

            foreach (int i in x)
            {
                Console.WriteLine(i);
            }

            Console.ReadKey();
        }
    public static int[] MergeSort(int[] array)
    {
        if (array.Length <= 1)
        {
            return array;
        }
        (int[], int[]) p = SplitArray(array);
        int[] left = MergeSort(p.Item1);
        int[] right = MergeSort(p.Item2);
        return Merge(left, right);


    }



    public static int[] Merge(int[] low, int[] high)
    {
        int[] middle = new int[(low.Length + high.Length)];
        int count = 0;
        foreach (int item in low)
        {
            Console.WriteLine("low: " + item + ',');
        }
        foreach (int item in high)
        {
            Console.WriteLine("high: " + item + ',');
        }
        int low_index = 0;
        int high_index = 0;
        while (low_index < low.Length && high_index < high.Length)
        {
            if (low[low_index] < high[high_index])
            {
                middle.SetValue(low[low_index], count);
                low_index++;
                count++;
                Console.WriteLine("Low inserted.");
            }
            else
            {
                middle.SetValue(high[high_index], count);
                high_index++;
                count++;
                Console.WriteLine("High inserted.");
            }

        }
        while (high_index < high.Length)
        {
            middle[low_index + high_index] = high[high_index++];
        }
        while (low_index < low.Length)
        {
            middle[low_index + high_index] = low[low_index++];
        }

        return middle;
    }


    public static (int[], int[]) SplitArray(int[] k)
    {
        int[] a = new int[((k.Length + 1) / 2)];
        int[] b = new int[(k.Length / 2)];

        for (int i = 0; i < a.Length; i++)
        {
            a[i] = k[i];
        }
        for (int i = 0; i < b.Length; i++)
        {
            b[i] = k[i + a.Length];
        }
        return (a, b);

    }

}
0 голосов
/ 29 августа 2018

Хорошо, я думаю, что главная ошибка, это были функции с high.copyTo (...) и low.copyTo (...) с неправильной индексацией

Вот полный исходный код (проверено): 

public static int[] MergeSort(int[] array)
{
  if (array.Length <= 1)
  {
    return array;
  }

  Tuple<int[], int[]> p = SplitArray(array);

  int[] left = MergeSort(p.Item1);
  int[] right = MergeSort(p.Item2);

  return Merge(left, right);
}

public static int[] Merge(int[] low, int[] high)
{
  int[] middle = new int[low.Length + high.Length];
  int count = 0;
  foreach (int item in low)
  {
    Console.WriteLine("low: " + item + ',');
  }
  foreach (int item in high)
  {
    Console.WriteLine("high: " + item + ',');
  }
  int low_index = 0;
  int high_index = 0;
  while (low_index < low.Length && high_index < high.Length)
  {
    if (low[low_index] < high[high_index])
    {
      middle[count] = low[low_index];
      low_index++;
      count++;
      Console.WriteLine("Low inserted.");
    }
    else
    {
      middle[count] = high[high_index];
      high_index++;
      count++;
      Console.WriteLine("High inserted.");
    }

  }
  if (low_index == low.Length)
  {
    for (; count < middle.Length; count++)
    {
      middle[count] = high[high_index];
      high_index++;
    }

    // alternate: Array.Copy(high, high_index, middle, count, middle.Length - count);
  }
  else
  {
    for (; count < middle.Length; count++)
    {
      middle[count] = low[low_index];
      low_index++;
    }
    // alternate: Array.Copy(low, low_index, middle, count, middle.Length - count);
  }

  return middle;
}

public static Tuple<int[], int[]> SplitArray(int[] k)
{
  int half = k.Length / 2;
  int[] a = new int[half];
  int[] b = new int[k.Length - half];

  int k_index = 0;

  for (int i = 0; i < a.Length; i++)
  {
    a[i] = k[k_index];
    k_index++;
  }

  for (int i = 0; i < b.Length; i++)
  {
    b[i] = k[k_index];
    k_index++;
  }

  return new Tuple<int[], int[]>(a, b);
}
...