' Copyright (c) 2010 the authors listed at the following URL, and/or
' the authors of referenced articles or incorporated external code:
' http://en.literateprograms.org/Quicksort_(Visual_Basic_.NET)?action=history&offset=20070726234304
' 
' Permission is hereby granted, free of charge, to any person obtaining
' a copy of this software and associated documentation files (the
' "Software"), to deal in the Software without restriction, including
' without limitation the rights to use, copy, modify, merge, publish,
' distribute, sublicense, and/or sell copies of the Software, and to
' permit persons to whom the Software is furnished to do so, subject to
' the following conditions:
' 
' The above copyright notice and this permission notice shall be
' included in all copies or substantial portions of the Software.
' 
' THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
' EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
' MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
' IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
' CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
' TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
' SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
' 
' Retrieved from: http://en.literateprograms.org/Quicksort_(Visual_Basic_.NET)?oldid=10766


Module Quicksort
    Sub swap(ByRef v1, ByRef v2)
        Dim tmp
        tmp = v1
        v1 = v2
        v2 = tmp
    End Sub

    Function partition(ByRef a() As Object, ByVal left As Integer, _
    ByVal right As Integer, ByRef pivot As Integer)
        Dim i
        Dim piv
        Dim store

        piv = a(pivot)

        swap(a(right - 1), a(pivot))

        store = left
        For i = left To right - 2
            If a(i) <= piv Then
                swap(a(store), a(i))
                store = store + 1
            End If
        Next
        swap(a(right - 1), a(store))

        Return store
    End Function

    Function getpivot(ByRef a() As Object, ByVal left As Integer, ByVal right As Integer)
        return New System.Random().Next(left, right - 1)
    End Function

    Sub quicksort(ByRef a() As Object, ByVal left As Integer, ByVal right As Integer)
        Dim pivot As Integer
        If right - left > 1 Then
            pivot = getpivot(a, left, right)
            pivot = partition(a, left, right, pivot)
            quicksort(a, left, pivot)
            quicksort(a, pivot + 1, right)
        End If
    End Sub

    Sub qsort(ByRef a() As Object)
        Dim i
        Dim ii
        For i=0 to a.Length()-1
            ii=New System.Random().Next(0, a.Length()-1)
            If i<>ii Then
                swap(a(i), a(ii))
            End If
        Next

        quicksort(a, 0, a.Length())
    End Sub

    Sub print(ByRef a() As Object)
        Dim i
        For i = 0 To a.Length() - 1
            System.Console.Write("  " & a(i))
        Next
        System.Console.WriteLine()
    End Sub

    Sub main()
        Dim towns() As Object = {"Paris", "London", "Stockholm", "Berlin", "Oslo", "Rome", _
        "Madrid", "Tallinn", "Amsterdam", "Dublin"}

        System.Console.Write("towns before qsort: ")
        print(towns)

        qsort(towns)

        System.Console.Write("towns after qsort: ")
        print(towns)

        Dim numbers() As Object = {5, 7, 5, 2, 8, 4, 6, 2, 3, 5, 1, 8, 5, 7, 3}

        System.Console.Write("numbers before qsort: ")
        print(numbers)

        qsort(numbers)

        System.Console.Write("numbers after qsort: ")
        print(numbers)
    End Sub
End Module