##################################################################
# Module:   Rename_Files_S_0_1.pyw
# Author:   MobileDigit
# Date:     2006-07-03
# Version:  0.1
##################################################################
"""
This is a program to test and time different sort algorithms.
"""
##################################################################
# Test Sorts - Version 0.1
# Last revision: 2006-07-03 13/YYYY-MM-DD HH
# 
##################################################################

from Tkinter import *
import random, time


def shuffle(array):
    random.shuffle(array)
#    print array

def bubbleSort(array):
    changed = 1
    n = range(len(array) - 1)
    while changed == 1:
        changed = 0
        for i in n:
            if array[i] > array[i + 1]:
                array[i], array[i + 1] = array[i + 1], array[i]
                changed = 1
#    print array

def newSort(array):
    upper = len(array) - 1
    n = range(upper + 1)
    count = 0
    while count != upper:
        high = upper - count
        for i in n:
           if array[i] >= array[high]:
              array[i], array[high] = array[high], array[i]
        count = count + 1
    if len(array) != 1:
        temp = array[1]
        del array[1]
        array.append(temp)
#        print array

# Add the results to a list and form an average


def run(repeat = 1, size = 200):
    i = 0
    while i < repeat:
        #array = [9, 1, 8, 5, 6, 2, 4]
        array = range(size)

        #start = time.time()
        shuffle(array)
        #end = time.time()
        #shuffle_time = end - start
        #print "Time to shuffle:\t", shuffle_time

        start = time.time()
        newSort(array)
        end = time.time()
        sort_time = end - start
        print "Time to sort:\t\t", sort_time
        i += 1

def repeat():
    print "Enter -1 to quit."
    repeat = int(raw_input("Enter number of times to repeat: "))
    size = int(raw_input("Enter size of array: "))
    while repeat or size != -1:
        run(repeat, size)
        repeat()

repeat()



def oSort():
    pass

def quickSort():
    pass

def count_procedure():
    global distance
    # If not empty
    if entry.get() != "":
        distance = int(entry.get()) - 1
    # In the case it is empty
    else:
        distance = 0
        entry.insert(0, 100)





##self = Tk()
##self.geometry('300x450')
##self.title("Sort tester")
##
##listbox = Listbox(self, background = 'white', height = 30)
##scrollbar = Scrollbar(self, command = listbox.yview, orient = VERTICAL)
##listbox.configure(yscrollcommand = scrollbar.set)
##listbox.grid(row = 1, column = 1, rowspan = 30, sticky = NS)
##scrollbar.grid(row = 1, column = 2, rowspan = 30, sticky = NS)
##
##mix = Label(self, text = 'Time to mix:\t').grid(row = 9, column = 3, columnspan = 4, sticky = W)
##sort = Label(self, text = 'Time to sort:\t').grid(row = 10, column = 3, columnspan = 4, sticky = W)
##show = Label(self, text = 'Time to show:\t').grid(row = 11, column = 3, columnspan = 4, sticky = W)
##entry = Entry(self, bg = 'white', width = 5).grid(row = 5, column = 3, padx = 10, pady = 5)
##sort = Button(self, text = 'Sort').grid(row = 5, column = 4, ipadx = 13, sticky = E)
##done = Button(self, text = 'Done').grid(row = 6, column = 4, ipadx = 10, sticky = E)
##
##frame = Frame(bd = 1, relief = SUNKEN).grid(row = 1, column = 3, columnspan = 4)
##v = IntVar()
##NewSort = Radiobutton(frame, text = "NewSort", variable = v, value = 1).grid(row = 1, column = 3, columnspan = 4, sticky = W)
##BubbleSort = Radiobutton(frame, text = "BubbleSort", variable = v, value = 2).grid(row = 2, column = 3, columnspan = 4, sticky = W)
##OSort = Radiobutton(frame, text = "O-Sort", variable = v, value = 3).grid(row = 3, column = 3, columnspan = 4, sticky = W)
##QuickSort = Radiobutton(frame, text = "QuickSort", variable = v, value = 4).grid(row = 4, column = 3, columnspan = 4, sticky = W)
##
###  1|LSTBOX|^|RADIO BTN|
###  4|      | |  FRAME  |
###  5|      | |ENT||SORT|
###  6|      | |    |QUIT|
###  8|      | |
###  9|      | |MIX LABEL|
### 10|      | |SORTLABEL|
### 11|      | |SHOWLABEL|
### 12|LSTBOX|v|
###      1    2   3    4
##
##
##self.mainloop()


















##def Sort():
##    Length = ent.get()
##    for I in Length:
##        Array(I) = randint(1, 100)
##        item = I & tab & Array(I)
##        listbox.insert(END, item) #Must be indented
##        ent.delete(0, END)
##    listbox.insert(END, 'Original Array')
##
##def OSort():
##    Length = VarArrayHighBound(Array)
##    # O-Sort  (Oosterwal Sort)  Version 2
##    Step = Int(Length / 2 - 1) #Set initial step size
##    while (Step > 0):
##        for I  in range(1, Length) - Step: #Set the range of the lower search cells
##            if intArray(I) > intArray(I + Step): #Compare cells
##                Temp = intArray(I)              # \
##                intArray(I) = intArray(I + Step)# | Swap Cells
##                intArray(I + Step) = Temp       # /
##        Step = Int(Step * 0.86) #Decrement the step size
##    Wend

#
##'2006-05-10
##'Testing different sorts
##
##Option Explicit
##Private intArray() As Integer
##Private strSort As String
##
##Private Sub Form_Load()
##    Randomize
##    optNewSort = True
##    txtHigh.Text = 10
##
##End Sub
##
##Private Sub cmdSort_Click()
##Dim dblTimerStart As Double, dblTimerFinish As Double, intIndex As Integer
##
##    lstDisplay.Clear
##
##    ReDim intArray(1 To txtHigh.Text)
##
##    lstDisplay.AddItem "Original Array"
##
##    dblTimerStart = Timer
##    For intIndex = LBound(intArray) To UBound(intArray)
##        intArray(intIndex) = Int((100 - 1 + 1) * Rnd) + 1
##        lstDisplay.AddItem intIndex & vbTab & intArray(intIndex)
##    Next
##    dblTimerFinish = Timer
##
##    lblTime = "Time to mix: " & Space(4) & Format(dblTimerFinish - dblTimerStart, "Fixed") & " seconds."
##
##    dblTimerStart = Timer
##    If strSort = "BubbleSort" Then
##        Call BubbleSort
##    ElseIf strSort = "NewSort" Then
##        Call NewSort
##    ElseIf strSort = "O-Sort" Then
##        Call OSort
##    ElseIf strSort = "QuickSort" Then
##        Call QuickSort
##    End If
##    dblTimerFinish = Timer
##
##    lblTime = lblTime & vbCrLf & "Time to sort: " & Space(3) & Format(dblTimerFinish - dblTimerStart, "Fixed") & " seconds."
##
##    lstDisplay.AddItem "Sorted Array"
##
##    dblTimerStart = Timer
##    For intIndex = LBound(intArray) To UBound(intArray)
##        lstDisplay.AddItem intIndex & vbTab & intArray(intIndex)
##    Next
##    dblTimerFinish = Timer
##
##    lblTime = lblTime & vbCrLf & "Time to show: " & Space(1) & Format(dblTimerFinish - dblTimerStart, "Fixed") & " seconds."
##
##End Sub
##
##Public Sub NewSort()
##Dim intIndex As Integer, intCounter As Integer, intHigh As Integer, intTemp As Integer
##    
##    Do While intCounter <> UBound(intArray) + UBound(intArray)
##        intHigh = UBound(intArray) - intCounter
##        For intIndex = LBound(intArray) To UBound(intArray)
##           If intArray(intIndex) > intArray(intHigh) Then
##              intTemp = intArray(intHigh)
##               intArray(intHigh) = intArray(intIndex)
##              intArray(intIndex) = intTemp
##           End If
##       Next
##       intCounter = intCounter + 1
##    Loop
##
##End Sub
##
##Public Sub BubbleSort()
##Dim blnSame As Boolean, intIndex As Integer, intTemp As String
##
##    Do While blnSame = False
##        blnSame = True
##       For intIndex = LBound(intArray) To UBound(intArray) - 1
##           If intArray(intIndex) > intArray(intIndex + 1) Then
##           intTemp = intArray(intIndex)
##            intArray(intIndex) = intArray(intIndex + 1)
##            intArray(intIndex + 1) = intTemp
##            blnSame = False
##            End If
##        Next
##    Loop
##End Sub
##
##Public Sub OSort()
##Dim Step As Integer, I, J, Temp As Long, Length As Integer
##
##    Length = UBound(intArray)
##
##    ' O-Sort  (Oosterwal Sort)  Version 2
##
##    Step = Int(Length / 2 - 1)              ' Set initial step size
##    
##    While (Step > 0)
##        
##        For I = 1 To Length - Step           ' Set the range of the lower search cells
##            If intArray(I) > intArray(I + Step) Then    ' Compare cells
##                Temp = intArray(I)              ' \
##                intArray(I) = intArray(I + Step) ' | Swap Cells
##                intArray(I + Step) = Temp       ' /
##            End If
##        Next
##            
##        Step = Int(Step * 0.86)             ' Decrement the step size
##        
##    Wend
##End Sub
##
##Public Sub QuickSort()
##Dim I, J, Temp As Long
##Dim LeftStack(32), RightStack(32), LeftIndex, RightIndex As Long
##Dim StackPointer, IntValue As Long, Length As Integer
##
##    Length = UBound(intArray)
##
##    LeftIndex = 1
##    RightIndex = Length
##        
##    StackPointer = 1
##    LeftStack(StackPointer) = LeftIndex
##    RightStack(StackPointer) = RightIndex
##    
##    Do
##        If RightIndex > LeftIndex Then
##            IntValue = intArray(RightIndex)
##            I = LeftIndex - 1
##            J = RightIndex
##            ' find the pivot item
##            Do
##                Do: I = I + 1: Loop Until intArray(I) >= IntValue
##                Do: J = J - 1: Loop Until J = LeftIndex Or intArray(J) <= IntValue
##                Temp = intArray(I)
##                intArray(I) = intArray(J)
##                intArray(J) = Temp
##            Loop Until J <= I
##            ' swap found items
##            Temp = intArray(J)
##            intArray(J) = intArray(I)
##            intArray(I) = intArray(RightIndex)
##            intArray(RightIndex) = Temp
##            ' push the pairs of pointers that differ most on the stack
##            StackPointer = StackPointer + 1
##            If (I - LeftIndex) > (RightIndex - I) Then
##                LeftStack(StackPointer) = LeftIndex
##                RightStack(StackPointer) = I - 1
##                LeftIndex = I + 1
##            Else
##                LeftStack(StackPointer) = I + 1
##                RightStack(StackPointer) = RightIndex
##                RightIndex = I - 1
##            End If
##        Else
##            'pop a new pair of pointers off the stack
##            LeftIndex = LeftStack(StackPointer)
##            RightIndex = RightStack(StackPointer)
##            StackPointer = StackPointer - 1
##            If StackPointer = 0 Then Exit Do
##        End If
##    Loop
##End Sub
##
##Private Sub optQuickSort_Click()
##strSort = "QuickSort"
##End Sub
##
##Private Sub optOSort_Click()
##strSort = "O-Sort"
##End Sub
##
##Private Sub optBubbleSort_Click()
##strSort = "BubbleSort"
##End Sub
##
##Private Sub optNewSort_Click()
##strSort = "NewSort"
##End Sub
##
##Private Sub cmdDone_Click()
##End
##End Sub

##def bubble(a):
##    n = len(a)
##    changed = 1
##    while changed:
##        changed = 0
##        for i in xrange(n-1):
##            if a[i] > a[i+1]:
##                a[i], a[i+1] = a[i+1], a[i]
##                changed = 1
##        n -= 1
##    print a

##def newSort(array):
##    upper, count, i = len(array) -1, 0, -1
##    while count != upper:
##        high = upper - count
##        for item in array:
##            
##            i = i + 1
##            if array[i] > array[high]:
##                temp = array[i]
##                array[i] = array[high]
##                array[high] = temp
##            count = count + 1
##    print array