.NET Tutorials, Forums, Interview Questions And Answers
Welcome :Guest
 
Sign In
Register
 
Win Surprise Gifts!!!
Congratulations!!!


Top 5 Contributors of the Month
david stephan

Home >> Articles >> C# >> Post New Resource Bookmark and Share   

 Subscribe to Articles

Insert element in sorted Generic list using binary search

Posted By:Dhananjay Kumar       Posted Date: September 21, 2010    Points: 25    Category: C#    URL: http://www.dotnetspark.com  

This article shows how we can insert an item into a sorted generic list such that after insertion the list will remain sorted.
 

I got a mail asking:

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


The answer to this is using Binary Search 

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

So we need to follow below algorithm

You can also follow my blog


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.


1.gif 


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 lstMyString = new List();
           lstMyString.Add("Apple");
           lstMyString.Add("Mango");
           lstMyString.Add("Banana");
           lstMyString.Add("papya ");
           lstMyString.Sort();
           foreach (var r in lstMyString)
           {
               Console.WriteLine(r);
           }
           Console.ReadKey(true);
       }
   }
}
          
Output 


2.gif

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


3.gif 


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


namespace ConsoleApplication21
{
   class Program
   {
       static void Main(string[] args)
       {
           List lstMyString = new List();
           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);
       } 
   }
}


Output 


4.gif


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 prdList = new List()
           {
               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. 


5.gif

How to sort a Generic List? Read here 


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. 


6.gif

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 compare = new CompareProduct();
           List prdList = new List()
           {
               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)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 


7.gif 


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


class CompareProduct : IComparer
{
   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;
   }
}


 Subscribe to Articles

     

Further Readings:

Responses
Author: Syed Shakeer Hussain         Company URL: http://www.dotnetspark.com
Posted Date: September 25, 2010

Hi Kumar,
Nice Article and Nice Tip shared on Sorting Items...



Post Comment

You must Sign In To post reply
Find More Articles on C#, ASP.Net, Vb.Net, SQL Server and more Here

Hall of Fame    Twitter   Terms of Service    Privacy Policy    Contact Us    Archives   Tell A Friend