موصى به, 2021

اختيار المحرر

الفرق بين فرز الفقاعة و فرز الفرز

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

هناك فرق كبير آخر بين الاثنين هو أن نوع الفقاعة عبارة عن خوارزمية ثابتة بينما يعتبر اختيار الفرز خوارزمية غير مستقرة. تعتبر الخوارزمية ثابتة للعناصر التي لها نفس المفتاح في نفس الترتيب الذي تحدث به قبل الفرز في القائمة أو الصفيف. بشكل عام ، تستخدم الخوارزميات الأكثر استقرارًا وسرعة ذاكرة إضافية.

رسم بياني للمقارنة

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

تعريف تصنيف الفقاعة

تعتبر Bubble sort هي أبسط خوارزمية تكرارية تعمل من خلال مقارنة كل عنصر أو عنصر مع العنصر المجاور لها وتبديلها إذا لزم الأمر. بكلمات بسيطة ، فإنه يقارن العنصر الأول والثاني من القائمة ويقوم بتبديلها ما لم تكن من ترتيب معين. وبالمثل ، فإن العنصر الثاني والثالث يتم مقارنتهم وتبديلهم ، وينتقل هذا المقارن والمبادلة إلى نهاية القائمة. عدد المقارنات في التكرار الأول هي n-1 حيث n هي عناصر الرقم في مصفوفة. سيكون العنصر الأكبر في المركز nth بعد التكرار الأول. وبعد كل عملية تكرار ، يتناقص عدد المقارنات ، وفي نهاية المطاف يتم إجراء مقارنة واحدة فقط.

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

تعريف فرز التحديد

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

في تصنيف الفرز ، لا يؤدي الصفيف الذي تم فرزه أو فرزه إلى أي اختلاف ويستهلك ترتيب n2 ( O (n2) ) في كلٍ من تعقيد الحالات الأفضل والأسوأ. اختيار التصنيف أسرع من فرز الفقاعة.

الاختلافات الرئيسية بين فرز الفقاعة و فرز الفرز

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

استنتاج

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

Top