VirtualRobot/HeapSort.py at master · helloworldC2/VirtualRobot · 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
import random
import Jobs

def siftDown(l,start, end,jobs,isReversed):
    root = start
    while root*2+1<=end:
        child = root*2+1
        swap = root
        if not isReversed:
            if l[swap] < l[child]:#swap left child to top
                swap = child
            if child+1 <= end and l[swap] < l[child+1]:
                swap = child + 1#swap right child to top
            if swap == root:
                return#larest element is at the top
            else:
                jobs.append(Jobs.JobGoTo(root))
                jobs.append(Jobs.JobPickUpTreasure(root))
                jobs.append(Jobs.JobStoreTreasure())

                jobs.append(Jobs.JobGoTo(swap))
                jobs.append(Jobs.JobPickUpTreasure(swap))
                jobs.append(Jobs.JobGoTo(root))
                jobs.append(Jobs.JobPlaceTreasure(root))

                jobs.append(Jobs.JobGoTo(swap))
                jobs.append(Jobs.JobSwapHandWithContainer())
                jobs.append(Jobs.JobPlaceTreasure(swap))

                l[root],l[swap] = l[swap],l[root]
                root = swap
        else:
            if l[swap] > l[child]:#swap left child to top
                swap = child
            if child+1 <= end and l[swap] > l[child+1]:
                swap = child + 1#swap right child to top
            if swap == root:
                return#larest element is at the top
            else:
                jobs.append(Jobs.JobGoTo(root))
                jobs.append(Jobs.JobPickUpTreasure(root))
                jobs.append(Jobs.JobStoreTreasure())

                jobs.append(Jobs.JobGoTo(swap))
                jobs.append(Jobs.JobPickUpTreasure(swap))
                jobs.append(Jobs.JobGoTo(root))
                jobs.append(Jobs.JobPlaceTreasure(root))

                jobs.append(Jobs.JobGoTo(swap))
                jobs.append(Jobs.JobSwapHandWithContainer())
                jobs.append(Jobs.JobPlaceTreasure(swap))

                l[root],l[swap] = l[swap],l[root]
                root = swap


def heapify(l,length,jobs,isReversed):

    start = (length-2)//2
    while start >=0:
        siftDown(l,start, length -1,jobs,isReversed)
        start -=1


def heapSort(l,length,isReversed):
    jobs = []
    for i,t in enumerate(l):
        jobs.append(Jobs.JobGoTo(i))
        jobs.append(Jobs.JobPlaceTreasure(i,treasure=t))
    heapify(l,length,jobs,isReversed)
    end = length-1
    while end > 0:
        jobs.append(Jobs.JobGoTo(end))
        jobs.append(Jobs.JobPickUpTreasure(end))
        jobs.append(Jobs.JobStoreTreasure())

        jobs.append(Jobs.JobGoTo(0))
        jobs.append(Jobs.JobPickUpTreasure(0))
        jobs.append(Jobs.JobGoTo(end))
        jobs.append(Jobs.JobPlaceTreasure(end))

        jobs.append(Jobs.JobGoTo(0))
        jobs.append(Jobs.JobSwapHandWithContainer())
        jobs.append(Jobs.JobPlaceTreasure(0))
        l[end],l[0] = l[0],l[end]
        end -=1
        siftDown(l,0,end,jobs,isReversed)
    jobs.append(Jobs.JobIdle())
    return jobs


##li = []
##for i in range(10000):
##    li.append(random.randint(0,100000))
##
##print "Made list, now sorting"
##heapSort(li, len(li))
##print "Done..printing..."
##print li
##print "Sorted"