Sorting a List while reading from file in c#

Question

I have a text file with deliveries (id,weight,...etc,) and I read them from a Text file and save them in my list. After my list is ready I have to sort it in correct order and only then I can work.

My question: Is there a way to get list sorted while reading the data from the text file, so that each next deliverable that is being read from the file, must be inserted in the list immediately at the right place.

You can see my LoadDeliverablesFromFile method below :

public void LoadDeliverablesFromFile(String filename)
{
    StreamReader sr = null;
    string s;
    try
    {
        sr = new StreamReader(new FileStream(filename, FileMode.Open, FileAccess.Read));
        this.myDeliverables.Clear();
        s = sr.ReadLine();
        while (s != null)
        {

            string[] words = s.Split(' ');
            int id = Convert.ToInt32(words[0]);
            int weight = Convert.ToInt32(words[1]);
            int buyersID = Convert.ToInt32(words[2]);
            Deliverable del = new Deliverable(id, weight, FindPerson(buyersID));
            myDeliverables.Add(del);
            s = sr.ReadLine();

        }

    }
    catch (Exception ex)
    {
        System.Windows.Forms.MessageBox.Show(ex.Message);
    }
    finally
    {
        if (sr != null) sr.Close();
    }

}

myDeliverables.Add(del); will add at end of list. Use InsertAt() to place data in correct location. — jdweng, Jun 12 '16 at 13:34
On which field of your Deliverable class you want your list to be sorted? — Steve, Jun 12 '16 at 13:39
How large is the performance hit of sorting the list at the end? Might be unnecessary optimisation. — James, Jun 12 '16 at 13:42
You're describing Insertion Sort, and there are explanations for the algorithm all over the web. It's far less efficient than doing a single sort at the end. Is there a specific reason you want to sort a bunch of times, rather than just once? — moswald, Jun 12 '16 at 13:55
Yes, insertion sort is O(N^2) on average, while a QuickSort at the end will be O(N.Log(N)) — Matthew Watson, Jun 12 '16 at 14:17
@MatthewWatson can you provide me with example please. I just want to practice. Should i implement one of the IComparable interfaces ? — Alex, Jun 12 '16 at 18:11
Try google "insertion sort c#" - there should be a few examples. — Matthew Watson, Jun 12 '16 at 21:10

score 0 · Answer 1 · edited May 23 '17 at 10:33

I'm guessing myDeliverables is of type List<Deliverable>

There is no List in .NET that allows inserting an element and get it sorted at the moment of the insertion, and for a good reason

First of all, consider if you really need to sort on insertion. If the list of elements you are reading is not too large or you do not populate the list from elements in the file frequently, the performance hit of sorting everything at the end shouldn't be a problem.

If you have measured the performance hit and it is significant, then inserting elements at place in an array won't be the best choice. list elements must be contiguous in memory so that means that after each sorted insertion all the elements after the index where you are inserted will be moved in in memory. (and depending on the size of the list, maybe a new memory allocation + copy of all elements is needed) That's why a list does not provide a method to sort on insertion

So, the point is: if you are in this situation, then a List is not the right data structure to use. I suggest using the SortedList data structure, but contrary to what it's name might suggest, it is not actually a List, but a map, )i.e. it requires a pair of key/value elements) and you'll get your sort on insertion.

Elements in a SortedList are ordered by key, so the field of the Deliverable class you want to use to sort, must implement the IComparable interface if it is a custom Type.

score 0 · Answer 2 · answered Jun 12 '16 at 13:43

You could use a for loop to iterate through the list to compare each current element of the list to the item you are planning to add. If the current item in the list is less then the item you are adding i++, else that index is your selected index. Then proceed to add the item in the list by using myDeliverables.Insert(i, new Deliverable(id, weight, FindPerson(buyersID)).

score 0 · Answer 3 · answered Jun 12 '16 at 14:31

0

You could try to add new Deliverable item to List and then to sort that List, but I recommend you to use SortedList

answered Jun 12 '16 at 14:31

Ghost

33
4

score 0 · Answer 4 · answered Jun 13 '16 at 16:35

I don't think you can do it with just a for loop - because this has to use two loops for and while - insertion algorithm check it in internet, there is plenty of information on it. If you use the insertion algorithm (that is at least what i used for it), note that you first add the this.myDeliverables.Add(new Deliverable(id, weight, per)); otherwise it will skip the last item, which is the 15th i think, the second assignment indeed is a bit confusing when you don't understand sorting algorithms.

Sorting a List while reading from file in c#

4 Answers4