Interview Question #6 – Three way partition – generic solution

15 בפברואר 2009

10 תגובות

This post is a part of the Interview Question Series posts.

Three way partition?! Is there a two way partition or a four way partition ?!

Well X way partition problems are simply dividing the array/collection into X compartments each with it's own distinct feature/property.

One way compartment sort is too simple (just return the array without doing anything) 🙂

Two compartments are not difficult as well – you just need to pointers one to the left side one to the right side and you advance the pointers from both sides towards middle when you can't move you swap between them. And the main loop is running while the left side hasn't crossed the right side. If you want the code just drop me a line…

The complexity is greatly increases when the number of compartments is more then two (and you bound to a memory complexity of O(1) – otherwise one could create a list per compartment, go through the source array and map the items to the corresponding list and at the end just merge the lists by the needed order).

So, what are our options – we can sort using some sort efficient sort – O(NlogN). Quite good but can we do better ? The answer is yes (otherwise I wouldn't bother…)

   1: namespace Question6_ThreeWayPartition
   2: {
   3:   /// <summary>
   4:   /// Question: When given unsorted array of integers sort the array so that in the beggining will be all
   5:   /// the negative numbers (unordered), then zeros and then all the positives (unordered)
   6:   /// </summary>
   7:   class Program
   8:   {
   9:     static void Main(string[] args)
  10:     {
  11:       //test the sorting using 10 random arrays
  12:       for (int i = 0; i < 10; i++)
  13:       {
  14:         //generate the random array and a copy (in order to test in the two methods)
  15:         int[] array = Generate(15);
  16:         
  17:         //print the original
  18:         Console.Write("\nOrigianl array: ");
  19:         PrintArray(array);
  20:  
  21:         SortUsingThreeWayPartition(array);
  22:         Console.Write("\nModified array: ");
  23:         PrintArray(array);
  24:       }
  25:  
  26:       Console.ReadLine();
  27:     }
  28:  
  29:     /// <summary>
  30:     /// Random array generator (range is [-3,3])
  31:     /// </summary>
  32:     /// <param name="length">size of array</param>
  33:     /// <returns>the array</returns>
  34:     private static int[] Generate(int length)
  35:     {
  36:       int[] array = new int[length];
  37:       Random randomGenerator = new Random();
  38:       for (int i = 0; i < array.Length; i++)
  39:       {
  40:         array[i] = randomGenerator.Next(-3, 4); //between -3 and 3 in order to give enough chance for the zeros
  41:       }
  42:       return array;
  43:     }
  44:  
  45:     /// <summary>
  46:     /// Sorting method
  47:     /// </summary>
  48:     /// <param name="array"></param>
  49:     public static void SortUsingThreeWayPartition(int[] array)
  50:     {
  51:       int firstPartition = 0, secondPartition = 0, thirdPartition = array.Length - 1;
  52:  
  53:       while (secondPartition <= thirdPartition)
  54:       {
  55:         if (array[secondPartition] > 0)
  56:         {
  57:           Swap(array, secondPartition, thirdPartition--); //move to the third partition
  58:         }
  59:         else if (array[secondPartition] < 0)
  60:         {
  61:           Swap(array, firstPartition++, secondPartition++); //move to the first partition
  62:         }
  63:         else
  64:         {
  65:           secondPartition++; // leave in the second partition
  66:         }
  67:       }
  68:     }
  69:  
  70:     /// <summary>
  71:     /// Swaps between two values in array
  72:     /// </summary>
  73:     /// <param name="array"></param>
  74:     /// <param name="i"></param>
  75:     /// <param name="j"></param>
  76:     private static void Swap(int[] array, int i, int j)
  77:     {
  78:       if (i == j)
  79:         return;
  80:  
  81:       int temp = array[i];
  82:       array[i] = array[j];
  83:       array[j] = temp;
  84:     }
  85:     
  86:     /// <summary>
  87:     /// Simple method that prints the array
  88:     /// </summary>
  89:     /// <param name="array"></param>
  90:     private static void PrintArray(int[] array)
  91:     {
  92:       foreach (int i in array)
  93:       {
  94:         Console.Write(i);
  95:         Console.Write(" ");
  96:       }
  97:       Console.WriteLine();
  98:     }
  99:   }
 100: }

You can generalize the algorithm using generics by providing a mapping function that maps the item to specific compartment (1, 2 or 3)  as following:

   1: /// <summary>
   2: /// Sorting method
   3: /// </summary>
   4: /// <param name="array"></param>
   5: /// <param name="mapper">mapping function where to move the item:
   6: /// 1 - 1st partition 
   7: /// 2 - 2nd partition
   8: /// 3 - 3rd partition
   9: /// </param>
  10: /// <typeparam name="T">array item type</typeparam>
  11: public static void SortUsingThreeWayPartition<T>(T[] array, Func<T, int> mapper)
  12: {
  13:   int firstPartition = 0, secondPartition = 0, thirdPartition = array.Length - 1;
  14:  
  15:   while (secondPartition <= thirdPartition)
  16:   {
  17:     int partition = mapper(array[secondPartition]);
  18:     switch (partition)
  19:     {
  20:       case 1:
  21:         Swap(array, firstPartition++, secondPartition++); //move to the first partition
  22:         break;
  23:       case 2:
  24:         secondPartition++; // leave in the second partition
  25:         break;
  26:       case 3:
  27:         Swap(array, secondPartition, thirdPartition--); //move to the third partition
  28:         break;
  29:     }
  30:   }
  31: }
  32:  
  33: /// <summary>
  34: /// Swaps between two generic items in array
  35: /// </summary>
  36: /// <typeparam name="T">array item type</typeparam>
  37: /// <param name="array"></param>
  38: /// <param name="i"></param>
  39: /// <param name="j"></param>
  40: private static void Swap<T>(T[] array, int i, int j)
  41: {
  42:   if (i == j)
  43:     return;
  44:   T temp = array[i];
  45:   array[i] = array[j];
  46:   array[j] = temp;
  47: }

And in order to solve the problem above all you need is to create the correct mapping as following:

   1: //For the problem above you can using the following code:
   2: SortUsingThreeWayPartition<int>(arrayCopy,
   3:   //mapper anonymous function
   4:   (num) => 
   5:   {
   6:     //if num is negative - map to the 1st partition
   7:     if (num < 0)
   8:       return 1;
   9:     //if num is zero - map to the 2nd partition
  10:     else if (num == 0)
  11:       return 2;
  12:     //if num is positive - map to the 3rd partition
  13:     else return 3;
  14:   });
הוסף תגובה
facebook linkedin twitter email

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *

10 תגובות

  1. Michael22 בפברואר 2013 ב 8:16

    Wouldn't
    while (secondPartition < thirdPartition) be sufficient as opposed to while (secondPartition <= thirdPartition) ? Besides, are you going to post on n-way partinioning as well? Thanks

    הגב
  2. vevinvddj22 באפריל 2013 ב 1:29

    Speaking of packing, I was thrilled when I found out the lens treatments were also saltwater safe, making them great for lying out on the beach. The lenses are also layered with a silicon-based hard coat, which makes them virtually scratch-proof, once again great for sandy excursions. These shades have all the stylishness you would expect from a top sunglasses manufacturer, but they're also more flexible, so you don't have to be ultra delicate with them. [url=http://www.cheapraybanssunglassesuk.com/]cheap ray ban sunglasses uk[/url]
    So enigmatic and revered a figure is he, Dylan's life would seem ripe for a 'Walk the Line'-style music biopic were it not for the fact that his story is so complex and so shrouded in myth and secrecy. Where would you start? How long would you have? How would you distinguish the truth from the myth? [url=http://www.cheapraybans-uk.com/]read more[/url]
    Narciso Rodriguez receive a gift with your purchase, 6 to 11. [url=http://www.cheapraybans-uk.com/]ray ban wayfarer sunglasses[/url] I want [the collection] to show the different layers of what makes me who I am. I thought it would be good to do something that was high-end streetwear, based around the whole Americana storm that is happening now.

    הגב
  3. zustinphn22 באפריל 2013 ב 2:30

    Para acrecentar la expectativas, se conoci贸 un video en YouTube donde se puede ver un local gigante, con grandes estantes repletos de las zapatillas de la pel铆cula. Hace aproximadamente un a帽o, varios medios estadounidenses revelaron que Nike hab铆a registrado en la oficina de patentes de los Estados Unidos (US Patent Office) un prototipo de las zapatillas Nike Air Mag similares a las que usaba el personaje de McFly. El modelo patentado contaba con un sofisticado sistema de cierre automatizado, con su propia bater铆a y cargador.
    Check out bizrate for great deals on . [url=http://www.zapatosnikeairmax2013.com/]zapatosnikeairmax2013.com/[/url] Siempre puede ser s煤per simple para colocar sobre y tipos incre铆blemente flexibles de zapatillas de deporte. Siempre se puede ser verdaderamente zapatos ligeros.
    Gilly lacing system provides a supportive fit and glove-like fit. Mesh lining with a removable sockliner for all day comfort. Unitsole foam midsole and outsole construction for lightweight cushioning and comfort. [url=http://www.zapatosnikeairmax2013.com/]read more[/url]
    The week started with defending two-time tournament champ Geoff Ogilvy withdrawing after cutting his hand on coral and needing 12 stitches when he tried to work in a little pre-event surfing. [url=http://www.zapatosnikeairmax2013.com/]nike air max 90 baratas[/url]

    הגב
  4. zustinkjc22 באפריל 2013 ב 3:07

    If your little one has asthma, be sure you take the time to chat with them as to what symptoms of asthma is and what it means to have it. Be aware about consuming your youngster for doctor's meetings, giving medicines, checking diet plan and guarding your child from causes, including part-draft smoke, pollen, animal pollen along with other typical substances. To incorporate an additional sizing into the video marketing campaign incorporate your company's logo.
    Nike has stepped up to the plate with another winner in the Nike Air Max MVP MCS molded baseball cleat. [url=http://www.zapatosnikeairmax2013.com/]nike air max 90[/url] That Executive to bring Spike Rod, a rod one, they are the account. That leaves Third Sister do not cry, said: 'Executive Hugh was evil, I will go home with you The! 'That Executive overjoyed with the Third Sister leaves was home..
    Rubber outsole with Waffle tread pattern for traction. Measurements: ; Weight: 13 oz ; Product measurements were taken using size 7.5, B – Medium. Know when to buy Take the g. [url=http://www.zapatosnikeairmax2013.com/]google site[/url]
    Varios sectores tienen sus luces de alerta encendidas. Es el caso de los empresarios de log铆stica y transporte, donde datos relevados por las entidades que agrupan a las empresas permiten estimar que en febrero hubo una ca铆da interanual de alrededor del 20% en el volumen de cargas transportadas, consecuencia tanto de los menores pedidos para comercios como de la falta de bienes importados para mover. La baja, seg煤n confiaron fuentes del sector, afecta principalmente al interior. [url=http://www.zapatosnikeairmax2013.com/]zapatos nike air max 2013[/url]

    הגב
  5. daixlpsvzhan@gmail.com9 במאי 2013 ב 9:33

    We run u not vice versa so swallow it.

    הגב
  6. missguo792@gmail.com2 ביולי 2013 ב 8:44

    Revis had skipped pre-season training camp demanding to renegotiate. He was scheduled to earn $1 million in the fourth-year of a six-year rookie deal.

    הגב
  7. Sleequabe24 ביולי 2013 ב 2:06

    eople who assist at that rite. I know that I am a poor sinner who needs forgiveness and repentance. The older Mass has helped me to understand that much better than the new form, and this is one of the most important reasons that I think [url=http://buchanancountyparks.com/soccerjerseys.html]wholesale soccer jerseys free shipping[/url] that it is better. July 20, 2010 at 5:52 pm 75 Paul says: Unlike most commentors, I am a little different. Since the age of 3 or 4, I have hardly attended an OF Mass. My parents left the local parish in the early 70 8242 s, I think Communion in the hand was the death nell that was years before it was officially approved . My Parish priest at the time was the only one in the parish who sympathised he gave me a bronze statue of St Paul which is still on my desk as I write But he felt he had to obey his bishop which according to Pope Benedict was not the case at all . So my parents [url=http://buchanancountyparks.com/soccerjerseys.html]cheap soccer jerseys[/url] sought out old retired priests still saying the Trad Mass. My parents believed that the guitars, extraordinary ministers and other abuses of the OF were a mockery and so refused to attend it at all. Sometimes we went 6 months without Mass, but even so, by the time I was about 14 and Masses were almost weekly again, I had learned the Latin almost by heart, and knew the meaning of all the prayers although the depth of meaning in the Traditional liturgy is something else. you can never plumb the depths of it Having a Mass in Latin is not an obstical to understanding except to those with no desire to find out. The only OF Masses I have attended have been funerals. The last one I attended had so much back patting at the beginning, that I felt God was only present insofar as He is 8216 present in the congregation'. It was a shame because there was a little separate chapel off to the side of the church where God really was present, and it would have been a simple matter to invite Him along. I didn't like the thought of Him being left out so I got up and spent the rest of the service in quiet prayer with Our Lord, something I could not do in the main church because of all the noise. Maybe it is because I am not used to thinking about God in an environment where everyone is making a din about how wo

    Article from:
    http://www.evilyoshida.com/User-Inoridiccix

    הגב
  8. scoocairrizix18 בספטמבר 2013 ב 22:33

    BOSSブラック無地の白T BOSSブラックライトグリーンライトグレーのストライプパンツエンポリオアルマーニの靴 [url=http://www.buranndbaggu.com/%E3%83%90%E3%83%BC%E3%83%90%E3%83%AA%E3%83%BC-burberry-%E3%83%90%E3%83%BC%E3%83%90%E3%83%AA%E3%83%BC-%E8%B2%A1%E5%B8%83-c-89_87.html]バーバリー財布[/url]
    2005年には、有名なシャネル255の再発行は、美しさとファッションを作成する際に、設計者の50歳のお祝いにリリースされました。シャネルのハンドバッグは、年間なんとと記録破りの販売をした再発行として、それは大きな驚きでした。本物のために行くのに十分賢明である金と女性を持っている幸運にすべての女性は、彼らが自分の255復刻を持っていたことを確認しました。これは、この古典的なキルトのハンドバッグは、ほとんどの女性のための欲求であり、1つを持つことが、単純に絶対必要であるという単純な事実が起こった。

    הגב
  9. scoocairrizix24 בספטמבר 2013 ב 20:32

    マークジェイコブスの最新ヴォーグバーバリーハンドバッグ [url=http://www.buranndbaggu.com/%E3%83%AB%E3%82%A4%E3%83%B4%E3%82%A3%E3%83%88%E3%83%B3louis-vuitton-%E3%83%8F%E3%83%B3%E3%83%89%E3%83%90%E3%83%83%E3%82%B0-c-40_30.html]ヴィトン バック[/url]
    一緒に両面非常に調和のとれた、ブーティとバーバリーのスカーフは私的財である。

    הגב