Monday, October 22, 2012

Dutch National Flag Problem

Here is the problematic flag:


It certainly does not says what the problem is. It's actually a three way partitioning problem.

Definition: An array A[1..n] needs to be rearranged in such a way that moving from left to right, we see three subgroups in this order: (-∞, low), [low, high], (high, ∞).

Algorithm: I came to this solution while working on a StackOverflow question about rearranging an array in such that all the elements less than zero are in left zero; and all the elements greater than zero lies to the right of it. My initial intuition was that I can do it by the improvising the partition part of Quicksort mechanism. It turns out while partitioning works for single pivot element. If you have a dupe of pivot, it may not work.

So, here is algorithm for three way partitioning:
A[1..n]

def three-way-part (A, low, high):
  left = 0
  right = n+1
  i = 1
  
  while i < right :
    if A[i] < low :
      swap(i, ++left)
    else if A[i] > high :
      swap(i, --right)
    else :
      i++
Complexity: Time complexity: O(n), space complexity: O(1)

Footnote:
[1] View longer discussion at Wikipedia
[2] View/download Java code from GitHub

2 comments:

  1. there is no any color comparison (i.e red,white,blue)

    ReplyDelete
  2. من الخدمات التي لا تقل أهمية عن كافة الخدمات التي تقدمها شركة تنظيف بالبخار بالرياض http://url.ie/13xnj هي تنظيف موكيت ,ولأننا جميعاً نعلم أن الموكيت سهل التلف للغاية إذا تم غسله أو تنظيفه بطريقة غير صحيحة فتقوم شركتنا بتوفير هذه الخدمة على قدر عالي من الجودة باستخدام أجهزة تنظيف بالبخار على أعلى مستوى حتى يعود الموكيت نظيفاً وجديداً بدون أي تلف أو خسائر. .… اقرأ المزيد

    المصدر: شركة تنظيف بالبخار بالرياض

    افضل شركة نقل اثاث برابغ  http://url.ie/13xnk طرق نقل العفش برابغ ؟
    تتمكن الشركة من القيام بأعمال نقل العفش برابغ اعتمادا على مجموعه من أفضل الطرق والأساليب ؛فقط يمكن الحديث عن أبرز الطرق :

    1-الاعتماد على الأوناش الحديثة
    تعتبر الأوناش الحديثة سواء الكهربية والهيدرليكية من أهم الأساليب المعتمد عليها فى أعمال نقل العفش ؛تلك الأوناش تتمكن من الوصول الى الأماكن الاكثر ارتفاعا بسهوله كبيرة ويتم الوصول الى النوافذ والقيام بأعمال نقل صحيحة ومميزة ؛فالأوناش توفر الوقت والجهد للقيام بأعمال النقل دون تعرض الاثاث لأى خدوش أو تكسير .

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

    2-الاعتماد على السيارات الحديثة
    تعتمد شركة نقل عفش برابغ على مجموعه من السيارات الحديثة ذات الأحجام المختلفه من أجل القيام بأعمال نقل العفش بطريقه صحيحة ؛تلك السيارات تم اعدادها خصيصا من أجل القيام بنقل العفش من مكان الى مكان أخر ؛تلك السيارات لها مجموعه من الأغطية التى تحمى الأثاث بمختلف أشكاله من التعرض للأتربه أو الشوائب أو العوالق الخطيرة ؛كما أن الاثاث سرعان ما يتعرض للأمطار الغزيرة خلال فصل الشتاء .

    تلك السيارات تتمكن من القيام بأعمال نقل العفش من مكان الى مكان أخر ؛كما تتمكن الشركة من الانتقال الى كافه الأماكن واختيار الطرق الممهدة .

    3-الاعتماد على الناقلات
    تعتمد الشركة على مجموعه من أفضل الناقلات الحديثة التى تتمكن من تحمل جميع الأوزان ؛والحفاظ على سلامة المنقولات من مكان الى مكان أخر دون تعرض الاثاث لأى خدوش أو عوالق خطيرة .

    خطوات القيام بأعمال نقل العفش برابغ
    1-أعمال تعبئة العفش
    تعتمد الشركة على مجموعه من أفضل أدوات التعبئة والعلب الكرتونية والحاويات المختلف مساحاتها من أجل القيام بأعمال تعبئة صحيحة تساعد على حمايه الاثاث أو العفش من التعرض للعديد من الكسور والخدوش بأشكالها المختلفه .

    2-أعمال فك وتركيب الاثاث
    هذه الطريقه من أحدث الأساليب المعتمد عليها من أجل نقل الاثاث بطريقه صحيحة منعا للتعرض لأى خدوش أو تلفيات ؛لذلك يتم تفكيك قطع الاثاث الى قطع صغيرة ويتم ترقيمه بأرقام محددة مما يساعد الأمر على سهوله نقله من مكان الى مكان أخر وتركيبه مرة أخرى بعد التفكيك ؛لذلك يتم ترتيب العفش بطريقه صحيحة داخل السيارات من أجل سهوله نزوله مرة أخرى .

    3-أعمال تغليف الاثاث
    تتمكن شركة نقل اثاث برابغ من القيام بأعمال تغليف الاثاث اعتمادا على مجموعه من الأدوات المميزة سواء البطاطين السميكة التى تساعد على حمايه الاثاث من التعرض لأى خدوش أو قطع ؛كما يتم الاعتماد على فريق عمل مميز من أفضل العاملين المتخصصين اللذين لديهم خبرات واسعه فى اختيار أفضل أدوات التغليف من أجل حمايه الاثاث من التعرض للمزيد من الخدوش أو التلفيات أو القطع .

    4-أعمال تخزين العفش
    تعتمد شركة نقل عفش برابغ على مجموعه من أفضل أماكن التخزين سواء مجموعه من المخازن أو المستودعات الكبرى التى تمكن الأفراد من القيام بأعمال التخزين لكافه أشكال الاثاث مهما بلغت أوزانها أو أحجامها .… اقرأ المزيد

    المصدر: شركة نقل اثاث برابغ

    ReplyDelete