فرز قائمة كبيرة من درجات الاختبار

Question

لديك قائمة كبيرة (قل ن > 10000) من درجات الاختبار التي ترغب في فرزها.درجات الاختبار ما بين 1 و 100.ما هي أسرع طريقة لفرز القائمة?

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

الفكر الثاني:يجب علينا استخدام الجداول التجزئة, هل نحن نهتم التكرارات?غير قادر على معرفة كيفية استخدام جداول التجزئة.

الفكر الثالث:هل هذا له علاقة بالفرز الأساسي?لا فكرة.

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

هل هذا سؤال سهل جدا أو سؤال صعب جدا?

Answer 1

هذا سؤال سهل للغاية ، بافتراض أن جميع الدرجات هي أعداد صحيحة.

هنا هو أبسط خوارزمية في كلمات واضحة.سوف نبدأ count, ، صفيف صحيح من 100 أصفار.لكل درجة s, ، سنضيف 1 إلى count[s].لإنتاج عشرات فرزها المطلوبين ، ونحن سوف الانتاج count[1] 1 ثانية, count[2] 2س, ...، وأخيرا count[100] 100 ثانية.

يسمى هذا النوع من خوارزمية الفرز فرز العد.

حالة أكثر من N ن > 10000$ درجات الاختبار التي تتراوح بين 1 و 100 هي استخدام رئيسي لفرز العد.تعقيد الوقت هو O س (ن)$ ويحد تعقيد الفضاء من قبل بعض مضاعفات ثابتة صغيرة من 100.

قد ترغب في التحقق فرز العد للمزيد من المعلومات.

Answer 2

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

هل نهتم بالنسخ المكررة؟

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

     maintain a int table[101] = {0}   - hash table with key as score
                        //all elements are initialised to 0

    array contains all scores
    for score in array
         table[score] = table[score] +1
         //above in O(N) time and O(1) space.

    sorted_list = {} // initially empty
    for (score= 0; score < 101;i++)
      for(count = 0; count < table[i]; count++)
          sorted_list.add(score)
          //the above runs in O(N) time and O(N) space.

الآن إذا كنا نهتم بالمعلومات إذا كانت النتيجة مثل الطالب/الموضوع الذي تنتمي إليه، استخدم هذا النهج أدناه.أفترض أنك ستقوم بتخزين النتيجة والمعلومات ذات الصلة في بنية c/c++ أو أي تنسيق كائن.

احتفظ الآن بجدول تجزئة بحجم 100 (نطاق درجات الاختبار) المفتاح = النتيجة value = قائمة بالكائنات أو المثيلات بهذه النتيجة (إذا كنت كذلك الفرز لقائمة الطلاب ثم قائمة الطلاب الحاصلين على هذه الدرجة )

إذا كنت معتادًا على لغة c/c++، فيمكن تنفيذ بنية البيانات هذه باستخدام مجموعة من القوائم المرتبطة. تقنية التجزئة المستخدمة هنا هي تجزئة منفصلة.

وظيفة بنية البيانات مثل هذا يحتوي DS [score] على مؤشر / مرجع إلى القائمة المرتبطة باستخدام خريطة تجزئة أخرى لتحديد ذيول كل قائمة فرعية في DS ، يمكننا إدراج عنصر جديد في وقت O (1).

لذلك في تمريرة واحدة من i = 0 إلى i

بعد الإدراج يمكننا إنشاء قائمة جديدة بتمريرة واحدة على DS التي أنشأناها.

الخوارزمية هي مثل هذا.

دع المصفوفة تحتوي على كافة الكائنات مع درجاتها الخاصة

    for (i = 0; i< n; i++)
      key = array[i].score
      DS[key].insert(array[i]) //the tail part can be used for O(1) insertion.

     //the above loop runs in O(N)

     sorted_list = {} // empty_list
     for(score = 1; score<=100;score++)
       for each (obj in DS[score]) 
          sorted_list.add(obj)

      //the above loop runs in O(N).

     //the N refers to the size of original list here.

هذا النهج بطريقة سحرية هو أساس قائمة الانتظار من النوع الأساسي 100.اقرأ المزيد حول فرز الجذر وفرز العد باستخدام تنفيذ قائمة الانتظار.

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

أعتقد أنك مخطئ في أن تمريرة أخرى ستغير N إلى Nˆ2 .إلا إذا كنت تضع "التمرير الآخر" في حلقة فلن يحدث ذلك.

آمل أن أجبت على جميع أسئلتك.