الفصل التاسع

Medians and Order Statistic

مقدمة 

في الفصل ده هنتعرض لمشكلة متشابهة مع مشكلة ال sorting الى حد كبير, المشكلة دي هي مشكلة ال Selection , وبنعرف مشكلة ال selection باستخدام ال Order statistic , في الاول يعني ايه Order statistic? او السؤال بشكل أصح يعني ايه ith order statistic لمجموعة عناصر , ببساطة كدة ال ith order statistic لمجموعة عناصر(غير مرتبة) عددها n هو العنصر اللي فيه عدد عناصر i-1 فقط قيمتهم أقل منه في مجموعة العناصر دي, أو تقدر تقول بعد ترتيب مجموعة العناصر دي هو العنصر اللي ترتيبه i فيهم. يعني كمثال لمجموعة العناصر x:

x = {10, 23, 1, 65, 14, 95, 230}

5th order statistic = 65

لان بعد ترتيب المجموعة x هتبقى:

x` = {1, 10, 14, 23, 65, 95, 230}

العنصر 65 ترتيبه الخامس او فيه 4 عناصر فقط قيمتهم أقل منه في المجموعة , وبالتالي هو ال 5th order statistic.

معنى كدة ان ال 1st order statistic هو اللي بنسميه ال Minimum أو العنصر صاحب أقل قيمة في المجموعة , وأن ال nth order statistic هو اللي بنسميه ال Maximum أو العنصر صاحب أكبر قيمة في المجموعة , فيه حاجة تالتة بنسميها ال Median (الوسيط) وهو العنصر اللي بيقسم مجموعة العناصر ل 3 مجموعات أول مجموعة فيها كل العناصر اللي قيمتها أقل من قيمة ال Median وتاني مجموعة هي المجموعة اللي فيها ال Median فقط وتالت مجموعة فيها كل العناصر اللي قيمتها أكبر من ال Median , يعني كمثال المجموعة x :

x = {10, 23, 1, 65, 14, 95, 230}

Median(x) = 23

لان ال 23 قسم المجموعة ل 3 مجموعات :

x = {1, 10, 14} + {23} + {65, 95, 230}

ال median لمجموعة عدد عناصرها n هو قيمة واحدة لو n عدد فردي وقيمتين بنسميها upper median و lower median لو n زوجي, في حالة الفردي الupper median = lower median

ال median ممكن يتعرف ب ال order statistic كالتالي :

lower median i = ⌊(n + 1) / 2⌋

upper median i = ⌈(n + 1) / 2⌉

المثال اللي فات x كان فيها 7 عناصر يعني n فردي وبالتالي ال lower = upper وهو ال 4th order statistic لان

⌊(n + 1) / 2⌋ = ⌈(n + 1) / 2⌉ = 7 + 1 / 2 = 8 / 2 = 4

لو شفنا مثال لمجموعة عدد عناصرها زوجي:

y = {50, 6, 25, 13, 652, 12, 32, 10} n = 8

y` = {6, 10, 12, 13, 25, 32, 50, 652}

lower median i = ⌊(n + 1) / 2⌋ = ⌊8 + 1 / 2⌋ = ⌊9 / 2⌋ = 4

upper median i = ⌈(n + 1) / 2⌉ = ⌈8 + 1 / 2⌉ = ⌈9 / 2⌉ = 5

lower median = 4th order statistic = 13

upper median = 5th order statistic = 25

ال Minimum وال Maximum وال Median هي measures (قياسات) بتساعدنا نوصف البيانات , يعني مثلا لو عندك بيانات عبارة عن مرتبات موظفين , ممكن أعلى مرتب أو أقل مرتب أو الوسيط للمرتبات يمثل وصف مفيد.

كدة ممكن نعرف مشكلة الـ selection كالتالي:

الدخل : مجموعة عناصر غير مرتبة عدد عناصره n , ورقم i حيث i قيمته بين الـ 1 وال n

الخرج : عنصر من مجموعة العناصر فيه عدد i - 1 من العناصر فقط في المجموعة أقل منه (ith order statistic)

Minimum and Maximum 

في السكشن ده عايزين نشوف ازاي ممكن نجيب الـ Minimum أو الـ Maximum لمجموعة عناصر عدد عناصرها n , لو عايزين نجيب ال Minimum بسهولة ممكن افترض مبدأيا ان اول قيمة هي ال minimum واخزنها واعدي على باقي عناصر المجموعة اقارن كل عنصر مع ال minimum لو العنصر ده اقل من ال minimum اخزنه هو وفي الاخر ارجع ال minimum اللي وصلتله.

لو هنجيب ال maximum التغيير اللي هنعمله بس هو بدل علامة اصغر من في سطر 3 هستخدم اكبر من واغير اسم المتغير ل max علشان المعنى. طبعا واضح ان ال running time بتاع ال algorithm ده عبارة O(n) , وعدد ال comparisons اللي بنعملها هي n - 1.

Simultaneous minimum and maximum 

لو عاوز أجيب ال minimum وال maximum في نفس ال algorithm ممكن أعمل متغيرين min و max والاتنين اساويهم بأول عنصر وأعدي على باقي العناصر , كل عنصر أقارنه بال min وال max وأعدل , وفي الاخر ارجع ال min وال max في array او structure او whatever حسب لغة البرمجة اللي بتستخدمها. هنا برده ال running time عبارة عن O(n) وعدد ال comparisons بيساوي 2n - 2 . هل فيه طريقة أفضل؟

ممكن بدل مبقارن عنصر عنصر أقارن عنصرين عنصرين , بمعنى انا معايا قيمة لل min وقيمة لل max ممكن اعدي على العناصر Pairs عنصرين عنصرين , في كل مرة اقران العنصرين دول واحدد مين الاكبر فيهم واقرانه مع الـ max والاصغر منهم اقارنه مع الـ min وبالتالي انا عملت 3 comparisons بس لكل عنصرين وفي الـ algorithm الاول العادي كنت بعمل 4 comparisons لكل عنصرين وبالتالي في الحالة التانية عدد الـ comparisons الكلي هيكون:

• في حالة ان n عدد زوجي هقارن اول عنصرين ببعض واحدد مين فيهم الـ max ومين الـ min وبعدبن اعدي على باقي العناصر , كل عنصرين هعمل عليهم 3 comparisons , وبالتالي مجموع عدد الـ comparisons هيساوي:

1 + 3 * (n/2 - 1) = 3 * n/2 - 2

• في حالة ان n عدد فردي هنساوي الـ min وال max باول عنصر واعدي على باقي العناصر , كل عنصرين هعمل عليهم 3 comparisons , وبالتالي مجموع عدد الـ comparisons هيساوي: 

3 * ⌊n/2⌋ 

وده imlementation بلغة الـ c لل 4 algorithms اللي شفناهم لغاية دلوقتي:

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

Selection in expected linear time 

طبعا مشكلة الـ selection ممكن تتحل بسهولة باستخدام ما يسمى بال naive algorithm (وكلمة naive معناها ساذج) من خلال انك ترتب مجموعة العناصر في الاول باستخدام أي sorting algorithm وبعدين ترجع العنصر الـ index بتاعه i لانه بعد الترتيب الـ ith order statistic بيكون موجود في الـ index i (ده في حالة الـ 1-based index) , الـ running time بتاع الـ naive algorithm هو الـ running time بتاع الـ sorting algorithm , وبما ان أقل running time ل sorting algorithm بيشتغل بدون أي assumptions على الـ input هو الـ O(nlgn) زي الـ quick_sort وال merge_sort وال heap_sort فهو ده الـ running time بتاع الـ naive algorithm.

بس هل احنا محتاجين نرتب مجموعة العناصر كلها علشان نجيب الـ ith order statistic؟ في الحقيقة لأ مش محتاجين ودلوقتي هنشوف algorithm بيشتغل في average(expected) case running time عبارة عن O(n) أو linear ولكن في worst case running time عبارة عن O(n²) ولكن علشان هو randomized فنقدر نقول ان مفيش input محدد يقدر يخلي الـ algorithm في الـ worst case , وبالتاالي احتمالية انه يشتغل في الـ worst case ضعيفة جدا جدا. الـ algorithm اسمه Randomized_Select وهو مبني على الـ Randomized_Quicksort (الفصل السابع), لو نفتكر في الـ randomized_quicksort كنا بنعتمد على الـ Randomized_Partition subroutine , نفس الـ procedure هنستخدمه في الـ Randomized_Select ولكن بعد منعمل partition هنشوف الـ index بتاع الـ pivot ومن خلاله هنعمل recursion مع جزء واحد بس(الـ pivot بيقسم المجموعة لجزئين) الجزء اللي فيه العنصر اللي احنا عايزينه , يعني كمثال لو احنا عايزين الـ 33th order statistic وعملنا randomized_partition رجعلنا الـ pivot الـ index بتاعه 50 فانا مش محتاج اعمل اي حاجة على العناصر اللي في الجزء اللي فوق الـ pivot , انا متأكد ان العنصر اللي انا عايزه موجود في الجزء اللي تحت الـ pivot.

• الـ algorithm بياخد دخل عبارة عن : A وهي الـ array اللي فيها العناصر, p الـ index اللي بيحدد بداية الجزء بتاع الـ call الحالي, r الـ index اللي بيحدد نهاية الجزء بتاع الـ call الحالي, i هو اللي بيحدد الـ ith order statistic اللي انا عايزه في مجموعة العناصركاملة.
• سطر 1 بي check لو الـ p = r يعني الـجزء الحالي فيه عنصر 1 اذا (سطر 2) رجعه هو اللي انا بدور عليه.
• سطر 3 اعمل partition وخز index الـ pivot في q.
• سطر 4 احسب عدد عناصر المجموعة اللي اقل من الـ  pivot زائد 1 وخزنها في k.
• سطر 5 قارن الـ i بال k لو بيساوو بعض يبقى (سطر 6) رجع العنصر اللي بيشاور عليه الـ pivot (لان معنى ان i بتساوي الـ  k ان الـ pivot فيه عدد i - 1 عناصر اقل منه وبالتالي هو اللي انا عايزه).
• سطر 7 لو i اصغر من الـ k يبقى (سطر 8) recursively نادي على نفس الـ algorith بس مع الجزء اللي اقل من الـ pivot و i مش هيتغير.
• سطر 9 لو i اكبر من الـ k يبقى recursively نادي على نفس الـ algorithm مع الجزؤ اللي اكبر من الـ pivot بس غير الـ i لان بالنسبة للجزء الاكبر من الـ pivot الـ order بتاع i  اتغير , بمعنى انك لو بتدور على 35th order statistic وال pivot بتاعك طلع 25 فترتيب الـ 35th في الجزء الاكبر من الـ pivot (فوق الـ 25) هو الـ 11th.

وده implementation لل Randomized_Select بلغة الـ C:

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

عايزين نعمل analysis لل algorithm بشكل informal بدون maths , الـ running time بتاع الـ algorithm بيعتمد على الـ partitioning , لو الـ partitioning بيتم بشكل stable مثلا 1 : 9 وكل مرة الـ i بيقع في الجزء الكبير هنعبر عن الـ running time بال recurrence ده:

T(n) = T(9/10 n) + O(n)

طبعا باستخدام الـ master theorem الحالة التالتة الحل هيكون O(n) , حتى لو الـ partitioning عبارة عن 1:99 هيبقى بنفس الناتج أول أي constant partitioning زي مشفنا في الـ Quicksort. أما الـ worst case بتحصل في حالة ان دايما الـ partition بينتج جزء فاضي وجزء فيه n - 1 عنصر في الحالة دي بس هنكون في الـ worst case ودي حالة احتمالها ضعيف جدا جدا جدا.

Selection in worst-case linear time 

دلوقتي هنشوف Selection algorithm بيشتغل في الـ worst-case في O(n) , هو مجرد تعديل على الـ Randomized_Select , المشكلة في الـ randomized_select اللي مخلياه بيشتغل في O(n) في الـ expected case مش الـ worst case هو اننا مش قادرين نضمن ان الـ partitioning stable , الفكرة هنا ان انا هنختار مسبقا الـ pivot اللي يخلي الـ partitioning يكون stable ونبعته ك argument لل partition procedure وهو يعمل partition استخدام الـ pivot ده فيكون stable , الـفكرة هنا ان احنا نجيب الـ pivot ده في linear time علشان الناتج يكون linear.

كل اللي غيرناه هو سطر 3 و 4 , احنا بنحسب في الاول الـ median وبعدينه نبعته لل partition procedure علشان يعمل partition عليه وبالتالي نضمن انه stable.

• محتاجين طريقة نجيب بيها الـ median تكون linear time؟ ممكن نقسم الـ array لمجموعات كل مجموعة فيها بحد أقصى 5 عناصر وبعدبن نرتب كل مجموعة باستخدام الـ insertion sort (لانه سريع مع دخل قليل) ونجيب الـ median بعد ترتيبها بسهولة, بعد كدة ن call نفس الـ algorithm وال recurrence الناتج هيكون linear.
• ازاي نعمل partition باستخدام الـ median? انت هيجيلك الـ median ت iterate في الاول على الـ array لغاية متوصله بعدين تعمله swap مع اخر عنصر في الـ array وت call الـ partition procedure العادي اللي شفناه في الفصل السابع(دي طريقة ممكن تشوف طريقة أحسن).

 

وده Implementation لل Quick_select algorithm بلغة الـ C:

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