فرز سريع ، أو فرز هور ، هي واحدة من خوارزميات الفرز الأكثر كفاءة. تم تطويره من قبل عالم الكمبيوتر الإنجليزي توني هور في عام 1959. على مر السنين ، أثبت الفرز السريع فعاليته ويستخدم على نطاق واسع في مختلف المجالات.
يعتمد مبدأ تشغيل الفرز السريع على مبدأ"فرق تسد". في كل خطوة من خطوات الخوارزمية ، يتم تحديد عنصر مرجعي ، وينقسم صفيف المصدر إلى مصفوفين فرعيين: عناصر أصغر من المرجع وعناصر أكبر من المرجع. ثم يتم تطبيق الفرز السريع بشكل متكرر على كلا المصفوفين الفرعيين. تستمر العملية حتى يصبح حجم الصف الفرعي 1 أو 0.
يعتمد الفرز السريع على حقيقة أن فرز المصفوفات الفرعية أسرع من فرز مصفوفة كاملة. يتم تحقيق ذلك بسبب حقيقة أن العنصر المرجعي مثبت في مكانه قبل استدعاء الفرز العودي للمصفوفات الفرعية. وبالتالي ، يتم تقليل عدد عمليات المقارنة والتقليب ، مما يسمح بإجراء الفرز السريع بشكل أسرع من العديد من خوارزميات الفرز الأخرى.
هنا مثال على تنفيذ خوارزمية فرز سريعة في بايثون:
ديف كويكسورت (آر آر):
إذا لين (أر) < = 1:
عودة آر
المحور = آر [لين (آر) / / 2]
اليسار = [س ل س في آر إذا س < محور]
الأوسط = [س ل س في آر إذا س = = محور]
الحق = [س ل س في آر إذا س > محور]
العودة فرز سريع (يسار) + وسط + فرز سريع (يمين)
آر = [3, 6, 8, 10, 1, 2, 1]
فرز_أر = فرز سريع(آر)
طباعة (فرز_ر)
- كيف يعمل الفرز السريع وأمثلة على استخدامه
- إدخال البيانات للفرز السريع
- تقسيم المصفوفة إلى مصفوفات فرعية
- تطبيق العودية من نوع سريع
- اختيار عنصر مرجعي
- مقارنة العناصر وإعادة ترتيبها
- أمثلة على استخدام الفرز السريع في مختلف المجالات
- 1. فرز مجموعة من الأرقام
- 2. فرز الصفوف
- 3. فرز الكائنات
- 4. فرز الملفات
- 5. فرز البيانات في قاعدة البيانات
- 6. فرز عناصر الواجهة
- سؤال وجواب
- لماذا أحتاج إلى نوع سريع?
- ما هو مبدأ الفرز السريع?
- ما هي الخوارزمية المستخدمة في الفرز السريع?
كيف يعمل الفرز السريع وأمثلة على استخدامه
الفرز السريع ، المعروف أيضا باسم الفرز السريع ، هو أحد أكثر خوارزميات الفرز كفاءة. وهو يقوم على مبدأ"فرق تسد". تقسم الخوارزمية مصفوفة المصدر إلى مجموعتين فرعيتين – عناصر أصغر من العنصر المرجعي وعناصر أكبر من العنصر المرجعي. ثم يتم فرز هاتين المجموعتين الفرعيتين بشكل متكرر بشكل منفصل.
مبدأ تشغيل الفرز السريع:
- يتم تحديد عنصر مرجعي من المصفوفة.
- تنقسم جميع العناصر الأخرى إلى مجموعتين: تلك التي هي أصغر من عنصر الدعم ، وتلك التي هي أكبر.
- يتم تطبيق الخوارزمية بشكل متكرر لكلا المجموعتين.
- ينتج عن الإخراج مجموعات فرعية مرتبة يتم دمجها في مصفوفة واحدة مرتبة.
مثال على استخدام الفرز السريع:
مثال 1:
- مجموعة المصدر: [9, 3, 7, 1, 5]
- عنصر الدعم: 5 (يمكنك تحديد أي عنصر من عناصر المصفوفة)
- تقسيم صفيف: [3, 1, 5, 9, 7] ( أقل من 5: [3 ، 1] ، أكثر من 5: [9 ، 7])
- التطبيق العودي للخوارزمية على المجموعات الفرعية:
- المجموعة الفرعية أقل من 5: [3 ، 1] ، عنصر الدعم: 3 ، القسم: [1 ، 3]
- المجموعة الفرعية أكبر من 5: [9 ، 7] ، عنصر الدعم: 9 ، القسم: [7 ، 9]
- مجموعات فرعية مرتبة: [1, 3, 5, 7, 9]
المثال 2:
- مجموعة المصدر: [6, 4, 2, 8, 10, 12]
- عنصر الدعم: 6
- تقسيم صفيف: [4, 2, 6, 8, 10, 12]
- التطبيق العودي للخوارزمية على المجموعات الفرعية:
- المجموعة الفرعية أقل من 6: [4 ، 2] ، عنصر الدعم: 4 ، القسم: [2 ، 4]
- المجموعة الفرعية أكبر 6: [8, 10, 12], عنصر الدعم: 8 ، انقسام: [8 ، 10 ، 12]
- مجموعات فرعية مرتبة: [2, 4, 6, 8, 10, 12]
وبالتالي ، يتيح لك الفرز السريع فرز المصفوفات بكفاءة من أي حجم ، مع وجود تعقيد خطي في الحالة المتوسطة والتربيعية في أسوأ الحالات.
إدخال البيانات للفرز السريع
كويكسورت هي واحدة من أسرع خوارزميات الفرز. يشير إلى فرق تسد الفرز. تعتمد الخوارزمية على مبدأ تقسيم مصفوفة المصدر إلى جزأين – عناصر أصغر من المرجع وعناصر أكبر من المرجع. ثم يتم تطبيق نفس الخوارزمية بشكل متكرر لكل جزء من هذه الأجزاء.
لكي تعمل خوارزمية الفرز السريع ، يجب أن يكون لديك بيانات الإدخال التالية:
- المصفوفة هي مجموعة من البيانات التي يجب فرزها. يمكن أن تكون عناصر المصفوفة أرقاما أو سلاسل أو أنواع بيانات أخرى.
- حجم المصفوفة هو عدد العناصر في المصفوفة. يحدد حجم المصفوفة عدد العمليات التي يجب إجراؤها أثناء الفرز.
- وظيفة المقارنة هي وظيفة تحدد ترتيب العناصر عند الفرز. على سبيل المثال ، لفرز الأرقام ، يمكنك استخدام دالة تقارن العناصر وإرجاع رقم سالب إذا كان العنصر الأول أقل من الثاني ، ورقم موجب إذا كان العنصر الأول أكبر من الثاني ، وصفر إذا كانت العناصر متساوية.
مثال على بيانات الإدخال للفرز السريع:
كونست آر = [5, 8, 1, 4, 2];حجم كونست = آر.الطول;
كونست قارن = (أ ، ب) = > أ-ب;
في هذا المثال ، يتم تحديد صفيف آر يحتوي على خمسة أرقام. حجم المصفوفة هو 5. تقوم وظيفة المقارنة بفرز العناصر بترتيب تصاعدي.
تقسيم المصفوفة إلى مصفوفات فرعية
يعتمد الفرز السريع على مبدأ تقسيم المصفوفة إلى مصفوفات فرعية.
تتكون عملية تقسيم المصفوفة إلى مجموعات فرعية من الخطوات التالية:
- يتم تحديد العنصر المرجعي للمصفوفة. يمكن تحديد العنصر المرجعي بطرق مختلفة ، على سبيل المثال ، العنصر الأول أو الأخير أو الأوسط من المصفوفة.
- تنقسم المصفوفة إلى قسمين: عناصر أصغر أو تساوي المرجع ، وعناصر أكبر من المرجع.
- يتم تنفيذ نوعين سريعين بشكل متكرر لكل من المصفوفات الفرعية المستلمة.
- يتم دمج المصفوفات الفرعية ، والنتيجة هي مصفوفة مرتبة.
يمكن تمثيل عملية تقسيم صفيف إلى مصفوفات فرعية باستخدام الجدول التالي:
| مجموعة المصدر | عنصر الدعم | عناصر أصغر أو متساوية | عناصر كبيرة |
|---|---|---|---|
| [5, 2, 9, 6, 1, 3] | 5 | [2, 1, 3] | [9, 6] |
كما يتضح من الجدول ، تقع العناصر الأصغر أو المساوية للمرجع في الجزء الأيسر (عناصر أصغر أو متساوية) ، والعناصر الأكبر من المرجع تقع في الجزء الأيمن (عناصر كبيرة).
مع كل العودية ، سيتم تقسيم مجموعة إلى مصفوفات فرعية أصغر وأصغر حتى يبقى عنصر واحد فقط في كل مستوى من العودية. ثم يتم دمج المصفوفات الفرعية بالترتيب الصحيح ، والنتيجة هي مصفوفة مرتبة.
من خلال هذه العملية البسيطة والفعالة لتقسيم المصفوفة ودمجها ، يوفر الفرز السريع سرعة فرز عالية وغالبا ما يستخدم في تطبيقات البرامج المختلفة.
تطبيق العودية من نوع سريع
الفرز السريع هو أحد أكثر خوارزميات الفرز فعالية التي تستخدم مبدأ"فرق تسد". بدلا من فرز قائمة العناصر واحدا تلو الآخر ، يقوم الفرز السريع بتقسيمها إلى جزأين وفرز كل منها بشكل متكرر.
يبدأ التطبيق العودي للفرز السريع بحقيقة أن القائمة الأصلية مقسمة إلى قسمين: قائمة بالعناصر الأصغر من العنصر المرجعي ، وقائمة بالعناصر الأكبر من العنصر المرجعي. ثم يتم فرز هذين الجزأين بشكل متكرر بشكل منفصل حتى يتم فرز القائمة بأكملها.
يمكن تمثيل عملية تطبيق الفرز السريع بشكل متكرر على النحو التالي:
- حدد عنصرا مرجعيا من قائمة.
- قسم القائمة إلى قسمين: قائمة عناصر أصغر من المرجع ، وقائمة عناصر أكبر من المرجع.
- قم بتطبيق فرز سريع بشكل متكرر على كل جزء من الأجزاء المستلمة.
- اجمع الأجزاء المصنفة في قائمة واحدة.
مثال على تطبيق متكرر للفرز السريع:
- القائمة الأصلية: [5, 9, 1, 3, 2, 8, 4]
- عنصر الدعم: 5
- عناصر أصغر: [1, 3, 2, 4]
- عناصر كبيرة: [9 ، 8]
- تطبيق الفرز السريع بشكل متكرر على العناصر الأصغر:
- تطبيق الفرز السريع بشكل متكرر على العناصر الكبيرة:
نتيجة للتطبيق العودي للفرز السريع ، يتم الحصول على قائمة مرتبة: [1, 2, 3, 4, 5, 8, 9].
اختيار عنصر مرجعي
الفرز السريع هي واحدة من أسرع خوارزميات الفرز وأكثرها كفاءة. ومع ذلك ، لضمان كفاءة الخوارزمية ، من الضروري تحديد العنصر المرجعي بشكل صحيح والذي سيتم على أساسه إجراء الفرز.
العنصر المرجعي هو عنصر من صفيف يتم تحديده كنقطة مرجعية لتقسيم صفيف إلى جزأين. أثناء تنفيذ الخوارزمية ، يتم وضع جميع العناصر الأصغر من المرجع في الجزء الأيسر من المصفوفة ، ويتم وضع جميع العناصر الأكبر من المرجع في الجزء الأيمن.
يمكن تنفيذ اختيار عنصر الدعم بطرق مختلفة:
- تحديد العنصر الأول من المصفوفة كمرجع. هذه الطريقة هي الأبسط ، ومع ذلك ، في حالة فرز المصفوفة بالفعل ، ستعمل خوارزمية الفرز ببطء.
- تحديد العنصر الأخير من المصفوفة كمرجع. هذه الطريقة سهلة التنفيذ أيضا ، ولكنها قد تكون أكثر كفاءة إذا تم فرز المصفوفة عمليا بترتيب عكسي.
- اختيار عنصر عشوائي من المصفوفة كمرجع. تقضي هذه الطريقة على مشاكل المصفوفات التي تم فرزها بالفعل ، ومع ذلك ، قد تكون أقل فعالية بسبب عشوائية اختيار العنصر المرجعي.
- اختيار وسيط من ثلاثة عناصر. تتضمن هذه الطريقة تحديد العنصر الوسيط من العناصر الأولى والمتوسطة والأخيرة للمصفوفة. يضمن تشغيل أكثر كفاءة للخوارزمية في معظم الحالات ، ولكنه يتطلب حسابات إضافية.
يعد اختيار العنصر المرجعي نقطة أساسية في تشغيل خوارزمية الفرز السريع. يمكن أن يؤدي اختيار الطريقة المثلى إلى تحسين أداء الفرز بشكل كبير.
مقارنة العناصر وإعادة ترتيبها
كويكسورت هي واحدة من الخوارزميات الأكثر كفاءة لفرز المصفوفات.
يعتمد مبدأ تشغيل الخوارزمية على فرق تسد: تنقسم المصفوفة إلى قسمين,
حيث يتم وضع جميع العناصر الأصغر من المحور على يسارها,
ويتم وضع تلك الأكبر أو المتساوية على اليمين. ثم يتم فرز الأجزاء اليمنى واليسرى بشكل متكرر حتى
يتم الوصول إلى الوحدة الأساسية أو حتى يصبح الجزء الأيسر مساويا للحق.
يستخدم عامل المقارنة" أكثر "أو" أقل " لمقارنة العناصر.
في حالة الأرقام ، هذه هي العوامل الرياضية" أكثر "( > ) و" أقل" (<).
على سبيل المثال ، عند مقارنة الرقمين 4 و 7 ، يعود عامل التشغيل" المزيد " صحيحا,
و " أقل " المشغل يعود كاذبة. عند مقارنة السلاسل ، يتم استخدامه
مقارنة معجمية تقارن ترتيبها أبجديا
أو تمثيل رمزي. على سبيل المثال ، للسلاسل "التفاح " و"الموز"
، يعود عامل التشغيل" الأقل "بشكل صحيح ، ويعود عامل التشغيل" المزيد " بشكل خاطئ.
يتم إعادة ترتيب العناصر في المصفوفة عن طريق تعيين القيم
من العناصر المجاورة. إذا كانت العناصر غير متسلسلة ، يتم تبديلها واحدة تلو الأخرى
حتى يتم فرزها. على سبيل المثال ، عند فرز مصفوفة [4, 7, 2, 1, 5]
تتم مقارنة العناصر 4 و 7 وإعادة ترتيبها إذا لزم الأمر. ثم العناصر
تتم مقارنة 7 و 2 وإعادة ترتيبها إذا لزم الأمر ، وهلم جرا حتى كامل
يتم فرز مجموعة: [1, 2, 4, 5, 7].
أمثلة على استخدام الفرز السريع في مختلف المجالات
الفرز السريع هو أحد أكثر خوارزميات الفرز كفاءة ويستخدم على نطاق واسع في مختلف المجالات حيث يلزم طلب البيانات.
1. فرز مجموعة من الأرقام
يتيح لك الفرز السريع ترتيب مجموعة من الأرقام بكفاءة بأكثر الطرق فعالية. يمكن أن يكون هذا مفيدا ، على سبيل المثال ، عند العمل بكمية كبيرة من البيانات ، عندما تكون سرعة العمليات مهمة.
2. فرز الصفوف
يمكن تطبيق الفرز السريع لترتيب الصفوف بالترتيب الأبجدي أو بالترتيب المحدد من قبل المستخدم. يمكن أن يكون هذا مفيدا ، على سبيل المثال ، عند فرز قائمة الأسماء أو العناوين.
3. فرز الكائنات
يمكن استخدام الفرز السريع لفرز الكائنات حسب حقل معين أو حقول متعددة. على سبيل المثال ، يمكن أن يكون هذا مفيدا عند فرز قائمة الطلاب حسب درجاتهم أو حسب الاسم الأول والأخير.
4. فرز الملفات
يمكن تطبيق الفرز السريع لتنظيم محتويات الملفات. على سبيل المثال ، يمكن أن يكون هذا مفيدا عند فرز ملفات السجل حسب الوقت أو عند فرز قائمة الكلمات في ملف نصي.
5. فرز البيانات في قاعدة البيانات
يمكن استخدام الفرز السريع لتنظيم البيانات في قاعدة بيانات. على سبيل المثال ، يمكن أن يكون هذا مفيدا عند فرز قائمة الطلبات حسب التاريخ أو عند فرز قائمة العملاء حسب هويتهم.
6. فرز عناصر الواجهة
يمكن تطبيق الفرز السريع لترتيب العناصر في واجهة المستخدم. على سبيل المثال ، يمكن أن يكون هذا مفيدا عند فرز قائمة المنتجات في متجر عبر الإنترنت حسب السعر أو عند فرز قائمة جهات الاتصال في دفتر العناوين أبجديا.
الأمثلة المقدمة ليست سوى جزء صغير من المناطق التي يمكن فيها تطبيق الفرز السريع. مزاياها في السرعة والكفاءة تجعلها واحدة من خوارزميات الفرز الأكثر شعبية.
سؤال وجواب
لماذا أحتاج إلى نوع سريع?
يتم استخدام الفرز السريع لترتيب العناصر في مصفوفة أو قائمة. يتميز بالإنتاجية والكفاءة العالية.
ما هو مبدأ الفرز السريع?
يعتمد مبدأ تشغيل الفرز السريع على تقسيم المصفوفة إلى مجموعتين فرعيتين ، تحتوي إحداهما على عناصر أصغر أو مكافئة للعنصر المرجعي ، والأخرى تحتوي على عناصر أكبر من العنصر المرجعي. ثم يتم تطبيق الخوارزمية بشكل متكرر على كلتا المجموعتين الفرعيتين حتى يتم تحقيق النتيجة النهائية.
ما هي الخوارزمية المستخدمة في الفرز السريع?
يستخدم الفرز السريع خوارزمية فرق تسد ، والتي تتمثل في تقسيم المهمة إلى مهام فرعية أصغر وحلها اللاحق. على وجه التحديد ، في الفرز السريع ، يتم تقسيم المصفوفة إلى مصفوفات فرعية وفرزها بشكل منفصل.