الفرز السريع في C++ بطيء

Question

لدي 9 قيم في شكل مصفوفة وأحتاج إلى حساب الوسيط من هذه القيم كجزء من عملية المحاكاة.

أستخدم الفرز السريع في C++ (أي qsort()) مما يؤدي إلى بطء العملية (حيث تتكرر هذه العملية عدة مرات).

هل هناك خوارزمية فرز أفضل يمكنني استخدامها؟

Answer 1

الفرز للحصول على الوسيط غير فعال للغاية.يمكنك استخدام STL nth_element بدلاً من ذلك:

#include <algorithm>

// Assuming you keep the elements in a vector v of size len

std::nth_element( v.begin(), v.begin()+len/2, v.end() );
median = v[len/2];

 //... or, if the elements are in a simple array v[len], then

std::nth_element( v, v+len/2, v+len );
median = v[len/2];

ملحوظة:سيقوم nth_element بتعديل المتجه/المصفوفة v.قم بعمل نسخة أولاً إذا كنت تريد الحفاظ على الأصل.

Answer 2

من فضلك من فضلك من فضلك لا توصي أبدًا بنوع الفقاعة إلا للمازوشيين!

للقيم الصغيرة، إدراج الفرز هو الأفضل، وهو جيد للتطبيقات الأخرى (البيانات المصنفة تقريبًا بأي طول).

يحرر:تنظيف التنسيق، مع التركيز على الإجابة المقترحة.

Answer 3

9 قيم فقط؟الفرز السريع هو مبالغة.

ربما تستخدم الفرز بالإدراج، أو الفرز الفقاعي، أو خوارزميات فرز أخرى أبسط عند العمل مع مجموعات بيانات أصغر.

أداء

يحتوي الفرز الفقاعي على التعقيد الأسوأ والمتوسط ​​على حد سواء О(n²)، حيث n هو عدد العناصر التي يتم فرزها.توجد العديد من خوارزميات الفرز ذات الحالة الأسوأ أو التعقيد المتوسط ​​الأفضل بكثير لـ O(n log n).حتى خوارزميات الفرز الأخرى О(n²)، مثل فرز الإدراج، تميل إلى الحصول على أداء أفضل من فرز الفقاعات.ولذلك فإن فرز الفقاعة ليس خوارزمية فرز عملية عندما يكون n كبيرًا.

ومع ذلك، من المؤكد أنك لم تضطر حتى إلى الفرز للحصول على الوسيط كما اقترح الآخرون.

Answer 4

1. كما ذكر أحد الأشخاص، ليست هناك حاجة للفرز بشكل كامل للحصول على الوسيط.

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

Answer 5

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

يتألق Quicksort وMergesort حقًا عندما يصل حجم عينتك إلى حد معين، ربما 50+.

في هذه المواقف، سأكتب الكود الخاص بي بدلاً من استخدام وظيفة مدمجة.

Answer 6

تُفضل خوارزمية std::sort() دائمًا تقريبًا على qsort().عادةً ما يكون أسهل في الاستخدام ويعمل بشكل أسرع.

إذا كنت ترغب في الدخول في التفاصيل، هناك في الواقع عائلة من خوارزميات الفرز.يكتب ستروستروب لغة البرمجة C++ غالبًا ما لا يكون هذا std::sort هو الشيء الصحيح الذي يجب استخدامه.في هذه الحالة، ربما يكون std::nth_element() هو ما تريده.

Answer 7

ليس لديك قيم كافية للعمل مع Quicksort ويجب عليك استخدام خوارزميات أقل تقدمًا (على سبيل المثال:فرز الفقاعة، فرز الإدراج، ... شرح هنا.

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

Answer 8

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

في مجموعات البيانات الصغيرة، يمكنك استخدام خوارزميات مختلفة للحصول على الأداء الأمثل.يتألق QuickSort بمجرد نمو مجموعة البيانات.

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