List Partitioning

I am not well trained into solving algorithms but from time to time this topic raises my interest and I find my self drawn into wanting to understand the underlying logic. I recently found a problem that I found to interresting to solve, it’s a Microsoft engineer interviewing question and I followed along the question and the solution and I might say the following:

• I am a bit disappointing that the interviewer was only focused on having the problem solved in his own way
• The solution is not the best

The problem to solve was:

Given a list of integers L and a number K, write a function to partition L into elements that are <K, =K, >K. There is no need for the partions to be sorted, so a sorting algorithm is out of question because it’s not efficient in this case.

E.G.

Given a list 4 5 3 2 1 0 and K = 3 we need to rearrange the list L to be  2 1 0 3 4 5 (more or less. Important is that 3 is in the middle, smaller values on the left, higher values on the right).

Having this in mind, I tried to understand the solution from the Microsoft interview worked, I implemented it and then…I wrote a my own solution, a custom approach and compared the results:

I ran the 2 methods and checked the output:

  static void PartitionKBasedMicrosoftSolving(int[] array, int k)
        {
            void Swap(ref int[] arr, int index1, int index2)
            {
                int swap = arr[index2];
                arr[index2] = arr[index1];
                arr[index1] = swap;
            }

            int mid = 0;
            int s = 0;
            int l = array.Length - 1;

            while (mid < l)
            {
                if (array[mid] < k)                 {                     Swap(ref array, s, mid);                     s++;                     mid++;                 }                 else if (array[mid] >= k)
                {
                    Swap(ref array, l, mid);
                    l--;
                }
                else
                {
                    mid++;
                }
            }
        }

 static void PartitionKBasedCustom(int[] array, int k)
        {
            void Swap(ref int[] arr, int index1, int index2)
            {
                int swap = arr[index2];
                arr[index2] = arr[index1];
                arr[index1] = swap;
            }

            //4 5 3 2 1 2 = 1
            //2 5 3 2 1 4 = 2
            //2 1 3 2 5 4 = 3
            //2 1 2 3 5 4 = 4

            int mid = array.Length / 2;

            for (int i = 0, j = array.Length - 1;
                     i < array.Length - mid                      && j >= mid;
                     i++, j--)
            {
                if (array[i] > array[j])
                {
                    Swap(ref array, i, j);
                }
            }
        };

To understand the microsoft interview solution you can follow the link: https://www.youtube.com/watch?v=UaI3WeesCoE&list=RDCMUCNc-Wa_ZNBAGzFkYbAHw9eg&start_radio=1&t=2433

What I did is to write in code what my brain did when solving this in my head:

• iterate the list from left to mid, and from right to mid
• when an element on the left is greater then an element from the right, swap them

This might not be a stellar test but i ran a couple of arrays against the 2 methods and the results show that my simple approach is about 4 times faster:

 int count = 1000000;
            int seed = 0;

            //a list of random arrays
            List<int[]> randomArrays = Enumerable.Range(0, count).Select(x =>
                Enumerable
                    .Range(0, new Random(seed++).Next(0, 1000))
                    .Select(x => x)
                    .ToArray()).ToList();

            //timing my method
            Stopwatch stopwatch = new Stopwatch();
            stopwatch.Start();

            for (int i = 0; i < 1000000; i++)
            {
                PartitionKBasedCustom(randomArrays[i], 3);
            }
            stopwatch.Stop();
            Console.WriteLine(stopwatch.ElapsedMilliseconds);

            //timing the classical method
            stopwatch.Restart();
            for (int i = 0; i < 1000000; i++)
            {
                PartitionKBasedMicrosoftSolving(randomArrays[i], 3);
            }
            stopwatch.Stop();

            Console.WriteLine(stopwatch.ElapsedMilliseconds);