فرز سريع و استثناء تجاوز سعة مكدس

Question

أعتقد أن فرز سريع في بعض الظروف الخاصة قد يسبب استثناء تجاوز سعة مكدس.

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

هنا هو بلدي نسخة من نوع سريع (دلفي):

procedure QuickSort(lLowBound, lHighBound: integer; lCompare: TListSortCompare;
  lSwap: TListSortSwap);

  procedure Sort(lLowIndex, lHighIndex: integer);
  var
    lLeft: Integer;
    lRight: Integer;
    lPivot: Integer;
    lLeftCompare: Integer;
    lRightCompare: Integer;
  begin
    repeat
      lLeft := lLowIndex;
      lRight := lHighIndex;
      lPivot := (lLowIndex + lHighIndex) div 2; //the pivot as the element in the middle
      //lPivot := lLowIndex + Random(lHighIndex - lLowIndex + 1); //the pivot chosen randomly
      repeat
        lLeftCompare := lCompare(lLeft, lPivot);
        while lLeftCompare < 0 do
        begin
          Inc(lLeft);
          lLeftCompare := lCompare(lLeft, lPivot);
        end;
        lRightCompare := lCompare(lRight, lPivot);
        while lRightCompare > 0 do
        begin
          Dec(lRight);
          lRightCompare := lCompare(lRight, lPivot);
        end;

        if lLeft <= lRight then
        begin
          if not ((lLeftCompare = 0) and (lRightCompare = 0)) then
          begin
            lSwap(lRight, lLeft);

            if lPivot = lLeft then
              lPivot := lRight
            else if lPivot = lRight then
              lPivot := lLeft;
          end;
          Inc(lLeft);
          Dec(lRight);
        end;
      until lLeft > lRight;

      if (lLowIndex < lRight) then
        Sort(lLowIndex, lRight);

      lLowIndex := lLeft;
    until lLeft >= lHighIndex;
  end;

begin
  if lHighBound > lLowBound then
    Sort(lLowBound, lHighBound);
end;

شكرا على المشورة الخاصة بك في وقت مبكر!

ماريوس.

Answer 1

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

باستخدام عنصر عشوائي يعني التنكس يمكن أن يحدث إلا من خلال حظ سيئ نقي (على افتراض أن RNG غير قابل للتنبؤ به مهاجم افتراضي)، لذلك فهو تكتيك جيد. تحسين مزيد من التحسن الذي يقلل بشكل كبير من احتمال التعرض له هذا الحظ السيئ هو استخدام الوسيط 3 (أو 5، أو أكثر) العناصر المختارة بشكل عشوائي، ولكن يجب أن يكون مرجحا ضد التعقيد الإضافي وتوقيت الجري هذا.

Answer 2

إحتمالات طريقة لتحسين الكفاءة هو اختيار 3 عناصر عشوائية واستخدام القيمة المتوسطة (واحد هو أن لا أكبر ولا أقل).

يمكنك أيضا استخدام كومة من الوثائق لدفع البوب حدود والكتابة حلقة بدلا من جعل دعوات متكررة (أيضا فإنه سيتم استخدام ذاكرة أقل منذ مؤشر إلى الصفيف لن تحتاج إلى أن تكون منسوخة على جميع المكالمات).

تحرير:لقد لاحظت أن الإجراءات الداخلية لا تأخذ المؤشر كما المعلمة حتى ننسى هذا الجزء ^_^ على أي حال ، فإن الإطار المكدس لديه معلومات أكثر من مجرد المعلمات وظيفة, لذلك سوف تكون أكثر كفاءة الذاكرة (و إن النقطة الرئيسية هي أن الكومة كانت تكدس البيانات المخصصة عادة ما تكون أكبر من عملية المكدس).

Answer 3

شكرا لإجاباتك.

Fortran، شكرا على اقتراحاتكم المتعلقة بإجراء طريقة غير متكررة. استنادا إليهم، تمكنت من صنع فرز سريع للتكتوري ويبدو أنه يعمل بشكل صحيح :).

إليك الرمز:

procedure QuickSortI(lLowBound, lHighBound: integer; lCompare: TListSortCompare;
  lSwap: TListSortSwap);
var
  lLeft: Integer;
  lRight: Integer;
  lPivot: Integer;
  lLeftCompare: Integer;
  lRightCompare: Integer;
  lStack: array of integer;
  lStackLen: integer;
begin
  if lHighBound > lLowBound then
  begin
    lStackLen := 2;
    SetLength(lStack, lStackLen);
    lStack[lStackLen - 1] := lLowBound;
    lStack[lStackLen - 2] := lHighBound;

    repeat
      lLowBound := lStack[lStackLen - 1];
      lHighBound := lStack[lStackLen - 2];
      SetLength(lStack, lStackLen - 2);
      Dec(lStackLen, 2);

      lLeft := lLowBound;
      lRight := lHighBound;
      lPivot := (lLowBound + lHighBound) div 2;
      repeat
        lLeftCompare := lCompare(lLeft, lPivot);
        while lLeftCompare < 0 do
        begin
          Inc(lLeft);
          lLeftCompare := lCompare(lLeft, lPivot);
        end;
        lRightCompare := lCompare(lRight, lPivot);
        while lRightCompare > 0 do
        begin
          Dec(lRight);
          lRightCompare := lCompare(lRight, lPivot);
        end;

        if lLeft <= lRight then
        begin
          if not ((lLeftCompare = 0) and (lRightCompare = 0)) then
          begin
            lSwap(lRight, lLeft);

            if lPivot = lLeft then
              lPivot := lRight
            else if lPivot = lRight then
              lPivot := lLeft;
          end;
          Inc(lLeft);
          Dec(lRight);
        end;
      until lLeft > lRight;

      if (lHighBound > lLeft) then
      begin
        Inc(lStackLen, 2);
        SetLength(lStack, lStackLen);
        lStack[lStackLen - 1] := lLeft;
        lStack[lStackLen - 2] := lHighBound;
      end;

      if (lLowBound < lRight) then
      begin
        Inc(lStackLen, 2);
        SetLength(lStack, lStackLen);
        lStack[lStackLen - 1] := lLowBound;
        lStack[lStackLen - 2] := lRight;
      end;

    until lStackLen = 0;
  end;
end;

آمل أن أطبقها بطريقة مثالية. لقد استخدمت مجموعة ديناميكية لتخزين حدود الفرز (كل زوج من العناصر هو الحد الأدنى والمرتفع).

يبدو أن الطريقة التابعة هذه أبطأ قليلا من الشخص العريز، لكنني أعتقد أنه لا يهم كثيرا.

إذا لاحظت خطأ أو تعرف طريقة لتحسين الطريقة، فسوف أكون ممتنا لو سمحت لي أن أعرف.

شكرا!

ماريوس.

Answer 4

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

تطبيق مكدس صريح الخاص بك أبطأ ويعاني من نفس المشكلة (على الرغم من أنه الآن هو كومة بدلا من المكدس).

شيء آخر مفقود هو التبديل للإدراج فرز عندما يكون الضوئي صغيرا (5-25 عناصر). إلقاء نظرة أيضا على أسئلة QuickSort Dual-Pivot على هذا الموقع.