программа быстрой сортировки сортирует, но никогда не останавливается - PullRequest
Новая
       14

программа быстрой сортировки сортирует, но никогда не останавливается

0 голосов
/ 22 марта 2020

программа, работающая

Я впервые реализую приложение быстрой сортировки в c#, и я думаю, что оно работает, но у него нет выхода, поэтому оно продолжает циклически повторяться Может кто-нибудь помочь и сказать мне, как исправить эту программу, не разрушая и не перестраивая технику?
и вот код: 

using System;
namespace quickso2
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] arr = { 12, 3, 1, 45, 16, 91, 21, 38 ,443,1212,53,2,1,0};
            sort ob = new sort();
            Console.WriteLine("before Sorting: ");
            for (int i = 0; i < arr.Length; i++)
            {
                Console.Write(arr[i]+ "  ");
            }

            ob.quicksorting(arr, -1, arr.Length - 1);
            Console.WriteLine("\n after Sorting: ");
            for (int i = 0; i < arr.Length; i++)
            {
                Console.Write(arr[i]+"  "  );
            }
        }
    }
    class sort
    {
        public int partition(int[] arr, int low, int high)
        {
            for (int i = low+1; i < high; i++)
            {

                if (arr[i] < arr[high])
                {
                    low++;
                    swap(ref arr[low], ref arr[i]);
                }
            }
            swap(ref arr[high], ref arr[low + 1]);
            //displaying sorting steps
            Console.WriteLine();
            for (int l = 0; l < arr.Length; l++) { 
            Console.Write(arr[l]+"  ");

            }
            return low + 1;
        }
        public void swap(ref int x, ref int y)
        {
            int temp = x;
            x = y;
            y = temp;
        }
         public void quicksorting(int[] arr, int low, int high)
        {
            int pivot ;
            if (low < high)
            {
                pivot = partition(arr, low, high);
                quicksorting(arr, -1, pivot - 1);
                quicksorting(arr, pivot + 1, arr.Length - 1);
            }
        }
    }
}

1 Ответ

0 голосов
/ 22 марта 2020

Проблема была связана с передачей индекса массива в вызовах функции быстрой сортировки.

Причины проблемы бесконечности l oop: 

  ob.quicksorting(arr, 0, arr.Length-1);          // In main method

  quicksorting(arr, -1, pivot - 1);               // Recursive call #1

  quicksorting(arr, pivot + 1, arr.Length - 1);   // Recursive call #2

Вот рабочее решение с обновленными индексами массива: 

using System;
namespace quickso2 {

  public class Program {
        public static void Main(string[] args) {
            int[] arr = { 12, 3, 1, 45, 16, 91, 21, 38 ,443,1212,53,2,1,0};
            sort ob = new sort();
            Console.WriteLine("before Sorting: ");
            for (int i = 0; i < arr.Length; i++) {
                Console.Write(arr[i]+ "  ");
            }
            ob.quicksorting(arr, 0, arr.Length-1);
            Console.WriteLine("\n after Sorting: ");
            for (int i = 0; i < arr.Length; i++) {
                Console.Write(arr[i]+"  "  );
            }
        }
  }

  class sort {
        public int partition(int[] arr, int low, int high) {
            int pivot = arr[low];
            while (true) {
                while (arr[low] < pivot) {
                    low++;
                }

                while (arr[high] > pivot) {
                    high--;
                }

                if (low < high) {
                    if (arr[low] == arr[high]) return high;
                    int temp = arr[low];
                    arr[low] = arr[high];
                    arr[high] = temp;
                }
                else {
                    return high;
                }
            }
        }

        public void quicksorting(int[] arr, int low, int high) {
            if (low < high) {
                int pivot = partition(arr, low, high);
                if (pivot > 1) {
                    quicksorting(arr, low, pivot - 1);
                }
                if (pivot + 1 < high) {
                    quicksorting(arr, pivot + 1, high);
                }
            }
        }
    }
}

Вывод: 

before Sorting: 
12  3  1  45  16  91  21  38  443  1212  53  2  1  0  
 after Sorting: 
0  1  1  2  3  12  16  21  38  45  53  91  443  1212
...