ترتيب سريع - ويكيبيديا

# ترتيب سريع

### من ويكيبيديا، الموسوعة الحرة

الترتيب السريع quicksort هو طريقة ترتيب من اختراع هوار (C.A.R.Hoare) في 1962.

## [تحرير] تفضيلات و خوارزمية

تنبني الخوارزمية على وضع العنصر الأول (يسمى مؤشر) في مكانه النهائي ثم وضع العناصر الأكبر من المؤشر من جهة اليمين و العناصر الأصغر من جهة اليسار. و تسمى هذه العملية تجزئة. و بالنسبة لكل تحت-جدول, نحدد مؤشرا جديدا و نعيد عملية التجزئة. تتكرر هذه العملية إلى أن نحصل على مجموعة مرتبة.

إذا تم اختيار المؤشر بطريقة صحيحة, نحصل على الطريقة الأسرع للترتيب في الحالة المتوسطة, مع تعقيد ب O(n ln (n)). و التي قد تتحول إلى O(n²) في الحالة الأصعب, و هي حالة جدول عناصره مرتبة أصلا. و لكن هذه الحالة بديهية لأن المجموعة مرتبة أصلا.

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

و بصفة عامة يعتبر الترتيب السريع الأكثر شيوعا (شعبية) من بين جميع خوارزميات الترتيب.

المشكلة الوحيدة تتمثل في كيفية اختيار المؤشر.

### [تحرير] اختيار أفضل مؤشر

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

### [تحرير] تحسينات أخرى

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

### [تحرير] مثال

    typedef int tab_entiers[MAX];

    int rapideEtape(tab_entiers t, int min, int max) {
            int temp = t[max];
            while(max > min) {
                    while(max > min && t[min] <= temp) min++;
                    if(max > min) {
                            t[max] = t[min];
                            max--;
                            while(max > min && t[max] >= temp) max--;
                            if(max > min) {
                                    t[min] = t[max];
                                    min++;
                            }
                    }
            }
            t[max] = temp;
            return max;
    }

    void rapide(tab_entiers t, int deb, int fin) {
            int mil;
            if(deb < fin) {
                    mil = rapideEtape(t,deb,fin);
                    if(mil - deb > fin - mil) {
                            rapide(t,mil+1,fin);
                            rapide(t,deb,mil-1);
                    }
                    else {
                            rapide(t,deb,mil-1);
                            rapide(t,mil+1,fin);
                    }
            }
    }

خوارزميات الترتيب

بالفقاعات · بالإختيار · بالإدراج · سريع ·

تمّ الاسترجاع من "http://ar.wikipedia.org../../../%D8%AA/%D8%B1/%D8%AA/%D8%AA%D8%B1%D8%AA%D9%8A%D8%A8_%D8%B3%D8%B1%D9%8A%D8%B9.html"

تصنيفات الصفحة: خوارزميات

##### Views

- مقالة
- ناقش هذه الصفحة
- النسخة الحالية

##### الموسوعة

- الصفحة الرئيسية
- الأحداث الجارية
- أحدث التغيرات الأساسية

##### تصفح

- المواضيع
- أبجدي
- بوابات

##### المشاركة و المساعدة

- بوابة المجتمع
- مساعدة
- الميدان
- التبرعات

##### بحث

##### لغات أخرى

- Català
- Česky
- Deutsch
- English
- Español
- Suomi
- Français
- עברית
- Italiano
- 日本語
- 한국어
- Lietuvių
- Nederlands
- Polski
- Português
- Русский
- Slovenčina
- Slovenščina
- Svenska
- Українська
- O'zbek
- Tiếng Việt
- 中文