Quicksort Quicksort Stackoverflow

Question

لذا ، فقد كنت أحاول تنفيذ سريعة سريعة ، فقط لتعلم شيء منه ، ولكنه يولد أيضًا مجموعة stackoverflowexception ، لكن لا يمكنني العثور على ما هو السبب.

هل يمكن لأحد أن يعطيني فكرة؟

  public void Partition(List<int> valuelist, out List<int> greater, out List<int> lesser)
        {
            lesser = new List<int>();  // <-- Stackoverflow exception here!
            greater = new List<int>();

            if (valuelist.Count <= 1)
                return;

            pivot = valuelist.First();

            foreach (int Element in valuelist)
            {
                if (Element <= pivot)
                    lesser.Add(Element);
                else
                    greater.Add(Element);
            }
        }

        public List<int> DoQuickSort(List<int> list)
        {
            List<int> great;
            List<int> less;

            Partition(list, out great, out less);

            DoQuickSort(great);
            DoQuickSort(less);

            list.Clear();
            list = (List<int>)less.Concat(great);

            return list;

        }

Answer 1

أنت لا تضع أي شروط على مكالماتك العودية DoQuicksort, ، لذلك لن يتوقف أبدًا عن التكرار ، مما يؤدي إلى فائض مكدس. يجب أن تتصل فقط DoQuicksort في القائمة إذا كان يحتوي على أكثر من عنصر واحد.

تعديل: كما قال ويل في تعليقه ، هذا نهج بطيء للغاية مع "Quicksort". يجب أن تنظر إلى خوارزميات التقسيم في مكانها ، كما ذكر في ويكيبيديا مقالة Quicksort.

Answer 2

أنت تقوم بحلقة لا حصر لها هناك

  DoQuickSort(great);

تحتاج إلى طريقة للخروج من تلك الحلقة بعلم أو حالة

تعديل
سأضيف أنه في وضع تصحيح الأخطاء ، مع الإعداد الافتراضي ، لا يمكنك الوصول إلى ما بين 10000 و 16000 مكالمة متكررة قبل إلقاء الاستثناء وما بين 50000 و 80،000 عندما يكون في وضع الإصدار ، وكل ذلك يعتمد على الكود الفعلي.

إذا لعبت مع عدد كبير من القيم ، فقد تحتاج إلى إدارة نفسك هذه المكالمة العودية باستخدام أ كومة هدف.

نموذج رمز لمعرفة مقدار المكالمة قبل تعطلها ؛
(Debug ؛ 14،210 Call ، إصدار 80،071 مكالمة)

   static int s = 1;
    static void Main(string[] args)
    {
        o();
    }

    static void o()
    {
        s++;
        Console.WriteLine(s.ToString());
        o();
    }

Answer 3

أعتقد أن إحدى المشكلات في التعليمات البرمجية التي تحتفظ بها القيمة المحورية عند تقسيم القائمة. هذا يعني أنك ستواجه موقفًا تقسم فيه جميع القيم إلى أكبر أو أقل ، وسيتوقف التقسيم عن العمل. لن يسمح لك هذا بشكل فعال بتقسيم إحدى القوائم أي شيء ، وبالتالي فإن حالة الخروج في طريقة التقسيم لا ترضي أبدًا.

يجب عليك تحديد قيمة محورية ، قم بإزالة العنصر المحوري من القائمة (هذا الجزء مفقود في الكود الخاص بك) ، ويضعه في قوائم أكبر وأقل ، وفرز تلك (متكررة) ، ثم تسلسل القائمة الأقل ، العنصر المحوري (هذا أيضًا ، بطبيعة الحال ، مفقود في الكود الخاص بك) والقائمة الأكبر .

يمكنني نشر عينة محدثة ، تعمل ، ولكن بما أنك في "وضع التعلم" ، سأبقيه لنفسي حتى تطلب ذلك :)