I am tasked with writing code to use IComparable with our custom type (Product).
The Product type has a property called OrdinalNumber which is the property being compared for the sort operation. An example of the ordinals can be something like this: 1 2 3 3 5 6 7 7 9 etc. The routine must replace duplicate or missing ordinals and sort the results.
I have found this example and have it working. https://msdn.microsoft.com/en-us/library/w56d4y5z(v=vs.110).aspx
Can someone please help me?
I don't want to sort a DataTable. We currently have code that sorts a DataTable, we want to rewrite that code to use a custom type called Product. The example code I have pasted here uses the new Product class.
Here is what I have so far:
Imports System.Collections.Generic
Public Class Product
Implements IEquatable(Of Product)
Implements IComparable(Of Product)
Public Property ProductName() As String
Get
Return m_ProductName
End Get
Set(value As String)
m_ProductName = value
End Set
End Property
Private m_ProductName As String
Public Property ProductId() As Integer
Get
Return m_ProductId
End Get
Set(value As Integer)
m_ProductId = value
End Set
End Property
Private m_ProductId As Integer
Public Property OrdinalNumber() As Integer
Get
Return m_OrdinalNumber
End Get
Set(value As Integer)
m_OrdinalNumber = value
End Set
End Property
Private m_OrdinalNumber As Integer
Public Overrides Function ToString() As String
Return "Ordinal Number: " & OrdinalNumber & " ID: " & ProductId & " Name: " & ProductName
End Function
Public Overrides Function Equals(obj As Object) As Boolean
If obj Is Nothing Then
Return False
End If
Dim objAsProduct As Product = TryCast(obj, Product)
If objAsProduct Is Nothing Then
Return False
Else
Return Equals(objAsProduct)
End If
End Function
Public Function SortByNameAscending(name1 As String, name2 As String) As Integer
Return name1.CompareTo(name2)
End Function
Public Function CompareTo(compareProduct As Product) As Integer _
Implements IComparable(Of Product).CompareTo
If compareProduct Is Nothing Then
Return 1
Else
Return Me.OrdinalNumber.CompareTo(compareProduct.OrdinalNumber)
End If
End Function
Public Overrides Function GetHashCode() As Integer
Return OrdinalNumber
End Function
Public Overloads Function Equals(other As Product) As Boolean Implements IEquatable(Of Product).Equals
If other Is Nothing Then
Return False
End If
Return (Me.OrdinalNumber.Equals(other.OrdinalNumber))
End Function
End Class
I am not sure why there is such focus on the Bingo variation (now redacted via edit) of a SelectionSort. The Bingo version is slightly faster version of SelectionSort when there are many duplicate values but only marginally so. It is not a sorter specialized for cases when there are some dupes. They are both slow.
How would I implement a selection or "bingo" sort using List.Sort
Thats not how it works. The actual sort mechanism(s) is built into the NET Framework. In the case of List.Sort() it will select one of 3 sorts as it sees fit. You can supply the comparison mechanism.
Given a data set of {1,3,5,5,7,9,15} The elements with 1 and 3 will always sort lower than 5 or 1024, so missing elements are not an issue. How you want the duplicate values to compare, might be.
There are several alternatives:
Dim sortedProds = myProducts.OrderBy(Function (j) j.Ordinal).ToList()
Time: ~6 ms for 20k items
If you want to do something about dupes, such as sort them by the Id:
Dim ProdsL = myProducts.OrderBy(Function(j) j.Ordinal).
ThenBy(Function(k) k.Id).ToList()
Time: ~8 ms for 20k items
Make the class implement IComparable:
Public Function CompareTo(other As ProductItem) As Integer _
Implements IComparable(Of ProductItem).CompareTo
If Ordinal < other.Ordinal Then Return -1
If Ordinal > other.Ordinal Then Return 1
' equal, return the lower ID or:
'Return 0
If Id < other.Id Then Return -1
Return 1
End Function
Usage:
myProducts.Sort(Function(x, y) x.CompareTo(y))
Time: ~28 ms for 20k items
You can also use a method which performs the comparison which means you dont have to implement IComparable unless it has value in other cases.
Private Function ProductComparer(x As ProductItem, y As ProductItem) As Integer
If x.Ordinal < y.Ordinal Then Return -1
If x.Ordinal > y.Ordinal Then Return 1
' equal, return the lower ID or:
'Return 0
If x.Id < y.Id Then Return -1
Return 1
End Function
Usage:
myProducts.Sort(AddressOf ProductComparer)
Time: 11 ms
SelectionSort (~3650 ms) and the Bingo variation (~3590 ms) are so far behind the others, they do not seem worth considering. Bingo is included just to satisfy the original question (even though there is already one in use elsewhere).
Private Sub BingoSort(items As List(Of ProductItem))
' converted from https://en.wikipedia.org/wiki/Selection_sort#Variants
' for http://stackoverflow.com/q/42303395/1070452
Dim max As Int32 = items.Count - 1
Dim nextVal = items(max).Ordinal
Dim value As Int32
Dim tmp As ProductItem
For i As Int32 = max - 1 To 0 Step -1
If items(i).Ordinal > nextVal Then
nextVal = items(i).Ordinal
End If
Next
While (max > 0) And (items(max).Ordinal = nextVal)
max -= 1
End While
While (max > 0)
value = nextVal
nextVal = items(max).Ordinal
For i As Int32 = max - 1 To 0 Step -1
If items(i).Ordinal = value Then
tmp = items(i)
items(i) = items(max)
items(max) = tmp
max -= 1
ElseIf items(i).Ordinal > nextVal Then
nextVal = items(i).Ordinal
End If
Next
While (max > 0) And (items(max).Ordinal = nextVal)
max -= 1
End While
End While
End Sub
Usage:
BingoSort(myProducts)
Time: ~3590 ms for 20k items.
Note that when there are no dupes (or the original list starts in Id order), the result is the same as linq's OrderBy
Dim Valid = ProdsLinq.SequenceEqual(ProdsBingo)
Given the poor performance there doesn't seem to be a reason to use it here. IComparable lets you decide how to tie-break duplicates and both Linq and List.Sort(IComparable) are gobs and gobs faster.
Note that something similar exists for the DataTable:
myDT.DefaultView.Sort = "Ordinal ASC"
' or
myDT.DefaultView.Sort = "Ordinal ASC, Id ASC"