Sorting a list of objects

[b5177241]

HI. Suppose I have:

Public Class myClass1
    Dim foo As String
    Dim bar As String
    Dim fum As Integer
    Public Sub New(ByVal foo As String, ByVal bar As String, ByVal fum As Integer)
        Me.foo = foo
        Me.bar = bar
        Me.fum = fum
    End Sub

End Class
.
.
.
    Sub main3()
        Dim myList As List(Of myClass1)
        myList.Add(New myClass1("a0", "b0", 0))
        myList.Add(New myClass1("a2", "b2", 2))
        myList.Add(New myClass1("a1", "b1", 1))
        myList.Add(New myClass1("a3", "b3", 4))

        ' Sort the list by the foo property
    End Sub

How would I go about sorting the list by its first property, foo using library methods?

[Shaggy Hiker]

Take a look in MSDN on the List.Sort method. You will see that there are a number of overloads for this method. One of them will work....but more on that in a minute.

If you are only EVER going to sort on that first property, then you should have the class implement the IComparer interface. It's pretty easy to do, but easy to forget, as well. Therefore, whenever I want to do that, I generally just go to MSDN and copy the sample that is found there and change it to suit. Once you have that interface implemented, the standard .Sort() method will sorth them correctly.

However, where I started out going was for those cases where this time you want to sort on one property, but next time you will want to sort on some other property. In those cases, just implementing IComparer won't suffice. In those cases, you will have to create a custom comparison routine and supply it as an argument to the .Sort method, and that's what all those overloads are all about.

[Niya]

Here is an example of an implementation of the IComparable<T> interface used for sorting by generic list objects. It compares by age:-

Private Class Data
        Implements IComparable(Of Data)
 
        Private _name As String
        Private _age As Integer
 
        Sub New(ByVal name As String, ByVal age As Integer)
            _name = name
            _age = age
        End Sub
 
        Public Function CompareTo(ByVal other As Data) As Integer Implements System.IComparable(Of Data).CompareTo
            If Me._age < other._age Then Return -1 'When me is less than other
            If Me._age = other._age Then Return 0 'Equal
            If Me._age > other._age Then Return 1 'When me is greater than other
 
        End Function
End Class

Implement that interface on your class and you can sort like:-

Dim lst As New List(Of Data)
 
        lst.Add(New Data("John", 2))
        lst.Add(New Data("Mary", 12))
        lst.Add(New Data("Mac", 12))
        lst.Add(New Data("Amber", 4))
        lst.Add(New Data("Joe", 77))
 
        lst.Sort()  '<---- Will sort according to Age because thats how IComparable<T> was implemented

[Joacim Andersson]

Since your class doesn't have any public properties the only way to go is to implement an IComparable interface.

Public Class myClass1
  Implements IComparable(Of myClass1)

  Private foo As String
  Private bar As String
  Private fum As Integer
  Public Sub New(ByVal foo As String, ByVal bar As String, ByVal fum As Integer)
    Me.foo = foo
    Me.bar = bar
    Me.fum = fum
  End Sub

  Public Function CompareTo(other As myClass1) As Integer Implements System.IComparable(Of myClass1).CompareTo
    Return String.Compare(Me.foo, other.foo)
  End Function
End Class

In this case I implemented the IComparable(Of T) interface and used your class as the type for T. The interface states that you must implement the CompareTo() method. Since you're only comparing strings I simply used the String.Compare() method and returned the value of that.

[b5177241]

Take a look in MSDN on the List.Sort method. You will see that there are a number of overloads for this method. One of them will work....but more on that in a minute.

If you are only EVER going to sort on that first property, then you should have the class implement the IComparer interface. It's pretty easy to do, but easy to forget, as well. Therefore, whenever I want to do that, I generally just go to MSDN and copy the sample that is found there and change it to suit. Once you have that interface implemented, the standard .Sort() method will sorth them correctly. .

OK -- Working on that. However my test program is failing on the first:

myList.Add(New myClass1("a0", "b0", 0))

It tells me "Object reference not set to an instance of an object."

Am I doing something wrong in my "New" method?

[Niya]

Try initializing foo to zero length in myClass1

EDIT:

Nvm, there is no default constructor so you have to pass it a value.

[Joacim Andersson]

myList.Add(New myClass1("a0", "b0", 0))

It tells me "Object reference not set to an instance of an object."

Am I doing something wrong in my "New" method?

No, it's not in your constructor. The problem is that you never create the object.

Dim myList As New List(Of myClass1)

[Shaggy Hiker]

Whenever you see that error message, look at the objects on the line that is giving you the error. One of them is Nothing, and that is where the problem lies. It's one of the simplest errors to diagnose, though the solution is not always obvious.

There is also an exception to that rule: If the error is showing you <some form>.Show or <some form>.ShowDialog, then the error actually didn't happen on that line (unless the form is Nothing), in which case you would need further work to figure out where the error actually occurred.

[b5177241]

Thanks! FYI, I am not writing forms apps. just CLI apps. I haven't delved into any forms stuff.

[b5177241]

This is great! I can use this immediately.

Today a related question cropped up.

Say I have an 100 x 2 array. Each of the 100 entries in the first dimension consists of a string and an integer. How would I sort the array by the integer values?

[Niya]

Does it have to be a two dimensional array ? Id prefer to use a List<T> or Collection<T> of a class that can hold my Integer and my String values and apply the methods recommended in this thread. The Array.Sort overloads that take an IComparer based object may be able to sort your two dimensional array, I'm not certain though. Jmc or paul may be able to help with that one.

[b5177241]

In this case I'm stuck with the array, since it is a part of a larger project, of which the sorting is just a little bit.

[Joacim Andersson]

This is great! I can use this immediately.

Today a related question cropped up.

Say I have an 100 x 2 array. Each of the 100 entries in the first dimension consists of a string and an integer. How would I sort the array by the integer values?

I don't get it. Is it an array of strings or of integers? Can you give an example of the values?

[b5177241]

eg.

dim a(99,1) as object
a(0,0) = "foo"
a(0,1) = 1
a(1,0) = "bar"
a(1,1) = 2

[Niya]

Something about that doesn't make any sense. Does that array represent rows ? Because if so then its kind of a bad design as you can access every element independently.

[Joacim Andersson]

Array.Sort() can only sort a 1-dimensional arrays so you have to write the logic for this yourself.
Here's a quick example

  Public Sub SortArray(ByRef array(,) As Object)
    Dim list As New List(Of KeyValuePair(Of String, Integer))
    Dim count = array.GetUpperBound(0)
    For i = 0 To count
      list.Add(New KeyValuePair(Of String, Integer)(CStr(array(i, 0)), CInt(array(i, 1))))
    Next
    list.Sort(Function(firstPair, secondPair) firstPair.Value.CompareTo(secondPair.Value))
    For i = 0 To count
      array(i, 0) = list(i).Key
      array(i, 1) = list(i).Value
    Next
  End Sub

[.paul.]

eg.

dim a(99,1) as object
a(0,0) = "foo"
a(0,1) = 1
a(1,0) = "bar"
a(1,1) = 2

you could use a bubble sort:

Dim a(9, 1) As Object
a(0, 0) = "c"
a(0, 1) = 3
a(1, 0) = "i"
a(1, 1) = 9
a(2, 0) = "f"
a(2, 1) = 6
a(3, 0) = "a"
a(3, 1) = 1
a(4, 0) = "d"
a(4, 1) = 4
a(5, 0) = "j"
a(5, 1) = 10
a(6, 0) = "g"
a(6, 1) = 7
a(7, 0) = "b"
a(7, 1) = 2
a(8, 0) = "e"
a(8, 1) = 5
a(9, 0) = "h"
a(9, 1) = 8
 
'bubble sort
For outer As Integer = a.GetUpperBound(0) To 0 Step -1
    For inner As Integer = 0 To outer - 1
        If CInt(a(inner, 1)) > CInt(a(inner + 1, 1)) Then
            Dim temp() As Object = {a(inner, 0), a(inner, 1)}
            a(inner, 0) = a(inner + 1, 0)
            a(inner, 1) = a(inner + 1, 1)
            a(inner + 1, 0) = temp(0)
            a(inner + 1, 1) = temp(1)
        End If
    Next
Next

[Shaggy Hiker]

I would suggest that there is never a justification to have an array of that nature. Creating an array of object just so that you can use strings and integers means that you have to cast everything to use it, and there should be plenty of other costly boxing and unboxing along the way. In most cases, a 2D array can be replaced by a 1D array of some class, and this is certainly such a case. Doing that would remove the problems with sorting, as well as making for a more efficient routine. Considering that the class would only have an integer and a string, a structure might also make sense.

[b5177241]

you could use a bubble sort:

I hope your kidding. Bubble sort is one of the worst sort methods and is O(n^2). A randomized quicksort would be much better and not much more work (O(n log n).

OTOH for 100 rows it wouldn't make much difference in practice.

What I am looking for is a way to use library functions. I think I have enough to go on for that.

[b5177241]

I would suggest that there is never a justification to have an array of that nature.

I agree. In my case I "inherited" the array from others in the project. I can try to persuade the team to alter the approach. In the meantime, I just need to find the best way to work with what I'm given.

[MattP]

I concur with Shaggy Hiker on this. A 1D array (or even better collection) of a class/structure makes much more sense.

To facilitate sorting a rectangular array on a specific column I created a couple of extension methods for converting the array from rectangular to jagged and back.

Imports System.Runtime.CompilerServices

Public Module SortHelper

    <System.Runtime.CompilerServices.Extension()> _
    Public Function ToJagged(Of T)(array As T(,)) As T()()
        Dim height As Integer = array.GetLength(0), width As Integer = array.GetLength(1)
        Dim jagged As T()() = New T(height - 1)() {}

        For i As Integer = 0 To height - 1
            Dim row As T() = New T(width - 1) {}
            For j As Integer = 0 To width - 1
                row(j) = array(i, j)
            Next
            jagged(i) = row
        Next
        Return jagged
    End Function

    <System.Runtime.CompilerServices.Extension()> _
    Public Function ToRectangular(Of T)(array As T()()) As T(,)
        Dim height As Integer = array.Length, width As Integer = array(0).Length
        Dim rect As T(,) = New T(height - 1, width - 1) {}
        For i As Integer = 0 To height - 1
            Dim row As T() = array(i)
            For j As Integer = 0 To width - 1
                rect(i, j) = row(j)
            Next
        Next
        Return rect
    End Function

End Module

Here's a small example array and a generic Sort method.

Public Class Form1

    Private Sub Form1_Load(sender As System.Object, e As System.EventArgs) Handles MyBase.Load
        Dim a(9, 1) As Object
        a(0, 0) = "c"
        a(0, 1) = 3
        a(1, 0) = "i"
        a(1, 1) = 9
        a(2, 0) = "f"
        a(2, 1) = 6
        a(3, 0) = "a"
        a(3, 1) = 1
        a(4, 0) = "d"
        a(4, 1) = 4
        a(5, 0) = "j"
        a(5, 1) = 10
        a(6, 0) = "g"
        a(6, 1) = 7
        a(7, 0) = "b"
        a(7, 1) = 2
        a(8, 0) = "e"
        a(8, 1) = 5
        a(9, 0) = "h"
        a(9, 1) = 8

        Dim jagged = a.ToJagged()
        Sort(jagged, 1)
        a = jagged.ToRectangular()
    End Sub

    Private Shared Sub Sort(Of T)(jaggedArray As T()(), col As Integer)
        Dim comp = Comparer(Of T).Default
        Array.Sort(Of T())(jaggedArray, Function(x, y) comp.Compare(x(col), y(col)))
    End Sub

End Class

[Shaggy Hiker]

Such is life, at times.

[.paul.]

OTOH for 100 rows it wouldn't make much difference in practice.

as you said for a small array it would work ok...

[Joacim Andersson]

What I am looking for is a way to use library functions. I think I have enough to go on for that.

As I mentioned in my previous reply there is no library functions to sort a multiple dimensional array. The closest you can come is to use code similar to what I showed or just use a regular bubble- or quick sort routine (bubble sort will most likely be quicker when you only have 100 items).