Getting Started with Adobe After Effects - Part 6: Motion Blur


Upload Image Close it
Select File

Browse by Tags · View All
BRH 58
#ASP.NET 55
ASP.NET 50
#DOTNET 49
.NET 40
WCF 21
DOTNET 12
c# 8
windows azure 7
SILVERLIGHT 7

Archive · View All
April 2011 9
March 2011 9
February 2011 8
December 2010 7
November 2010 5
September 2010 5
August 2010 5
May 2011 4
October 2010 4
January 2011 2

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

Oct 7 2010 8:46AM by Dhananjay Kumar   

Binary search is the example of divide and conquer algorithm . This is best algorithm with running time of Log base 2 n . In this article we will see , how could we use this algorithm to insert an element in sorted list while marinating the sorted order of the list.

I got a mail asking,

“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;
usingSystem.Collections.Generic;
usingSystem.Linq;
usingSystem.Text;
usingSystem.Collections.ObjectModel;


namespace ConsoleApplication21
{
    classProgram
    {
        staticvoid Main(string[] args)
        {

            ListlstMyString = newList();
            lstMyString.Add("Apple");
            lstMyString.Add("Mango");
            lstMyString.Add("Banana");
            lstMyString.Add("papya ");
            lstMyString.Sort();
            foreach (var r inlstMyString)
            {
                Console.WriteLine(r);
            }
            Console.ReadKey(true);

        }  
    }
}

Output

clip_image004

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

stringstrToInsert = "Cashew"; 
intbinraySearchIndex =  lstMyString.BinarySearch(strToInsert);

if (binraySearchIndex< 0)
{
    lstMyString.Insert(~binraySearchIndex, strToInsert);
}

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
{
    classProgram
    {
        staticvoid Main(string[] args)
        {
            ListlstMyString = newList();
            lstMyString.Add("Apple");
            lstMyString.Add("Mango");
            lstMyString.Add("Banana");
            lstMyString.Add("papya ");
            lstMyString.Sort();
			
            stringstrToInsert = "Cashew"; 
            intbinraySearchIndex =  lstMyString.BinarySearch(strToInsert);

            if (binraySearchIndex< 0)
            {
                lstMyString.Insert(~binraySearchIndex, strToInsert);
            }
            foreach (var r inlstMyString)
            {
                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

classProduct
{
    publicstringProductName { get; set; }
    publicintProductPrice { get; set; }
}

And List of Product as below,

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

Now first let us sort this list.

prdList.Sort(compare.Compare);

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.

int search = 0;
ProductproductToInsert = new Product { 
                           ProductName = "Ball", 
                           ProductPrice = 30 };
search = prdList.BinarySearch(productToInsert, (IComparer<product>)compare);

if (search < 0)
{
    prdList.Insert(~search, productToInsert);
}

Program.cs

using System;
usingSystem.Collections.Generic;
usingSystem.Linq;
usingSystem.Text;
usingSystem.Collections.ObjectModel;


namespace ConsoleApplication21
{
    classProgram
    {
    staticvoid Main(string[] args)
        {
            inttempPrevious = 0;
            inttempcurrent = 0;
            IComparer compare = newCompareProduct();
            List<Product>prdList = newList<Product>()
            {
                newProduct {ProductName = "Apple",ProductPrice = 101},
                newProduct {ProductName = "Apple",ProductPrice = 99},
                newProduct {ProductName = "Pen",ProductPrice = 99},
                newProduct {ProductName = "Pencil", ProductPrice = 100},
                newProduct {ProductName ="Apple", ProductPrice = 100}, 
                newProduct { ProductName = "Mango", ProductPrice = 35},
                newProduct {ProductName = "Shirt", ProductPrice=200}
            } ;

            prdList.Sort(compare.Compare);

            int search = 0;
            ProductproductToInsert = new Product { 
                                       ProductName = "Ball", 
                                       ProductPrice = 30 };
            search = prdList.BinarySearch(productToInsert, (IComparer<product>)compare);

            if (search < 0)
            {
                prdList.Insert(~search, productToInsert);
            }

            foreach (Productp inprdList)
            {
                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

classCompareProduct : IComparer
{
    publicint Compare(  Product p1,   Product p2)
    {
        int result;
        if (Product.ReferenceEquals(p1, p2))
        {
            result = 0;
        }
        else
        {
            if (p1 == null)
            {
                result = 1;
            }
            elseif (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; 
    }
    intStringCompare(stringstrFirstString, stringsecondString)
    {
        int result;
        if (strFirstString == null)
        {
            if (secondString == null)
            {
                result = 0;
            }
            else
            {
                result = 1;
            }
        }
        else
        {
            result = strFirstString.CompareTo(secondString);
        }
        return result;
    }
    intNumberCompare(int number1, int number2)
    {
        int result;
        if (number1 > number2)
        {
            result = 1;
        }
        elseif (number1 < number2)
        {
            result = -1;
        }
        else
        {
            result = 0;
        }
        return result;
    }

Tags: #DOTNET, DOTNET, #ASP.NET, ASP.NET, BRH,


Dhananjay Kumar
49 · 4% · 1198
0
Liked
 
0
Lifesaver
 
0
Refreshed
 
0
Learned
 
0
Incorrect



Submit

1  Comments  

  • Very Nice Example . Thanks for your effort and service to Human Being.

    commented on Oct 28 2010 9:49AM
    anwar701
    1606 · 0% · 12

Your Comment


Sign Up or Login to post a comment.

    Copyright © Rivera Informatic Private Ltd Contact us      Privacy Policy      Terms of use      Report Abuse      Advertising      [ZULU1097]