QuickSort هي خوارزمية فرق تسد. في نموذج تصميم خوارزمية Divide & Conquer ، نقسم المشكلات إلى مسائل فرعية بشكل متكرر ثم نحل المشكلات الفرعية وأخيراً نجمع الحلول للوصول إلى النتيجة النهائية. في هذه المقالة سوف نركز على QuickSort In
سيتم تغطية المؤشرات التالية في هذه المقالة ،
هيا نبدأ!
شيء واحد يجب أخذه في الاعتبار عند تقسيم المشاكل إلى مشاكل فرعية هو أن بنية المشاكل الفرعية لا تتغير كما في المشكلة الأصلية.
تتكون خوارزمية Divide & Conquer من 3 خطوات:
- تقسيم: تقسيم المشكلة إلى مشاكل فرعية
- قهر: حل المشاكل الفرعية بشكل متكرر
- الجمع: الجمع بين الحلول للحصول على النتيجة النهائية
هناك العديد من الخوارزميات القائمة على نموذج فرق تسد. من بينها الفرز السريع ودمج الفرز.
على الرغم من أن التعقيد الزمني الأسوأ لـ QuickSort هو O (n2) وهو أكثر من العديد من خوارزميات الفرز الأخرى مثل Merge Sort و Heap Sort ، فإن QuickSort أسرع في الممارسة العملية ، لأنه يمكن تنفيذ الحلقة الداخلية بكفاءة على معظم البنى ، وفي معظم بيانات العالم الحقيقي.
لنتحدث عن تنفيذ خوارزمية الفرز السريع. تأخذ خوارزميات Quicksort عنصرًا محوريًا وتقسم المصفوفة حول العنصر المحوري. هناك عدد من الأشكال المختلفة لبرنامج Quicksot والتي تعتمد على كيفية اختيار العنصر المحوري. هناك عدة طرق لاختيار العنصر المحوري:
ما هي لغة البرمجة ساس
- اختيار العنصر الأول
- اختر العنصر الأخير
- اختيار عنصر عشوائي
- اختيار العنصر المتوسط
الشيء المهم التالي الذي يجب فهمه هو وظيفة partition () في خوارزمية الفرز السريع. وظيفة التقسيم لأخذ عنصر محوري ، ووضعه في الموضع الصحيح ، ونقل جميع العناصر الأصغر من العنصر المحوري إلى يساره وجميع العناصر الأكبر إلى اليمين. يستغرق الترتيب السريع وقتًا خطيًا للقيام بذلك.
ثم يتم تقسيم المصفوفة إلى جزأين من العنصر المحوري (أي العناصر الأقل من المحور والعناصر الأكبر من المحور) ويتم فرز المصفوفتين بشكل متكرر باستخدام خوارزمية Quicksort.
الآن بعد أن فهمنا عمل خوارزمية QuickSort. دعونا نفهم كيفية تطبيق خوارزمية Quicksort في جافا.
QuickSort وظيفة:
/ * تحتاج وظيفة Quicksort إلى فرز المصفوفة بأدنى وأعلى مؤشر * /
كيفية تجنب الجمود في جافا
تصنيف باطل (int arr []، int lowIndex، int highIndex) {// until lowIndex = highIndex if (lowIndexالآن دعونا نلقي نظرة على كود التقسيم لفهم كيفية عمله.
تقسيم الشفرة
في كود التقسيم ، سنختار العنصر الأخير كعنصر محوري. نجتاز المصفوفة الكاملة (أي باستخدام المتغير j في حالتنا). نتتبع آخر أصغر عنصر في المصفوفة (أي باستخدام المتغير i في حالتنا). إذا وجدنا أي عنصر أصغر من المحور ، فإننا ننقل عنصر التبادل الحالي a [j] مع arr [i] ، وإلا فإننا نستمر في العبور.
قسم int (int arr []، int lowIndex، int highIndex) {// جعل العنصر الأخير كمحور int pivot = arr [highIndex] // استخدام i لتتبع العناصر الأصغر من pivot int i = (lowIndex-1) من أجل (int j = lowIndex jالآن بعد أن فهمت وظيفة Quicksort & التقسيم ، دعنا نلقي نظرة سريعة على الكود الكامل
QuickSort كود جافا
class QuickSort {// Partition Method int partition (int arr []، int lowIndex، int highIndex) {int pivot = arr [highIndex] int i = (lowIndex-1) for (int j = lowIndex j// طريقة الفرز
تصنيف باطل (int arr []، int lowIndex، int highIndex) {if (lowIndex// طريقة طباعة المصفوفة
printArray ثابت فارغ (int arr []) {int n = arr.length لـ (int i = 0 i// الطريقة الرئيسية
public static void main (String args []) {int arr [] = {101، 37، 68، 29، 11، 5} int n = arr.length QuickSort ob = new QuickSort () ob.sort (arr، 0، n-1) System.out.println ('مصفوفة مرتبة') printArray (arr)}} انتاج:
الآن بعد تنفيذ برنامج Java أعلاه ، ستفهم كيفية عمل QuickSort وكيفية تنفيذه في Java.وهكذا وصلنا إلى نهاية هذه المقالة حول 'Quicksort in Java'. إذا كنت ترغب في معرفة المزيد ،تفحص ال بواسطة Edureka ، شركة تعليمية موثوقة عبر الإنترنت. تم تصميم دورة تدريب وإصدار شهادات Java J2EE و SOA من Edureka لتدريبك على مفاهيم Java الأساسية والمتقدمة جنبًا إلى جنب مع العديد من أطر Java مثل Hibernate & Spring.
لديك سؤال لنا؟ يرجى ذكر ذلك في قسم التعليقات في هذه المدونة وسنعاود الاتصال بك في أقرب وقت ممكن.