Getting Started with Adobe After Effects - Part 6: Motion Blur
First Time? You can support us by signing up. It takes only 5 seconds. Click here to sign up. If you already have an account, click here to login.
Loading

1st Prize - Apple iPad


DOTNET Quiz 2011 - How to insert an item in sorted generic list such that after insertion list would be sorted?

  • How to insert an item in sorted generic list such that after insertion list would be remaining sorted? Please provide following details. Algorithm Name, Basic Working on of the Algorithm, Advantage and Disadvantages and Better Alternatives.

    A sample working code in .net (C# or VB) will get extra credit.

    Posted on 01-29-2011 00:00 |
    Nupur Dave
    174 · 1% · 284

5  Answers  

Subscribe to Notifications
  • Score
    10

    A simple way to implement a sorted list is a doubly-linked list of items that contain the key (on which items are sorted) and the content (the item itself). To insert an item, you traverse the list, starting at the head, until you find a key that is greater (or equal) to the key to be inserted. Then you open the links and insert the item right before the found item. To implement this, I have created a ListElement that contains the key, the item and references to the respective previous and next item. The first item will have no reference to a previous item, and the last item no reference to a next item. The List itself stores a reference to the head and tail of the list. This is where traversal begins. The IComparable restriction on the TKey parameter is necessary to be able to compare two keys.

            /// <summary>
            /// One Element of the sorted list
            /// </summary>
            /// <typeparam name="TKey">Type of key used</typeparam>
            /// <typeparam name="TContent">Type of content used</typeparam>
            class ListElement<TKey, TContent> where TKey : IComparable
            {
                // who is before me?
                public ListElement<TKey, TContent> Next { get; set; }
                // who comes after me?
                public ListElement<TKey, TContent> Prev { get; set; }
                // my sort key
                public TKey Key { get; set; }
                // my content
                public TContent Content { get; set; }
    
                /// <summary>
                /// Constructor: create an element without references
                /// </summary>
                /// <param name="key">sort value</param>
                /// <param name="content">content value</param>
                public ListElement(TKey key, TContent content)
                {
                    Key = key;
                    Content = content;
                    Next = null;
                    Prev = null;
                }
            }
    

    To hide the implementation details from the user, I have embedded this class into my SortedList, so it is only visible inside the class. The class itself has to handle (among others) insertion, deletion, and traversal of the list. For the question only asks for the insert method, the others are omitted:

        public class SortedList<TKey, TContent> where TKey : IComparable
        {
            class ListElement<TKey, TContent> where TKey : IComparable
            {
                 // see code above
            }
    
            // anchors
            ListElement<TKey, TContent> head;
            ListElement<TKey, TContent> tail;
    
            public SortedList()
            {
                head = null;
                tail = null;
            }
    
            /// <summary>
            /// Insert an element into the sorted list so the list is sorted again after insertion
            /// </summary>
            /// <param name="key">key value (for sort order)</param>
            /// <param name="content">item value</param>
            /// <returns>the list itself</returns>
            public SortedList<TKey, TContent> Add(TKey key, TContent content)
            {
                ListElement<TKey, TContent> newElement = new ListElement<TKey, TContent>(key, content);
                // if no element in the list, this is the first and last one
                if (head == null)
                {
                    head = newElement;
                    tail = newElement;
                    return this;
                }
                // if the new element is less than the head, it becomes the head
                if (((IComparable)head.Key).CompareTo(key) >= 0)
                {
                    newElement.Next = head;
                    head = newElement;
                }
                // find the preceding element
                for (var element = head; element.Next != null; element = element.Next)
                {
                    if (((IComparable)element.Next.Key).CompareTo(key) >= 0)
                    {
                        newElement.Prev = element;
                        newElement.Next = element.Next;
                        element.Next = newElement;
                        return this;
                    }
                }
                // all preceding elements are less than the new: insert at end
                newElement.Prev = tail;
                tail.Next = newElement;
                tail = newElement;
                return this;
            }
        }
    

    The Add method returns the list reference, so multiple adds can be performed in 'fluent' code, like

    public void AddSomeElements()
    {
        SortedList<int, string> list = new SortedList<int, string>();
    
        list
            .Add(2, "two")
            .Add(4, "four")
            .Add(1000, "M");
    }
    

    Discussion: This algorithm is one of the simplest for sorted lists. It is suitable for small lists. Your could improve the insert method to double speed if you held the middle key at class level and decide first whether to traverse the list from head or tail.

    For larger lists, a tree or hash storage for the items would be more appropriate, as you have to traverse the whole list if you want to insert an element at the end, which makes the algorithm O(n).

    Replied on Jan 31 2011 1:38AM  . 
    Guenter
    28 · 6% · 1887
  • Score
    10

    There are already two classes SortedList and SortedDictionary which can be used for this purpose and are sufficient for our needs in most cases. But in case you want your own implementation for any reason, it’s easy to construct your own class.

    The basic concept is: when adding items to the list, find the best position where it can be inserted and insert it there (as opposed to typically adding it to the end of list). For this you can use the built in BinarySearch method. If you know that there would be many items to be added, you can provide an overloaded method that adds items to the end of list and then sorts the array / list after that. This way your list will always be sorted. This would typically be faster than searching for an appropriate position before each item insert for a large set of items.

    Here is a simple implementation. Note that I have shown only the adding and getting the items; I’ve skipped the rest for simplicity of this demo. Additional methods will be required in real scenario. Also I have assumed that a comparer won't be required and default comparer would suffice; but for complex classes, a custom comparer would be required.

    Public Class MySortedList(Of T)
        Private list As List(Of T)
        Public Sub New()
            list = New List(Of T)
        End Sub
        Public Sub New(ByVal ParamArray items() As T)
            list = New List(Of T)
            list.AddRange(items)
            list.Sort()
        End Sub
    
        Public Sub Add(ByVal item As T)
            Dim pos As Integer = list.BinarySearch(item)
            If pos < 0 Then pos = Not pos
            list.Insert(pos, item)
        End Sub
    
        Public Sub AddRange(ByVal item() As T)
            list.AddRange(item)
            list.Sort()
        End Sub
    
        Public Sub Remove(ByVal item As T)
            list.Remove(item)
        End Sub
    
        Public Function Item(ByVal index As Integer) As T
            Return list(index)
        End Function
    
        Public ReadOnly Property Count() As Integer
            Get
                Return list.Count
            End Get
        End Property
    End Class

    For a demo, add a button to a windows form and this code:

    Dim mySortedList As New MySortedList(Of String)
    Dim random As New Random
    
    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
        '' Add a few random items for demo
        For i = 1 To 100
            Dim key As Integer = random.Next(0, 100)
            mySortedList.Add("hello" & i.ToString)
        Next
    
        '' now we list them in the debug window.
        '' observe that the output is sorted.
        For i = 0 To mySortedList.Count - 1
            Debug.WriteLine(mySortedList.Item(i))
        Next
    End Sub

    Clicking the button will add 100 items to an instance of this class and will list them in the debug window. Note that the output in debug window is always sorted.

    Replied on Jan 31 2011 4:46AM  . 
    Pradeep Kumar
    301 · 0% · 145
  • Score
    8

    Here is a very simple resolvation procedure:

    class Program { static void Main(string[] args) { List IntegersList = new List();

            IntegersList.AddRange(new int[] { 8, 2, 11, 11, 4, 0 }); //Add some test data
    
            IntegersList.Sort(); //Sort the list
    
            for (int i = 0; i < IntegersList.Count; i++)
            {
                Console.WriteLine(IntegersList[i]); //Print the list
            }
    
            Console.WriteLine("After Inserting");
    
            int IntegerToInsert = 9; //Value that needs to be added without re-sorting the list.
    
            int PositionToInsert = IntegersList.BinarySearch(IntegerToInsert); //Returns appropriate negated index
    
            IntegersList.Insert(~PositionToInsert, IntegerToInsert); //Negate the negated integer.
    
            for (int i = 0; i < IntegersList.Count; i++)
            {
                Console.WriteLine(IntegersList[i]); //Expected Ouput should equal Actual.
            }
    
            Console.ReadKey(); //Verify the result on the console.
        }
    }
    

    Replied on Feb 10 2011 9:22AM  . 
    Dheeraj
    2381 · 0% · 5
  • Score
    9

    How to insert an item in sorted generic list such that after insertion list would be remaining sorted? This can be achieved using binary search, this runs using divide and conquer principle and its pretty fast.

    Please provide following details. Algorithm Name, Basic Working on of the Algorithm, Advantage and Disadvantages and Better Alternatives.

    • Algorithmname : Binary Search. Binary Search returns a negative integer if item is not found in the list. On putting bitwise complement operator (~) on the returned negative integer, we will get a positive integer.This will be the index for the next element larger than the element searched. And if there is no greater value its total count of the list. Advantage is this will be faster hence its best practice algorithm

    Basic Working : Working example in C#

         namespace BinarySearch
    {
        class Program
        {
            static void Main(string[] args)
            {
                List<string> lstMyString = new List<string>();
                lstMyString.Add("Vamshi");
                lstMyString.Add("Pandu");
                lstMyString.Add("Anirudh");
                lstMyString.Add("Pannu");
                lstMyString.Sort();
                //inserting an item
                string strToInsert = "Chanti";
                int binraySearchIndex =  lstMyString.BinarySearch(strToInsert);
                if (binraySearchIndex < 0)
                {
                    lstMyString.Insert(~binraySearchIndex, strToInsert);
                }
                foreach (var r in lstMyString)
                {
                    Console.WriteLine(r);
                }
                Console.ReadKey(true);
            } 
        }
    
    }
    
    Replied on Feb 14 2011 4:27AM  . 
    Vamshi
    134 · 1% · 376
  • Score
    9

    There are SortedDictionary and SortedList classes defined in .NET library. They both use binary search for retrieval but where the two classes differ is in memory use and speed of insertion and removal. More detailed information about differences can be found in MSDN. Aside from this both of them require TKey values to be unique. I believe if necessary then in the most cases we can solve this issue by changing a key value a bit (e.g. adding suffix) however it might not be the most convenient and efficient solution. In some cases you can even use Hashtable, that might be the fastest option in some scenarious because Hashtable use hash values. Also instead of searching in the whole list, as SortedList and SortedDictionary do, Hashtable uses buckets based on hash value of a key. However I wouldn't consider Hashtable as a generic solution. Aside from this SortedDictionary, SortedList and Hashtable require both key and value that might not be necessary for our task. You can find an article comparing performance of all the approaches described above here.

    It's not very difficult to implement your own sorted list. By doing so you'll also have more control on how to do certain things based on the estimated usage of the list (e.g. if you expect considerably more updates than retrievals, if you expect retrievals of the whole list only etc.). There are solutions already implemented available in the web. For example here is a nice one done by Eric Marchesin in his article Automatic sorted list. This sample code is not generic as originally it was created in 2003, however adding generics there should not be a big challenge.

    Just for demonstration purposes here is a simplified version of the list that will do what is required in the question. We assume that number of inserts is not considerably higher comparing to the number of retrievals. To insert the value into the list we'll use binary search. This method is an O(log n) operation, where n is count of items.

    The MySortedList class:

    class MySortedList 
    { 
    private List list; 
    public MySortedList() 
    { 
    list = new List(); 
    } 
    
    public void Add(T item) 
    { 
    int pos = list.BinarySearch(item); 
    list.Insert((pos < 0) ? ~pos : pos, item); 
    } 
    
    public bool Remove(T item) 
    { 
    return list.Remove(item); 
    } 
    
    public T this[int index] 
    { 
    get { return list[index]; } 
    set { list[index] = value; } 
    } 
    
    public int Count 
    { 
    get { return list.Count; } 
    } 
    
    public string ToString() 
    {
    string result = ""; 
    
    foreach (T item in list) 
    { 
    result += ((result != "") ? "|" : "") + item.ToString(); 
    } 
    return result; 
    } 
    }
    

    Test function can be:

    static void Main(string[] args) 
    { 
    MySortedList sl = new MySortedList(); 
    
    sl.Add("My"); 
    sl.Add("My"); 
    sl.Add("Sorted"); 
    sl.Add("List"); 
    Console.WriteLine(sl.ToString()); 
    sl.Remove("My"); 
    Console.WriteLine(sl.ToString()); 
    Console.WriteLine(sl.Count); 
    Console.WriteLine(sl[sl.Count-1]); 
    Console.ReadLine(); 
    }
    

    The output will be:

    List|My|My|Sorted
    List|My|Sorted
    3
    Sorted

    Replied on Mar 29 2011 9:08PM  . 
    Dmitry Kharlap (aka Docker)
    153 · 1% · 325

Your Answer


Sign Up or Login to post an answer.
Please note that your answer will not be considered as part of the contest because the competition is over. You can still post an answer to share your knowledge with the community.

Copyright © Rivera Informatic Private Ltd.