الفصل السابع

Quicksort

مقدمة

اتعرضنا في الفصول اللي عدت لأكتر من algorithm بيحل مشكلة ال sorting , بداية من ال Insertion sort وال Merge sort في الفصل التاني , واخر حاجة في الفصل السادس اتعرضنا لل Heap sort , في الفصل ده بإذن الله هنتعرض لل Quicksort algorithm , وهنشوف إنه أفضل algorithm شفناة لغاية دلوقتي , أولا ال Quicksort فيه ميزة ال sort in place زي ال Heap sort وعكس ال Merge sort , واحنا عارفين إن sort in place معناها إنه بيرتب في نفس ال data structure اللي فيها مجموعة الأرقام , وبمعنى أكثر دقة ال algorithm بيكون sort in place لما بيكون بيحتاج عدد constant من أماكن تخزين إضافية , يعني لو فيه algorithm بيحتاج يحجز array من 10 أرقام بالتحديد(عدد constant) كسعة تخزين إضافية أثناء تنفيذه فهو مازال sort in place , أما لو بيحتاج يحجز array من عدد n / 2 (حيث إن n دخل ال algorithm) فهنا n / 2 مش constant وبالتالي ال algorithm مش sort in place.

بالرغم من إن ال Quicksort ال worst-case running time بتاعه بيساوي Θ(n²) وده asymptotically كبير جدا , وده لو فاكرين هو ال worst-case running time بتاع ال Insertion sort , إلا إن ال average-case running time أو ال expected running time بتاعه بيساوي Θ(nlgn) وده ال running time بتاع ال merge sort لو فاكرين , طيب إيه اللي بيخلي ال Quicksort أفضل من ال Merge sort وال Heap sort؟ 

1. ال Quicksort زي ماقلنا sort in place وبالتالي دي ميزة مش موجودة في ال Merge sort.
2. ال Quicksort في التنفيذ in average-case بيكون أسرع من ال Merge sort وال Heap sort وده لإن ال constants الموجودة في ال Θ(nlgn) صغيرة مقارنة بال constants في حالة ال Merge وال Heap.
3. ال worst-case بتاع ال Quicksort نقدر نتجنبها تماما من خلال technique ال randomizationاللي شفناه في الفصل الخامس(وهنشوف الكلام ده بالتفصيل بإذن الله).  

Description of Quicksort

ال Quicksort بيشتغل بطريقة ال divide-and-conquer اللي اتعرضنا ليها في الفصل التاني وهي الطريقة اللي بيشتغل بيها ال Merge sort , الطريقة هي عبارة عن 3 خطوات : divide, conquer, and combine , يعني بنقسم المشكلة لأجزاء(divide) ونحل كل جزء لوحده بنفس الطريقة(conquer) وبعدين نجمع الأجزاء دي مع بعض(combine), ال Merge sort كان بيعتمد على خطوة ال merge او ال combine بمعنى انه كان بيرتب في خطوة ال merge , أما ال Quicksort بيعتمد على خطوة ال divide بمعنى انه بيرتب في خطوة ال divide , إزاي؟ معانا array عدد عناصرها n , بنقسم ال array دي ل 3 أجزاء: جزء عبارة عن عنصر واحد وهنسميه pivot , وجزء على يمين ال pivot عبارة عن مجموعة عناصر قيمة كل عنصر فيها أكبر من قيمة ال pivot , وجزء على شمال ال pivot عبارة عن مجموعة عناصر قيمة كل عنصر فيها أصغر من قيمة ال pivot , دي خطوة ال divide , وعلشان فيها بنقسم ال array فبنسمي الخطوة دي partition , بعد الخطوة دي نحل الجزء اللي على اليمين لوحده والجزء اللي عالشمال لوحده بنفس الطريقة recursively , ودي خطوة ال conquer , في خطوة ال combine مش محتاجين نعمل حاجة , ليه؟ لإن العناصر اللي عالشمال أصغر من ال pivot والعناصر اللي عاليمين أكبر من ال pivot وبالتالي لو العناصر اللي عالشمال والعناصر اللي عاليمين اترتبت النتيجة هتكون array مرتبة , على سبيل المثال لو معانا ال array دي:

A = {8, 11, 3, 18, 13, 5, 10} 

وعملنالها partition فنتجت ال array دي

A = {8, 3, 5, 10, 13, 11, 18} 

ال pivot = 10 , لو رتبنا الجزء اللي على شمال ال pivot هتنتج ال array دي

A_left = {3, 5, 8}

لو رتبنا الجزء اللي على يمين ال pivot هتنتج ال array دي

A_right = {11, 13, 18} 

اجمع ال 2 arrays مع ال pivot

A_ordered = {3, 5, 8, 10, 11, 13, 18}

وبالتالي مش محتاجين نعمل حاجة في خطوة ال combine.

وبالتالي ال Quicksort هيكون بالشكل ده :

ال algorithm بيجيله دخل عبارة عن ال array للي هتترتب (A) و ال index اللي بيحدد بداية الجزء اللي هيترتب في ال call دي (p), وال index اللي بيحدد نهاية الجزء (r).

•   سطر 1 بنتأكد إن اللي جايلنا في ال call دي هو أكتر من عنصر لإن لو عنصر واحد فأنا مش محتاج أعمل أي حاجة.
• سطر 2 بيعمل partition وال partition بيرجع ال index بتاع ال pivot .
• سطر 3 و 4 بيعمل recursive call لل Quicksort على الجزء الشمال والجزء اليمين. 

فاضل ال procedure اللي هيعمل partition , في ال procedure ده هيجيلنا نفس الدخل اللي جه لل Quicksort , وعايزين نرتب ال array ل 3 أجزاء ونرجع ال index بتاع ال pivot , طبعا فيه أكتر من طريقة لعمل ال procedure ده وكل واحد ممكن يكتب procedure بنفسه وممكن تقارن بينهم من خلال تنفيذ ال algorithm بأكتر من procedure وتقيس ال time بتاع ال algorithm مع كل procedure , ال procedure اللي هنشوف ال pseudocode بتاعه دلوقتي يعتبر efficient جدا.

الصورة دي بتوضح ال procedure بيشتغل إزاي , في ال procedure ده بيختار ال pivot كاخر عنصر في ال array , اللي مسميه x , وطبعا ال p هو index بداية ال array و r هو index نهاية ال array , ال index j هو اللي هنلف بيه على عناصر ال array وبالتالي هيقسم ال array لجزئين: الجزء اللي على شماله اترتب والجزء اللي على يمينه بما فيهم المكان اللي هو بيشاور عليه لسة مترتبش(unrestricted) , في الجزء اللي اترتب محتاجين index يوضح المكان المظبوط لل pivot بحيث لما اخلص انقل ال pivot في مكانه الصحيح , وال index ده هو i في كل iteration هيكون الجزء اللي شمال ال i بما فيهم المكان اللي هو بيشاور عليه أصغر من ال pivot والجزء اللي يمين ال i أكبر من ال pivot , وفي كل iteration بختبر العنصر اللي بيشاور عليه j لو هو أكبر من ال pivot يبقى هو في مكانه الصحيح(يمين ال i) وما إلا هزود ال j بواحد وأكمل , أما لو هو أصغر من ال pivot فهنا محتاج ازود ال i بواحد فيشاور على عنصر أكبر من ال pivot وبعدين اعمل swap بينه وبين العنصر ده, وهكذا , لغاية ما اعدي على العناصر كلها من أول عنصر للعنصر اللي قبل الأخير(قبل ال pivot) وفي النهاية أعمل swap بين ال pivot والمكان اللي بيشاور عليه i + 1 لإن من ال i ونازل أصغر من ال pivot ومن ال i + 1 وطالع أكبر من ال pivot وبالتالي ال pivot في مكانه الصح , وفي النهاية اعمل return لل index بتاع ال pivot اللي هو i + 1.

وده ال pseudocode اللي بيعمل الحوار ده:

• سطر 1 بيحدد ال pivot وهو اخر عنصر في ال array اللي ال index بتاعه r.
• سطر 2 بيعمل initialization لل i ومخليه p - 1 علشان ال i بيشاور على عنصر أكبر من الpivot وهو لسة مختبرش العنصر الأول. 
• سطر 3 بيلف على عناصر ال array ماعدا ال pivot. 
• سطر 4 بيقارن العنصر بتاع ال iteration الحالي مع ال pivot. 
• سطر 5 لو كان أصغر من ال pivot هيزود ال i بواحد.
• وسطر 6 هيعمل swap بين العنصر اللي بيشاور عليه ال i (بعد ما زوده بواحد) مع العنصر اللي بيشاور عليه ال j بتاع ال iteration الحالي. 
• سطر 7 بيكون خرج من ال loop فبيعمل swap بين العنصر اللي ال index بتاعه i + 1 وال pivot فييجي ال pivot في مكانه الصحيح. 
•  سطر 8 بيرجع ال index بتاع ال pivot بعد محطه في مكانه الصحيح. 

والصورة دي بتوضح تنفيذ ال Partition procedure على ال array دي:

A = {2, 8, 7, 1, 3, 5, 6, 4}

من الواضح جدا إن ال running time بتاع ال Partition procedure بيساوي O(n) ﻷنه بي loop على array عدد عناصرها كحد أقصى n وبينفذ في كل مرة O(1) instructions.

وده implementation لل Quicksort بلغة ال C :

https://github.com/hossamnasser938/Introduction-to-Algorithms-TextBook/blob/master/quick_sort.c

Performance of Quicksort

ال performance بتاع ال Quicksort بيعتمد على ال partitioning أو القسمة اللي بيقسمها ال pivot لل array في كل call, بمعنى ان لو ال partitioning كان balanced (متزن يعني بيقسم ال array لجزئين حجمهم قريب من بعض) هيكون ال running time بتاعه Θ(nlgn) , أما لو ال partitioning كان unbalanced (غير متزن جدا يعني ال array بتتقسم لجزء كبير جدا وجزء صغير جدا) فكدة ال running time هيكون Θ(n²) , كدة عندنا 3 حالات :

Worst-case Partitioning

ال worst-case بتحصل في حالة انه كل مرة بيقسم ال array لجزء بيساوي n-1 وجزء بيساوي صفر وبالتالي هو مقسمش أصلا , والحالة دي بتحصل (في حالتين فقط) لما ال array تكون sorted أو reversely sorted يعني مرتبة تصاعديا أو تنازليا , لإن في الحالتين هيكون ال pivot(اخر عنصر في ال array) إما أكبر عنصر أو أصغر عنصر وبالتالي أما المجموعة اللي أصغر منه أو اللي أكبر منه مفهاش عناصر , وبيكون ال recurrence اللي بيوصف ال running time في الحالة دي بالشكل ده:

T(n) = T(n - 1) + T(0) + Θ(n)

T(n) = T(n - 1) + Θ(n)

باستخدام ال substitution method ممكن نثبت إن ال recurrence ده بيساوي Θ(n²).

 Best-case Partitioning

ال best-case بتحصل في حالة إنه كل مرة بيقسم ال array لنصفين متساويين (n / 2 , n / 2 - 1) , وفي الحالة دي ال running time ممكن نوصفه بال recurrence ده :

T(n) = 2T(n / 2) + Θ(n)

وباستخدام ال master method ممكن بسهولة نثبت ان ال recurrence ده بيساوي O(nlgn).

Balanced Partitioning

إمتى نقول ان ال partitioning ده balanced أو لأ؟ أو السؤال بشكل تاني أمتى ال running time بتاع ال Quick sort بيكون Θ(nlgn) وإمتى بيكون Θ(n²) ؟

لو فرضنا إن ال partitioning كل مرة بيقسم ال array بنسبة 1 : 9 يعني بيقسم ال array لجزئين: جزء منهم (1/10)n والتاني (9/10)n , القسمة دي واضح انها unbalanced , إلا إننا لو حسبنا ال running time في الحالة دي هيكون O(nlgn) يعني balanced.

في الحقيقة حتى لو القسمة كانت 1 : 99 هتكون balanced وده اللي بيخلي ال Quicksort قوي جدا.

 

A randomized version of quick sort

زي ما شفنا إن ال Quicksort من الصعب جدا انه يشتغل في ال worst-case , إلا فحالة واحدة إن ال array تكون sorted أو reversely sorted , طيب إزاي نحل المشكلة دي؟ شفنا في الفصل التالت technique اسمه randomization , ممكن نستخدم ال technique ده علشان نحل المشكلة بتاعتنا , بإننا نحول ال algorithm من Quicksort ل Randomized_Quicksort , وده بيحصل بإننا بدل منختار ال pivot كآخر عنصر في ال array دايما نختار ال pivot بشكل random , وبالتالي حتى لو ال array جت مرتبة , أنا بختار ال pivot بشكل عشوائي فال algorithm هيكون في ال average-case . فيه طريقة سهلة جدا لتحويل ال Quicksort ل Randomizes_Quicksort من غير منغير ال procedures اللي استخدمناها, وهي اننا نعمل swap مابين العنصر الاخير وعنصر عشوائي من ال array كأول خطوة في ال Partition ونكمل ال Partition زي ماهو.

وبالتالي ال Randomized_Partition وال Randomized_Quicksort هيكونوا بالشكل ده:

وده implementation لل Randomized Quicksort بلغة ال C :

https://github.com/hossamnasser938/Introduction-to-Algorithms-TextBook/blob/master/randomized_quick_sort.c

Enhancement

أسرع algorithm لمشكلة ال counting في حالة إن الدخل قليل _وقليل أقصد بيها في حدود ال 100 عنصر_ هو ال Insertion sort , يعني في حالة إن الدخل 100 أو أقل ال Insertion sort بيكون أسرع في التنفيذ من ال Quicksort , وبالتالي ممكن نحسن أداء ال Quicksort من خلال إننا نستخدم ال Quicksort لما يكون الدخل كبير ولما نوصل لدخل 100 أو أقل نستخدم ال Insertion sort , وده بالتجربة فعلا أسرع من استخدام ال Quicksort فقط. وده Implementation بلغة ال C :

https://github.com/hossamnasser938/Introduction-to-Algorithms-TextBook/blob/master/quick_sort_with_insertion.c