I have an array such as A-B-C-D-E-F-G-H-I-J-K I want to rotate it N places to the right; for example, if N=3, the array should end I-J-K-A-B-C-D-E-F-G-H

Assume that the only available operation is a FLIP method that can invert any portion of the array. For example, applied to the original array FLIP(3,6) would produce A-B-F-E-D-C-G-H-I-J-K.

I wrote this Visual Basic console application to compare Juggler's 3-Flip algorithm to my Bubble Sort Algorithm. For "small" (1,000 element) arrays, there was no performance difference between them. But the superiority of Juggler's algorithm is dramatic with the larger arrays:

For array size 10,000 and offset 560, Juggler's algorithm took 0 seconds (Windows clock time) and mine took 25 seconds.

For array size 100,000 and offset 560, Juggler was done in 1 second, but it too me 4 minutes, 33 seconds.

For array size 1,000,000 and offset 560, Juggler was done in an impressive 5 seconds, but I was still plodding away 11 minutes later.   

Here is the program: 

Imports System
Imports System.Runtime.InteropServices
Imports System.Math
Module Module1
    Sub Main()
        Randomize()
        Dim strExecute As String
        strExecute = "Y"
        While strExecute = "Y"
            Mainline()
            Console.WriteLine("  ")
            Console.WriteLine("Do you want to run again ? (Y/N)")
            strExecute = UCase(Console.ReadLine())
        End While
    End Sub
    Sub Mainline()
        Dim strFastSlowSw As String
        Dim dblArray() As Double
        Dim dblArraySize As Double
        Dim intWorkarea As Integer
        Dim dblRealSize As Double
        Dim dblArrayOffset As Double
        Dim strArrayNumber As String
        Dim strArrayDigit As String
        Dim dblArrayDigit As Double
        Dim dblHalfSize As Double
        Dim dblHalfOffset As Double
        Dim dblDigitPlace As Double
        Dim strCurrTime As String
        dblArraySize = 0
        While (dblArraySize < 10 _
        Or dblArraySize > 99000000)
            Console.WriteLine("  ")
            Console.WriteLine("Please enter an array size between 10 and " & _
            "99000000")
            dblArraySize = Int(Console.ReadLine())
        End While
        dblArrayOffset = 0
        While (dblArrayOffset = 0 _
        Or dblArrayOffset >= dblArraySize)
            Console.WriteLine("  ")
            Console.WriteLine("Please enter an array offset less than " & _
            Str(dblArraySize))
            dblArrayOffset = Int(Console.ReadLine())
        End While
        Console.WriteLine("  ")
        Console.WriteLine("Please wait while I populate the array " & _
        "with values 1,2,3,...," & Str(dblArraySize))
        ReDim dblArray(dblArraySize)
        dblRealSize = dblArraySize - 1
        For Index1 As Integer = 0 To dblRealSize
            dblArray(Index1) = Index1
            dblArray(Index1) += 1
        Next
        Console.WriteLine("  ")
        Console.WriteLine("The initial array begins with:")
        DisplayArray(dblArray)
        strFastSlowSw = "?"
        While strFastSlowSw <> "B" And strFastSlowSw <> "F"
            Console.WriteLine("  ")
            Console.WriteLine("Do you want the Bubble Sort " & _
            " algorithm, or the three Flip " & _
            "algorithm? (B/F)")
            strFastSlowSw = UCase(Console.ReadLine())
        End While
        Console.WriteLine("  ")
        strCurrTime = TimeOfDay
        If strFastSlowSw = "B" Then
            Console.WriteLine("Starting the Bubble Sort " & _
                   "Algorithm at " & strCurrTime)
            SlowAlgorithm(dblArray, dblArraySize, dblArrayOffset)
        Else
            Console.WriteLine("Starting the three Flip " & _
                   "Algorithm at " & strCurrTime)
            FastAlgorithm(dblArray, dblArraySize, dblArrayOffset)
        End If
        Console.WriteLine("  ")
        strCurrTime = TimeOfDay
        Console.WriteLine("Algorithm completed at " & strCurrTime)
        Console.WriteLine("  ")
        Console.WriteLine("The final array begins with:")
        DisplayArray(dblArray)
    End Sub
    Sub FastAlgorithm(ByRef dblArray, ByRef dblArraySize, ByRef dblArrayOffset)
        Dim dblHoldElement1 As Double
        Dim dblReverseIndex1 As Double
        Dim dblMaxIndex1 As Double
        Dim intWorkarea1 As Integer
        Dim dblRealSize1 As Double
        Dim dblStartIndex1 As Double
        Dim dblStartIndex As Double
        Dim dblEndIndex As Double
        Dim dblFlipSize As Double
        Dim dblFlipDecr As Double
        ' FLIP(1,M)
        dblStartIndex = 0
        dblEndIndex = (dblArraySize - dblStartIndex - 1) / 2
        dblEndIndex = Int((dblEndIndex * 100) / 100)
        dblFlipSize = dblArraySize - 1
        dblFlipDecr = 0
        FlipIt(dblArray, dblStartIndex, dblEndIndex, dblFlipSize, dblFlipDecr)
        ' FLIP(1,N)
        dblStartIndex = 0
        dblEndIndex = (dblArrayOffset - dblStartIndex - 1) / 2
        dblEndIndex = Int((dblEndIndex * 100) / 100)
        dblFlipSize = dblArrayOffset - 1
        FlipIt(dblArray, dblStartIndex, dblEndIndex, dblFlipSize, dblFlipDecr)
        ' FLIP(N+1,M)
        dblStartIndex = dblArrayOffset
        dblEndIndex = (dblArraySize - dblStartIndex) / 2
        dblEndIndex = Int((dblEndIndex * 100) / 100)
        dblEndIndex += dblStartIndex
        dblFlipSize = dblArraySize - 1
        dblFlipDecr = dblStartIndex
        FlipIt(dblArray, dblStartIndex, dblEndIndex, dblFlipSize, dblFlipDecr)
    End Sub
    Sub SlowAlgorithm(ByRef dblArray, ByRef dblArraySize, ByRef dblArrayOffset)
        Dim dblRightIndex As Double
        Dim dblStartBubble As Double
        Dim dblEndBubble As Double
        Dim dblIndexWork1 As Double
        Dim dblIndexWork2 As Double
        Dim dblLoopLimit As Double
        dblStartBubble = dblArraySize - dblArrayOffset
        dblEndBubble = dblArraySize - 1
        dblLoopLimit = dblStartBubble
        For Index75 As Double = dblStartBubble To dblEndBubble
            dblRightIndex = Index75
            For Index65 As Double = 1 To dblLoopLimit
                SwitchTwo(dblArray, dblRightIndex)
                dblRightIndex -= 1
            Next
        Next
    End Sub
    Sub DisplayArray(ByRef dblArray)
        Console.WriteLine(Str(dblArray(0)) & " " & Str(dblArray(1)) & _
        " " & Str(dblArray(2)) & " " & Str(dblArray(3)) & " " & Str(dblArray(4)) _
        & " " & Str(dblArray(5)) & " " & Str(dblArray(6)) _
        & " " & Str(dblArray(7)) & " " & Str(dblArray(8)) & " " & Str(dblArray(9)))
    End Sub
    Sub FlipIt(ByRef dblArray, ByRef dblStartIndex, ByRef dblEndIndex, _
    ByRef dblFlipSize, ByRef dblFlipDecr)
        Dim dblFlipHold As Double
        Dim dblFlipIndex As Double
        For Indexf As Double = dblStartIndex To dblEndIndex
            dblFlipIndex = dblFlipSize - Indexf + dblFlipDecr
            dblFlipHold = dblArray(Indexf)
            dblArray(Indexf) = dblArray(dblFlipIndex)
            dblArray(dblFlipIndex) = dblFlipHold
        Next Indexf
    End Sub
    Sub SwitchTwo(ByRef dblArray, ByRef dblRightIndex)
        Dim dblLeftIndex As Double
        Dim dblSwitchHold As Double
        dblLeftIndex = dblRightIndex - 1
        dblSwitchHold = dblArray(dblRightIndex)
        dblArray(dblRightIndex) = dblArray(dblLeftIndex)
        dblArray(dblLeftIndex) = dblSwitchHold
    End Sub
End Module

Posted by Penny on 2004-04-20 13:04:39