How to order array in lexicographical order vb.net

问题:

This is kinda complicated for me to understand

    Dim test() As Byte = New Byte() {50, 40, 30, 10, 10}
    Dim answer() As UInteger = SortLexicoGraphicallyBigIntegerArray(test)

The answer is the each Rotation sorted from lowest array value to highest array value.

Rotation 0 = 50, 40, 30, 10, 10
Rotation 1 = 10, 50, 40, 30, 10
Rotation 2 = 10, 10, 50, 40, 30
Rotation 3 = 30, 10, 10, 50, 40
Rotation 4 = 40, 30, 10, 10, 50

When I sort this array above by hand I should get

Rotation 2 = 10, 10, 50, 40, 30
Rotation 1 = 10, 50, 40, 30, 10
Rotation 3 = 30, 10, 10, 50, 40
Rotation 4 = 40, 30, 10, 10, 50
Rotation 0 = 50, 40, 30, 10, 10

So the answer should be 2, 1, 3, 4, 0

I get stuck in a infinite loop and I can't put my finger on it

Here is my Code

Public Function GetRotation(Data As Byte(), rotation As UInteger) As Byte()
   'Rotation Left
    Dim rotationData As New List(Of Byte)

    Dim start As UInteger = Data.Length - rotation Mod Data.Length

    For i = 0 To Data.Length - 1
        rotationData.Add(Data((start + i) Mod (Data.Length)))
    Next

    Return rotationData.ToArray()
End Function

Public Function SortLexicoGraphicallyBigIntegerArray(data As Byte()) As UInteger()
    Dim OrderedRotations As New List(Of UInteger)
    Dim index As Integer = 0
    Dim rowSwapped As Boolean
    Dim data1 As Byte()
    Dim data2 As Byte()

    For rotation As Short = 0 To data.Length - 1
        OrderedRotations.Add(rotation)
    Next

    For rotation As Long = data.Length - 1 To 0 Step -1
        Do
            rowSwapped = False
            data1 = GetRotation(data, OrderedRotations(rotation))
            data2 = GetRotation(data, OrderedRotations((rotation + 1) Mod (data.Length)))
            Do
                If data1(index) > data2(index) Then
                    'Swaps a full row in a few copies.
                    Dim tmpFirst As UInteger = OrderedRotations(index)
                    OrderedRotations(index) = OrderedRotations(index + 1)
                    OrderedRotations(index + 1) = tmpFirst

                    data1 = GetRotation(data, OrderedRotations(rotation))
                    data2 = GetRotation(data, OrderedRotations((rotation + 1) Mod (data.Length)))
                    rowSwapped = True
                End If
                index += 1
            Loop While index < data.Length - 1
            index = 0

        Loop While rowSwapped <> False
    Next
    Return OrderedRotations.ToArray()
End Function

Here is a new attempt I tried I still can't make it work

    Public Function SortLexicoGraphicallyBigIntegerArray(ByRef data As Byte()) As UInteger()
        Dim OrderedRotations As New List(Of UInteger)
        Dim index As Integer = 0
        Dim data1 As Byte()
        Dim data2 As Byte()

        Dim rotation As UInteger = 0
        Dim eachRotation As Integer = 0
        Dim TryAgain As Boolean = False

        For rotation = 0 To data.Length - 1
            data1 = GetRotation(data, rotation)
            OrderedRotations.Add(rotation)
            If OrderedRotations.Count > 1 Then
redo:
                data1 = GetRotation(data, OrderedRotations(rotation))
                For eachRotation = OrderedRotations.Count - 1 To 0 Step -1
                    If OrderedRotations(eachRotation) = OrderedRotations(rotation) Then Continue For
                    data2 = GetRotation(data, OrderedRotations(eachRotation))

                    For index = 0 To data.Length - 1
                        If data1(index) = data2(index) Then
                            Continue For
                        ElseIf data1(index) < data2(index) Then
                            Exit For
                        ElseIf data1(index) > data2(index) Then
                            Dim tmpFirst As UInteger = OrderedRotations(rotation)
                            OrderedRotations(rotation) = OrderedRotations(eachRotation)
                            OrderedRotations(eachRotation) = tmpFirst
                            GoTo redo
                            Exit For
                        End If
                    Next
                Next
            End If
        Next

        Return OrderedRotations.ToArray()
    End Function

Something to do with multi-layer comparisons which I can't grasp.

回答1:

You can do a general binary sort algorithm:-

Dim flag As Boolean
Dim tempvalue As dataarraytype
Dim i As Integer

Do
    flag = False
    For i = 0 to dataarray.length - 2
        If dataarray(i) > dataarray(i+1) Then   'Do the test you require
            'Swap values
            tempvalue = dataarray(i)
            dataarray(i) = dataarray(i+1)
            dataarray(i+1) = tempvalue
            flag = True
        End If
    Next
Loop While flag

Solved using FateOfLeap's answer here is the full working code

Public Function SortLexicoGraphicallyBigIntegerArray(ByRef data As Byte()) As UInteger()
    Dim OrderedRotations As New List(Of UInteger)
    Dim index As Integer = 0
    Dim data1 As Byte()
    Dim data2 As Byte()

    Dim rotation As UInteger = 0
    Dim eachRotation As Integer = 0
    Dim TryAgain As Boolean = False

    For rotation = 0 To data.Length - 1
        data1 = GetRotation(data, rotation)
        OrderedRotations.Add(rotation)
        If OrderedRotations.Count > 1 Then
            Dim flag As Boolean
            Do
                flag = False

                For eachRotation = OrderedRotations.Count - 1 To 0 Step -1
                    data1 = GetRotation(data, OrderedRotations(rotation))
                    If OrderedRotations(eachRotation) = OrderedRotations(rotation) Then Continue For
                    data2 = GetRotation(data, OrderedRotations(eachRotation))

                    For index = 0 To data.Length - 1
                        If data1(index) > data2(index) Then
                            Exit For
                        ElseIf data1(index) < data2(index) Then
                            Dim tmpFirst As UInteger = OrderedRotations(rotation)
                            OrderedRotations(rotation) = OrderedRotations(eachRotation)
                            OrderedRotations(eachRotation) = tmpFirst
                            flag = True
                        End If
                    Next
                Next
            Loop While flag
        End If
    Next

    Return OrderedRotations.ToArray()
End Function