فرز الخوارزمية مع أقل عدد من العمليات

Question

ما هي خوارزمية الفرز مع أقل عدد من العمليات؟ أحتاج إلى تنفيذها في HLSL كجزء من تأثير تظليل البكسل V2.0 لـ WPF ، لذلك يجب أن يكون هناك عدد صغير جدًا من العمليات ، مع الأخذ في الاعتبار قيود Pixel Shader. أحتاج إلى فرز 9 قيم ، وتحديداً البكسل الحالي وجيرانه.

Answer 1

إما تريد استخدام نوع الإدراج أو نوع Radix. فيما يلي بعض تطبيقات C ++:

نوع راديكس

void radix (int byte, long N, long *source, long *dest)
{
  long count[256];
  long index[256];
  memset (count, 0, sizeof (count));
  for ( int i=0; i<N; i++ )
    count[((source[i])>>(byte*8))&0xff]++;

  index[0]=0;
  for ( i=1; i<256; i++ )
    index[i]=index[i-1]+count[i-1];
  for ( i=0; i<N; i++ )
    dest[index[((source[i])>>(byte*8))&0xff]++] = source[i];
}

تحتاج إلى الاتصال radix() أربع مرات ، لأنه يعمل فقط واحد عمود.

ترتيب بالإدراج

void insertSort(int a[], int length)
{    
    int i, j, value;
    for(i = 1; i < length; i++)
    {
        value = a[i];
        for (j = i - 1; j >= 0 && a[j] > value; j--)
            a[j + 1] = a[j];
        a[j + 1] = value;
    }
}

Answer 2

قام Knuth ببعض العمل على العثور على خوارزميات الفرز المثلى. ولكن حتى بالنسبة لخمسة عناصر فقط ، فإن الخوارزمية مع أصغر عدد من المقارنات معقد للغاية للتنفيذ.

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

ترتيب بالإدراج:

• تنفيذ بسيط
• فعالة لمجموعات البيانات الصغيرة (تماما)
• التكيف ، أي فعالة لمجموعات البيانات التي تم فرزها بالفعل بشكل كبير: التعقيد الزمني هو O (n + d) ، حيث D هو عدد الانقلابات
• أكثر كفاءة في الممارسة العملية من معظم الخوارزميات التربيعية البسيطة الأخرى ، أي O (N2) مثل فرز الاختيار أو نوع الفقاعة ؛ أفضل حالة (مدخلات مصنفة تقريبًا) هي O (N)
• مستقر ، أي لا يغير الترتيب النسبي للعناصر ذات المفاتيح المتساوية
• في مكانه ، لا يتطلب أي فقط كمية ثابتة O (1) من مساحة الذاكرة الإضافية
• على الإنترنت ، يمكن أن الفرز قائمة لأنها تستقبلها.