sortingAlgoVisualizer/sortingAlgo.py at master · normanvuong/sortingAlgoVisualizer · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
import time
#Merge Sort
def mergeSort(subjectList, firstPos, lastPos, visualizeData, timeTick) :
    if firstPos < lastPos - 1 :
        workspace = [None] * (lastPos - firstPos)
        mergeSortAux(subjectList, firstPos, lastPos, workspace, 0, visualizeData, timeTick)

#Aux function to divide the list into two part then start merging after done
def mergeSortAux(subjectList, firstPos, lastPos, workspace, workspaceFirstPos, visualizeData, timeTick) :
    if firstPos < lastPos - 1 :
        middlePos = (firstPos + lastPos) // 2

        visualizeData(subjectList, ['yellow' if x >= firstPos and x <= middlePos else 'blue' if x > middlePos and x < lastPos else 'red' for x in range(len(subjectList))])
        time.sleep(timeTick)
        mergeSortAux(subjectList, firstPos, middlePos, workspace, workspaceFirstPos, visualizeData, timeTick)
        mergeSortAux(subjectList, middlePos, lastPos, workspace, workspaceFirstPos + (middlePos - firstPos), visualizeData, timeTick)

        visualizeData(subjectList, ['yellow' if x >= firstPos and x <= middlePos else 'blue' if x > middlePos and x < lastPos else 'red' for x in range(len(subjectList))])
        time.sleep(timeTick)
        merge(subjectList, firstPos, middlePos, subjectList, middlePos, lastPos, workspace, workspaceFirstPos, visualizeData, timeTick)

        for pos in range(firstPos, lastPos) :
            subjectList[pos] = workspace[workspaceFirstPos + (pos - firstPos)]
        visualizeData(subjectList, ['green' if x >= firstPos and x < lastPos else 'red' for x in range(len(subjectList))])
        time.sleep(timeTick)

#merging function that put them into an order list
def merge(subjectListA, firstPosA, lastPosA, subjectListB, firstPosB, lastPosB, resultList, resultListFirstPos, visualizeData, timeTick) :
    if firstPosA < lastPosA and firstPosB < lastPosB :
        if subjectListA[firstPosA][1] < subjectListB[firstPosB][1] :
            resultList[resultListFirstPos] = subjectListA[firstPosA]
            merge(subjectListA, firstPosA + 1, lastPosA, subjectListB, firstPosB, lastPosB, resultList, resultListFirstPos + 1, visualizeData, timeTick)
        else :
            resultList[resultListFirstPos] = subjectListB[firstPosB]
            merge(subjectListA, firstPosA, lastPosA, subjectListB, firstPosB + 1, lastPosB, resultList, resultListFirstPos + 1, visualizeData, timeTick)
    elif firstPosA < lastPosA :
        resultList[resultListFirstPos] = subjectListA[firstPosA]
        merge(subjectListA, firstPosA + 1, lastPosA, subjectListB, firstPosB, lastPosB, resultList, resultListFirstPos + 1, visualizeData, timeTick)
    elif firstPosB < lastPosB :
        resultList[resultListFirstPos] = subjectListB[firstPosB]
        merge(subjectListA, firstPosA, lastPosA, subjectListB, firstPosB + 1, lastPosB, resultList, resultListFirstPos + 1, visualizeData, timeTick)
    return resultList


#Insertion Sort
#def insertionSort(subjectList, firstPos, lastPos) :
    #if firstPos < lastPos :
        #insertionSort(subjectList, firstPos, lastPos - 1)
        #insertion(subjectList, firstPos, lastPos, subjectList[lastPos - 1])

#def insertion(subjectList, firstPos, lastPos, newValue) :
    #if firstPos > lastPos - 1 :
        #subjectList[firstPos] = newValue
    #elif subjectList[lastPos - 2][1] <= newValue[1] :
        #print(lastPos)
        #print(subjectList[lastPos - 2][1])
        #subjectList[lastPos - 1] = newValue
    #else :
        #subjectList[lastPos - 1] = subjectList[lastPos - 2]
        #insertion(subjectList, firstPos, lastPos - 1, newValue)

def insertionSort(subjectList, firstPos, lastPos, visualizeData, timeTick) :
    for index in range(firstPos, lastPos) :
        if index == 0 :
            pass
        else :
            newValue = subjectList[index]
            second_index = index - 1
            while second_index >=0 and subjectList[second_index][1] > newValue[1] :
                visualizeData(subjectList, ['yellow' if x == second_index or x == second_index + 1 else 'blue' if x == index else 'red' for x in range(len(subjectList))])
                subjectList[second_index + 1] = subjectList[second_index]
                time.sleep(timeTick)
                second_index -= 1
            subjectList[second_index+1] = newValue
            visualizeData(subjectList, ['green' if x == second_index + 1 or x == index else 'red' for x in range(len(subjectList))])
            time.sleep(timeTick)
    visualizeData(subjectList, ['green' for x in range(len(subjectList))])


#heap sort
def heapSort(subjectList, visualizeData, timeTick) :
    workList = []
    for index in range(0, len(subjectList)) :
        heapInsert(subjectList, workList, subjectList[index], visualizeData, timeTick)
        visualizeList = workList[0:index+1] + subjectList[index+1:]
        visualizeData(visualizeList, ['green' if x >= 0 and x <=index else 'red' for x in range(len(visualizeList))])
        time.sleep(timeTick)
    #resultList = []
    #while len(workList) != 0 :
        #resultList.append(heapRemove(workList, visualizeData, timeTick))
    for index in range(0, len(subjectList)) :
        subjectList[index] = heapRemove(workList, visualizeData, timeTick) #resultList[index]
    visualizeData(subjectList, ['green' for x in range(len(subjectList))])

def heapInsert(originalList, subjectList, newValue, visualizeData, timeTick) :
    subjectList.append(newValue)
    if len(subjectList) == 0 :
        pass
    else :
        heapSwap(originalList, subjectList, len(subjectList) - 1, visualizeData, timeTick)

def heapSwap(originalList, subjectList, posToCheck, visualizeData, timeTick) :
    #if posToCheck <= 0 :
        #pass
    if posToCheck > 0 :
        parentPos = (posToCheck - 1) // 2
        if subjectList[posToCheck][1] < subjectList[parentPos][1] :
            #visualizeList = subjectList[0:posToCheck+1] + originalList[posToCheck+1:]
            #visualizeData(visualizeList, ['yellow' if x == parentPos and x == posToCheck else 'red' for x in range(len(visualizeList))])
            #time.sleep(timeTick)
            subjectList[parentPos], subjectList[posToCheck] = subjectList[posToCheck], subjectList[parentPos]
            #visualizeList = subjectList[0:posToCheck+1] + originalList[posToCheck+1:]
            #visualizeData(visualizeList, ['green' if x == parentPos and x == posToCheck else 'red' for x in range(len(visualizeList))])
            #time.sleep(timeTick)
        heapSwap(originalList, subjectList, parentPos, visualizeData, timeTick)

def heapRemove(subjectList, visualizeData, timeTick) :
    if len(subjectList) == 1 :
        return subjectList.pop()
    else :
        subjectList[0], subjectList[len(subjectList) - 1] = subjectList[len(subjectList) - 1], subjectList[0]
        valueToSave = subjectList.pop()
        heapResort(subjectList, 0, visualizeData, timeTick)
        return valueToSave

def heapResort(subjectList, posToCheck, visualizeData, timeTick) :
    leftChildPos = posToCheck * 2 + 1
    rightChildPos = posToCheck * 2 + 2
    if rightChildPos <= len(subjectList) - 1 :
        if subjectList[leftChildPos][1] < subjectList[rightChildPos][1] :
            if subjectList[posToCheck][1] > subjectList[leftChildPos][1] :
                subjectList[posToCheck], subjectList[leftChildPos] = subjectList[leftChildPos], subjectList[posToCheck]
                heapResort(subjectList, leftChildPos, visualizeData, timeTick)
        else :
            if subjectList[posToCheck][1] > subjectList[rightChildPos][1] :
                subjectList[posToCheck], subjectList[rightChildPos] = subjectList[rightChildPos], subjectList[posToCheck]
                heapResort(subjectList, rightChildPos, visualizeData, timeTick)
    elif leftChildPos <= len(subjectList) - 1 :
        if subjectList[posToCheck][1] > subjectList[leftChildPos][1] :
            subjectList[posToCheck], subjectList[leftChildPos] = subjectList[leftChildPos], subjectList[posToCheck]
    #else :
        #pass

def bubbleSort(subjectList, visualizeData, timeTick) :
    for index in range(0, len(subjectList)) :
        for second_index in range(index+1, len(subjectList)) :
            if subjectList[index][1] > subjectList[second_index][1] :
                subjectList[index], subjectList[second_index] = subjectList[second_index], subjectList[index]
                visualizeData(subjectList, ['green' if x == index or x == second_index else 'red' for x in range(len(subjectList))])
                time.sleep(timeTick)
        visualizeData(subjectList, ['green' for x in range(len(subjectList))])

def selectionSort(subjectList, visualizeData, timeTick) :
    for index in range(0, len(subjectList)) :
        minValueIndex = index
        for second_index in range(index + 1, len(subjectList)) :
            if subjectList[second_index][1] < subjectList[minValueIndex][1] :
                visualizeData(subjectList, ['yellow' if x == second_index or x == minValueIndex else 'red' for x in range(len(subjectList))])
                time.sleep(timeTick)
                minValueIndex = second_index
        subjectList[index], subjectList[minValueIndex] = subjectList[minValueIndex], subjectList[index]
        visualizeData(subjectList, ['green' if x == index or x == minValueIndex else 'red' for x in range(len(subjectList))])
        time.sleep(timeTick)
    visualizeData(subjectList, ['green' for x in range(len(subjectList))])

#QuickSort
def quickSort(subjectList, firstPos, lastPos, visualizeData, timeTick) :
    if firstPos < lastPos - 1 :
        splitPoint = partition(subjectList, firstPos, lastPos - 1, subjectList[lastPos - 1], visualizeData, timeTick)
        exchange(subjectList, splitPoint, lastPos - 1)
        visualizeData(subjectList, ['green' if x == splitPoint or x == lastPos - 1 else 'grey' for x in range(len(subjectList))])
        time.sleep(timeTick)
        quickSort(subjectList, firstPos, splitPoint, visualizeData, timeTick)
        quickSort(subjectList, splitPoint + 1, lastPos, visualizeData, timeTick)

def partition(subjectList, firstPos, lastPos, splitValue, visualizeData, timeTick) :
    visualizeData(subjectList, ['red' if x == subjectList[firstPos] else 'blue' if x == splitValue else 'yellow' if x == subjectList[lastPos] else 'grey' for x in subjectList])
    time.sleep(timeTick)
    if firstPos >= lastPos :
        return firstPos
    elif subjectList[firstPos][1] < splitValue[1] :
        return partition(subjectList, firstPos + 1, lastPos, splitValue, visualizeData, timeTick)
    elif subjectList[lastPos-1][1] > splitValue[1] :
        return partition(subjectList, firstPos, lastPos - 1, splitValue, visualizeData, timeTick)
    else :
        exchange(subjectList, firstPos, lastPos - 1)
        visualizeData(subjectList, ['green' if x == subjectList[firstPos] or x == subjectList[lastPos] else 'blue' if x == splitValue else 'grey' for x in subjectList])
        time.sleep(timeTick)
        return partition(subjectList, firstPos + 1, lastPos - 1, splitValue, visualizeData, timeTick)

def exchange(subjectList, firstPosToChange, secondPosToChange) :
    subjectList[firstPosToChange], subjectList[secondPosToChange] = subjectList[secondPosToChange], subjectList[firstPosToChange]
#L = [ ]

#L = [['Witcher 3', 150], ['Megaman', 100], ['Zero', 80], ['X', 50], ['Gogeta', 0], ['Bass', 50], ['Vegito', 1]]
#try :
    #while True :
        #name = input("Please enter the name: ")
        #number = int(input("Please enter the number: "))
        #L.append([name, number])
#except :
    #pass

#print(L)
#quickSort(L, 0, len(L))
#selectionSort(L)
#bubbleSort(L)
#heapSort(L)
#insertionSort(L, 0, len(L))
#mergeSort(L, 0, len(L))
#print(L)