Saturday, 21 January 2012

Inserting element in sorted Generic list (List) using binary search in C#

Inserting element in sorted Generic list (List) using binary search in C#


“How we could insert an item in sorted generic list such that after insertion list would be remaining sorted?”

Answer of this is using Binary Search

As we know Binary search works on Divide and conquer algorithm. And running time using Binary search is very efficient.

So we need to follow below algorithm

Step 1
Sort the list

Step 2
Save the value to be inserted in a variable

Step 3
Do the binary search of the inserted variable in the list.
clip_image002

Step 4
Insert the item at the compliment of the number returned by the binary search.

Example #1 inserting a string in sorted list of string.

Program.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections.ObjectModel;
namespace ConsoleApplication21
{
    class Program
    {
        static void Main(string[] args)
        {
            List<string> lstMyString = new List<string>();
            lstMyString.Add("Apple");
            lstMyString.Add("Mango");
            lstMyString.Add("Banana");
            lstMyString.Add("papya ");
          foreach (var r in lstMyString)
            {
                Console.WriteLine(r);
            }
            Console.ReadKey(true);
     }
Output
clip_image004

Now if in above sorted list we need to add one more string item cashew.
clip_image006

So first we need to perform the binary search and then find the index of the next top element by negating the integer returned by the Binary search.

Program.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections.ObjectModel;
namespace ConsoleApplication21
{
    class Program
    {
        static void Main(string[] args)
        {
            List<string> lstMyString = new List<string>();
            lstMyString.Add("Apple");
            lstMyString.Add("Mango");
            lstMyString.Add("Banana");
            lstMyString.Add("papya ");
            lstMyString.Sort();
            string strToInsert = "Cashew";
            int binraySearchIndex =  lstMyString.BinarySearch(strToInsert);
            if (binraySearchIndex < 0)
            {
                lstMyString.Insert(~binraySearchIndex, strToInsert);
            }
            foreach (var r in lstMyString)
            {
                Console.WriteLine(r);
            }
            Console.ReadKey(true);
              }

Ouput
clip_image008


Example #2: Inserting a custom class in list of custom class .

I have a class called Product
Product.cs
   class Product
    {
        public string ProductName { get; set; }
        public int ProductPrice { get; set; }
    }

And List of Product as below,



 List<Product> prdList = new List<Product>()
            {
               new Product {ProductName = "Apple",ProductPrice = 101},
                new Product {ProductName = "Apple",ProductPrice = 99},
                new Product {ProductName = "Pen",ProductPrice = 99},
                new Product {ProductName = "Pencil", ProductPrice = 100},
                new Product {ProductName ="Apple", ProductPrice = 100},
                new Product { ProductName = "Mango", ProductPrice = 35},
                new Product {ProductName = "Shirt", ProductPrice=200}
            };

Now first let us sort this list.

clip_image009
How to sort a Generic List? 

Now in sorted list of Product we need to insert one more product such that it should be inserted in sorted order in the list.

clip_image011
Program.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections.ObjectModel;
namespace ConsoleApplication21
{
    class Program
    {
        static void Main(string[] args)
        {
            int tempPrevious = 0;
            int tempcurrent = 0;
            IComparer<Product> compare = new CompareProduct();
            List<Product> prdList = new List<Product>()
            {
               new Product {ProductName = "Apple",ProductPrice = 101},
                new Product {ProductName = "Apple",ProductPrice = 99},
                new Product {ProductName = "Pen",ProductPrice = 99},
                new Product {ProductName = "Pencil", ProductPrice = 100},
                new Product {ProductName ="Apple", ProductPrice = 100},
                new Product { ProductName = "Mango", ProductPrice = 35},
                new Product {ProductName = "Shirt", ProductPrice=200}
            };
            prdList.Sort(compare.Compare);
             int search = 0;
            Product productToInsert = new Product {
                                        ProductName = "Ball",
                                        ProductPrice = 30 };
            search = prdList.BinarySearch(productToInsert, (IComparer<Product>)compare);
            if (search < 0)
            {
                prdList.Insert(~search, productToInsert);
            }
            foreach (Product p in prdList)
            {
                tempcurrent = p.ProductPrice;
                if (tempcurrent != tempPrevious)
                {
                    Console.WriteLine("**********************");
                    Console.WriteLine("Price = " + p.ProductPrice);
                }
                Console.WriteLine(p.ProductName);
                tempPrevious = p.ProductPrice;
            }
            Console.ReadKey(true);
        }
    }

Output
clip_image013


For reference generic sort class for list of Product is as below


CompareProduct.cs
 class CompareProduct : IComparer<Product>
    {
        public   int Compare(  Product p1,   Product p2)
        {
            int result;
            if (Product.ReferenceEquals(p1, p2))
            {
                result = 0;
            }
            else
            {
                if (p1 == null)
                {
                    result = 1;
                }
                else if (p2 == null)
                {
                    result = -1;
                }
                else
                {
                    result = NumberCompare(p1.ProductPrice, p2.ProductPrice);
                    //result = StringCompare(p1.ProductName, p2.ProductName);
                    if (result == 0)
                    {
                       // result = NumberCompare(p1.ProductPrice, p2.ProductPrice);
                        result = StringCompare(p1.ProductName, p2.ProductName);
                    }
                }
            }
            return result;
        }
         int StringCompare(string strFirstString, string secondString)
        {
            int result;
            if (strFirstString == null)
            {
                if (secondString == null)
                {
                    result = 0;
                }
                else
                {
                    result = 1;
                }
            }
            else
            {
                result = strFirstString.CompareTo(secondString);
            }
            return result;
        }
         int NumberCompare(int number1, int number2)
        {
            int result;
            if (number1 > number2)
            {
                result = 1;
            }
            else if (number1 < number2)
            {
                result = -1;
            }
            else
            {
                result = 0;
            }
            return result;
        }
    }
}
 

Post a Comment