وأوضح فرز سريع في جافا

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

عندما يكون عدد العناصر في القائمة زوجيًا ، فإن تقسيم القائمة إلى النصف يعني أن النصف الأول الحرفي من القائمة هو النصف الأول ، والنصف الثاني الحرفي من القائمة هو النصف الثاني. العنصر الأوسط (الأوسط) للقائمة بأكملها ، هو العنصر الأخير في القائمة الأولى. هذا يعني أن المؤشر الأوسط هو الطول / 2 - 1 ، حيث يبدأ عد الفهرس من الصفر. الطول هو عدد العناصر في القائمة. على سبيل المثال ، إذا كان عدد العناصر 8 ، فإن النصف الأول من القائمة يحتوي على 4 عناصر والنصف الثاني من القائمة يحتوي أيضًا على 4 عناصر. هذا جيد. نظرًا لأن عد الفهرس يبدأ من 0 ، فإن المؤشر الأوسط هو 3 = 8 / 2-1.

ماذا عن الحالة عندما يكون عدد العناصر في القائمة أو القائمة الفرعية فرديًا؟ في البداية ، لا يزال الطول مقسومًا على 2. حسب الاصطلاح ، فإن عدد العناصر في النصف الأول من هذا التقسيم هو الطول / 2 + 1/2. يبدأ عد الفهرس من الصفر. يُعطى المؤشر الأوسط بالطول / 2 - 1/2. يعتبر هذا بمثابة المدى المتوسط ​​، من خلال العرف. على سبيل المثال ، إذا كان عدد العناصر في القائمة هو 5 ، فإن الفهرس الأوسط هو 2 = 5/2 - 1/2. وهناك ثلاثة عناصر في النصف الأول من القائمة وعنصرين في النصف الثاني. العنصر الأوسط في القائمة بأكملها هو العنصر الثالث في الفهرس ، 2 ، وهو الفهرس الأوسط لأن عد الفهرس يبدأ من 0.

القسمة بهذه الطريقة هي مثال على حساب الأعداد الصحيحة.

وسيط ثلاث قيم

سؤال: ما هو وسيط التسلسل:

ج ب أ

حل:
رتب القائمة بترتيب تصاعدي:

أ ب ج

الحد الأوسط ، ب ، هو الوسيط. هو الحجم الذي يقع بين المقدارين الآخرين.

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

باستخدام 'الفرز السريع' ، يلزم توفر الوسيط للقائمة بأكملها والقوائم الفرعية. الكود الكاذب للبحث عن متوسط ​​ثلاث قيم متباعدة في قائمة (مصفوفة) هو:

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

سينتج عن الفرز في هذا البرنامج التعليمي قائمة حيث تكون القيمة الأولى هي القيمة الأصغر ، والقيمة الأخيرة هي القيمة الأكبر. بالأبجدية ، A أقل من Z.

هنا ، المحور هو الوسيط الناتج. منخفض هو أدنى مؤشر في القائمة أو القائمة الفرعية (ليس بالضرورة لأدنى قيمة) ؛ مرتفع هو أعلى مؤشر في القائمة أو القائمة الفرعية (ليس بالضرورة لأعلى قيمة) ، والوسط هو المؤشر الأوسط التقليدي (ليس بالضرورة للقيمة الوسطى للقائمة بأكملها).

لذا ، فإن الوسيط المطلوب الحصول عليه هو بين قيمة أدنى مؤشر وقيمة المؤشر الأوسط وقيمة أعلى مؤشر.

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

في نهاية هذه المقايضات الثلاثة ، ستكون القيمة الوسطى للقيم الثلاثة المعنية هي A [عالية] ، والتي قد يكون محتواها الأصلي قد تغير في مقطع الكود. على سبيل المثال ، ضع في اعتبارك التسلسل غير الفرز:

ج ب أ

نحن نعلم بالفعل أن الوسيط هو B. ومع ذلك ، يجب إثبات ذلك. الهدف هنا هو الحصول على متوسط ​​هذه القيم الثلاث باستخدام مقطع الكود أعلاه. تقارن عبارة if الأولى بين B و C. إذا كانت B أقل من C ، فيجب تبديل موقعي B و C. B أقل من C ، لذلك يصبح الترتيب الجديد:

ب ج أ

لاحظ أن قيم المؤشر الأدنى والمؤشر الأوسط قد تغيرت. تقارن عبارة if الثانية A و B. إذا كانت A أقل من B ، فيجب تبديل موقعي A و B. أ أقل من ب ، لذا يصبح الترتيب الجديد:

أ ج ب

لاحظ أن قيم أعلى مؤشر وأدنى مؤشر قد تغيرت. تقارن عبارة if الثالثة C و B. إذا كانت C أقل من B ، فيجب تبديل مواضع C و B. C لا تقل عن B ، لذلك لا يتم إجراء مقايضة. يبقى الترتيب الجديد كما كان في السابق ، أي:

أ ج ب

B هو الوسيط ، وهو A [مرتفع] ، وهو المحور. لذلك ، يتم إنشاء المحور في أقصى نهاية القائمة أو القائمة الفرعية.

وظيفة المبادلة

الميزة الأخرى التي يحتاجها Quick Sort هي وظيفة التبديل. وظيفة المبادلة ، تتبادل قيم متغيرين. الكود الكاذب لوظيفة المبادلة هو:

هنا ، يشير x و y إلى القيم الفعلية وليس إلى النسخ.

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

محتوى المادة

• خوارزمية الفرز السريع
• قسم Pseudocode
• رسم توضيحي للفرز السريع
• جافا الترميز
• استنتاج

خوارزمية الفرز السريع

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

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

خطوات خوارزمية الفرز السريع كالتالي:

1. تأكد من وجود رقمين على الأقل لفرزهما في القائمة التي لم يتم فرزها.
2. احصل على قيمة مركزية مقدرة للقائمة ، تسمى المحور. الوسيط ، كما هو موضح أعلاه ، هو أحد طرق الحصول على المحور. طرق مختلفة تأتي مع مزاياها وعيوبها. - اراك لاحقا.
3. قسم القائمة. هذا يعني ، ضع المحور في القائمة. بهذه الطريقة ، تكون جميع العناصر الموجودة على اليسار أقل من القيمة المحورية ، وتكون جميع العناصر الموجودة على اليمين أكبر من القيمة المحورية أو مساوية لها. هناك طرق مختلفة للتقسيم. تأتي كل طريقة تقسيم مع مزاياها وعيوبها. التقسيم هو تقسيم في نموذج فرق تسد.
4. كرر الخطوات 1 و 2 و 3 بشكل متكرر لأزواج القائمة الفرعية الجديدة التي تظهر حتى يتم فرز القائمة بأكملها. هذا هو الإخضاع في نموذج فرق تسد.

الكود الزائف للفرز السريع هو:

قسم Pseudocode

الكود الزائف للقسم المستخدم في هذا البرنامج التعليمي هو:

في الرسم التوضيحي لـ Quick Sort أدناه ، يتم استخدام هذا الرمز:

رسم توضيحي للفرز السريع

ضع في اعتبارك القائمة (المصفوفة) التالية من الأحرف الأبجدية التي لم يتم فرزها:

Q W E R T Y U I O P

من خلال الفحص ، تكون القائمة التي تم فرزها هي:

E I O P Q R T U W Y

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

Q W E R T Y U I O P

يتم تحديد المحور الأول من arr [0] = Q و arr [4] = T و arr [9] = P ، ويتم تحديده على أنه Q ويتم وضعه في أقصى يمين القائمة. لذلك ، تصبح القائمة التي تحتوي على أي فرز للدالة المحورية:

P W E R T Y U I O Q

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

الفهارس المنخفضة والعالية الآن هي 0 و 9. لذلك ، سيبدأ الكمبيوتر بالمسح من الفهرس 0 حتى يصل إلى فهرس ، قيمته تساوي أو أكبر من المحور ويتوقف عند هذا الحد مؤقتًا. سوف يقوم أيضًا بالمسح من الطرف العلوي (الأيمن) ، الفهرس 9 ، النازل ، حتى يصل إلى فهرس تكون قيمته أقل من أو تساوي المحور ويتوقف عند هذا الحد مؤقتًا. هذا يعني موقفين للتوقف. إذا كان i ، متغير المؤشر المتزايد ، من منخفض لا يساوي أو أكبر من متغير المؤشر المتناقص ، j من أعلى ، فسيتم تبديل هاتين القيمتين. في الوضع الحالي ، توقف المسح من كلا الطرفين عند W و O. وهكذا تصبح القائمة:

P O E R T Y U I W Q

لا يزال المحور Q. المسح في اتجاهين متعاكسين يستمر ويتوقف وفقًا لذلك. إذا لم تكن i مساوية لـ أو أكبر من j ، فسيتم تبديل القيمتين اللتين توقف عندهما المسح من كلا الطرفين. هذه المرة ، توقف المسح من كلا الطرفين عند R و I. لذلك ، يصبح ترتيب القائمة:

P O E I T Y U R W Q

لا يزال المحور Q. المسح في اتجاهين متعاكسين يستمر ويتوقف وفقًا لذلك. إذا لم تكن i مساوية لـ أو أكبر من j ، فسيتم تبديل القيمتين اللتين توقف عندهما المسح. هذه المرة ، توقف المسح من كلا الطرفين عند T لـ i و I لـ j. لقد التقيت أو عبرت أنا و j. لذلك ، لا يمكن أن يكون هناك مقايضة. تظل القائمة كما هي:

P O E I T Y U R W Q

في هذه المرحلة ، يجب وضع المحور Q في موضعه النهائي في الفرز. يتم ذلك عن طريق تبديل arr [i] بـ arr [high] ، مبادلة T و Q. تصبح القائمة:

P O E I Q Y U R W T

في هذه المرحلة ، انتهى تقسيم القائمة بأكملها. لعب المحور = Q دوره. يوجد الآن ثلاث قوائم فرعية ، وهي:

P O E I Q Y U R W T

التقسيم هو التقسيم والقهر (الفرز) في النموذج. Q في موضع الفرز الصحيح. كل عنصر على يسار Q أصغر من Q ، وكل عنصر على يمين Q أكبر من Q. ومع ذلك ، لا تزال القائمة اليسرى غير مرتبة ؛ والقائمة الصحيحة لا تزال غير مرتبة. يجب استدعاء وظيفة الفرز السريع بأكملها بشكل متكرر من أجل فرز القائمة الفرعية اليسرى والقائمة الفرعية اليمنى. يجب أن يستمر استدعاء 'الفرز السريع' ؛ سيتم وضع قوائم فرعية جديدة حتى يتم فرز القائمة الأصلية بالكامل. لكل استدعاء لوظيفة الفرز السريع ، يتم الاهتمام بالقائمة الفرعية اليسرى أولاً قبل حضور القائمة الفرعية اليمنى المقابلة. يجب الحصول على محور جديد لكل قائمة فرعية.

بالنسبة للقائمة الفرعية:

P O E I

تم تحديد المحور (الوسيط) لـ P و O و I. سيكون المحور O. بالنسبة إلى هذه القائمة الفرعية ، وفيما يتعلق بالقائمة الكاملة ، فإن arr [low] الجديد هو arr [0] ، و arr [high] الجديد هو arr [i-1] = arr [ 4-1] = arr [3] ، حيث i هو الفهرس المحوري الأخير من القسم السابق. بعد استدعاء الدالة pivot () ، القيمة المحورية الجديدة ، pivot = O. لا تخلط بين الدالة المحورية والقيمة المحورية. قد تقوم الوظيفة المحورية ببعض الفرز الصغير وتضع المحور في أقصى يمين القائمة الفرعية. تصبح هذه القائمة الفرعية ،

أنا P E O

باستخدام هذا المخطط ، ينتهي المحور دائمًا عند الطرف الأيمن من القائمة الفرعية أو القائمة بعد استدعاء الوظيفة الخاص به. يبدأ المسح من كلا الطرفين من arr [0] و arr [3] حتى i و j يلتقيان أو يتقاطعان. يتم إجراء المقارنة باستخدام المحور = O. تقع المحطات الأولى عند P و E. ويتم تبديلها ، وتصبح القائمة الفرعية الجديدة:

أنا E P O

يستمر المسح من كلا الطرفين ، وتكون المحطات الجديدة عند P لـ i و E لـ j. الآن أنا و ي التقيا أو يتقاطعان. لذلك تظل القائمة الفرعية كما هي:

أنا E P O

ينتهي تقسيم القائمة الفرعية أو القائمة عند وضع المحور في موضعه النهائي. لذلك ، يتم تبديل القيم الجديدة لـ arr [i] و arr [high]. أي ، يتم تبديل P و O. تصبح القائمة الفرعية الجديدة:

I E O P

O الآن في موقعها النهائي للقائمة بأكملها. انتهى دورها كمحور. تم تقسيم القائمة الفرعية حاليًا إلى ثلاث قوائم أخرى ، وهي:

I E O P

في هذه المرحلة ، يجب استدعاء التصنيف السريع من القائمة الفرعية اليمنى الأولى. ومع ذلك ، لن يتم استدعاؤها. بدلاً من ذلك ، سيتم تدوينه وتحجزه ، ليتم استدعاؤه لاحقًا. أثناء تنفيذ عبارات وظيفة التقسيم ، من أعلى الوظيفة ، يجب استدعاء 'الفرز السريع' للقائمة الفرعية اليسرى (بعد استدعاء pivot ()). سيتم استدعاؤه للقائمة:

بمعنى آخر

سيبدأ بالبحث عن وسيط I و E. وهنا ، arr [low] = I، arr [mid] = I and arr [high] = E. لذا يجب تحديد الوسيط ، المحوري ، بواسطة خوارزمية البيفوت ، 1. ومع ذلك ، فإن الشفرة الزائفة المحورية أعلاه ستحدد المحور مثل E. يحدث هذا الخطأ هنا لأن الرمز الكاذب أعلاه مخصص لثلاثة عناصر وليس عنصرين. في التنفيذ أدناه ، هناك بعض التعديل على الكود. تصبح القائمة الفرعية ،

ه أنا

ينتهي المحور دائمًا عند الطرف الأيمن من القائمة الفرعية أو القائمة بعد استدعاء الوظيفة الخاص بها. يبدأ المسح من كلا الطرفين من arr [0] و arr [1] حصريًا حتى يلتقي i و j أو يتقاطعان. تم إجراء المقارنة مع المحور = I. المحطات الأولى والوحيدة عند I و E: عند I لـ i و E لـ j. الآن أنا و J قد التقيا أو عبرتا. لذلك ، تظل القائمة الفرعية كما هي:

ه أنا

ينتهي تقسيم القائمة الفرعية أو القائمة عند وضع المحور في موضعه النهائي. لذلك ، يتم تبديل القيم الجديدة لـ arr [i] و arr [high]. يحدث هنا أن arr [i] = I و arr [high] = I. لذلك ، يتم تبديل نفس القيمة مع نفسها. تصبح القائمة الفرعية الجديدة:

ه أنا

أنا الآن في موقعه النهائي للقائمة بأكملها. انتهى دورها كمحور. تم الآن تقسيم القائمة الفرعية إلى قائمتين أخريين ،

ه أنا

الآن ، المحاور حتى الآن هي Q و O و I. تنتهي المحاور في مواضعها النهائية. قائمة فرعية لعنصر واحد ، مثل P أعلاه ، تنتهي أيضًا في موضعها النهائي.

في هذه المرحلة ، تم فرز أول قائمة فرعية على اليسار بالكامل. وإجراء الفرز الآن في:

E I O P Q Y U R W T

القائمة الفرعية اليمنى الأولى:

Y U R W T

لا يزال بحاجة إلى الفرز.

قهر القائمة الفرعية اليمنى الأولى
تذكر أنه تم تدوين مكالمة الفرز السريع الخاصة بالقائمة الفرعية اليمنى الأولى وحجزها بدلاً من تنفيذها. في هذه المرحلة ، سيتم تنفيذه. وهكذا ، فإن arr [low] = arr [5] = arr [QPivotIndex + 1] ، و arr الجديد [high] يظل arr [9]. ستحدث هنا مجموعة مماثلة من الأنشطة التي حدثت لأول قائمة فرعية على اليسار. وهذه القائمة الفرعية اليمنى الأولى مرتبة على النحو التالي:

R T U W Y

وقد تم فرز القائمة الأصلية التي لم يتم فرزها إلى:

E I O P Q R T U W Y

جافا الترميز

إن وضع الخوارزمية في Java هو مجرد وضع جميع مقاطع الشفرة الكاذبة المذكورة أعلاه في طرق Java في فئة واحدة. لا تنسَ أنه يجب أن يكون هناك طريقة main () في الفصل تستدعي وظيفة quicksort () مع المصفوفة غير المفروزة.

طريقة pivot ()

طريقة Java pivot () التي تُرجع القيمة ، pivot ، يجب أن تكون:

طريقة المبادلة

يجب أن تكون طريقة () swap:

طريقة الترتيب السريع

يجب أن تكون طريقة الترتيب السريع:

طريقة التقسيم

يجب أن تكون طريقة التقسيم ():

الطريقة الرئيسية ()

يمكن أن تكون الطريقة () الرئيسية:

يمكن وضع جميع الأساليب المذكورة أعلاه في فئة واحدة.

استنتاج

الفرز السريع عبارة عن خوارزمية فرز تستخدم نموذج فرق تسد. يبدأ بتقسيم قائمة غير مرتبة إلى قائمتين أو ثلاث قوائم فرعية. في هذا البرنامج التعليمي ، قسم Quick Sort القائمة إلى ثلاث قوائم فرعية: قائمة فرعية على اليسار ، وقائمة وسطى لعنصر واحد ، وقائمة فرعية على اليمين. الاستيلاء في 'الفرز السريع' هو قسمة قائمة أو قائمة فرعية أثناء فرزها باستخدام قيمة محورية. شرح هذا البرنامج التعليمي تنفيذًا واحدًا لـ Quick Sort في لغة كمبيوتر Java.

نبذة عن الكاتب

كريسانثوس فورتشا

مكتشف تكامل الرياضيات من المبادئ الأولى والسلسلة ذات الصلة. درجة الماجستير في التعليم الفني ، تخصص الإلكترونيات وبرامج الكمبيوتر. بكالوريوس إلكترونيات. لدي أيضًا معرفة وخبرة على مستوى الماجستير في الحوسبة والاتصالات. من بين 20000 كاتب ، كنت أحمل المركز السابع والثلاثين في موقع devarticles.com. أعمل في هذه المجالات منذ أكثر من 10 سنوات.

وظائف تلميح لينكس ذات الصلة

• مقارنة الجمل في جافا
• كيفية استخدام HashMap في Java
• وأوضح فرز سريع في جافا
• اجتياز الشجرة الثنائية للطلب المسبق في Java
• وأوضح دمج فرز في جافا
• كيفية استخدام الماسح الضوئي في Java
• جافا الكتابة إلى ملف