QuickSortPython/QuickSort.py at master · c0state/QuickSortPython · 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
importrandom
importunittest

defquicksort(array):
defswap(a, b):
temp=array[a]
array[a] =array[b]
array[b] =temp

defpartition(array, begin, end):
# pick pivot elem and move to end
pivotIndex=random.randint(begin, end)
pivotElem=array[pivotIndex]
swap(pivotIndex, end)

swapindex=begin
foriinxrange(begin, end):
ifarray[i] <pivotElem:
swap(swapindex, i)
swapindex+=1

swap(swapindex, end)
returnswapindex

defdoquicksort(array, begin, end):
arraylen=end-begin+1

ifarraylen<2:
return

pivotIndex=partition(array, begin, end)

doquicksort(array, begin, pivotIndex-1)
doquicksort(array, pivotIndex+1, end)

doquicksort(array, 0, len(array)-1)

classQuickSortTestFunctions(unittest.TestCase):

defisSorted(self, array):
iflen(array) <2:
returnTrue

prev_index=0

foriinxrange(1, len(array)):
ifarray[prev_index] >array[i]:
returnFalse
prev_index=i

returnTrue

defsort_and_test(self, array):
quicksort(array)
returnself.isSorted(array)

deftest_sorted_empty(self):
self.assertTrue(self.sort_and_test([]))

deftest_sorted_one(self):
self.assertTrue(self.sort_and_test([1]))

deftest_sorted_two(self):
self.assertTrue(self.sort_and_test([2,1]))
self.assertTrue(self.sort_and_test([1,1]))

deftest_random(self):
foriinxrange(0, 100):
array= [ random.randint(-1000000, 1000000) forjinxrange(0, random.randint(20,100))]
self.assertTrue(self.sort_and_test(array))

if__name__=="__main__":

array= [ random.randint(0, 100) foriinxrange(0, 20) ]

print("Initial array is:", array)
quicksort(array)
print("Quicksorted array is:", array)

unittest.main()
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
importrandom
importunittest

defquicksort(array):
defswap(a, b):
temp=array[a]
array[a] =array[b]
array[b] =temp

defpartition(array, begin, end):
# pick pivot elem and move to end
pivotIndex=random.randint(begin, end)
pivotElem=array[pivotIndex]
swap(pivotIndex, end)

swapindex=begin
foriinxrange(begin, end):
ifarray[i] <pivotElem:
swap(swapindex, i)
swapindex+=1

swap(swapindex, end)
returnswapindex

defdoquicksort(array, begin, end):
arraylen=end-begin+1

ifarraylen<2:
return

pivotIndex=partition(array, begin, end)

doquicksort(array, begin, pivotIndex-1)
doquicksort(array, pivotIndex+1, end)

doquicksort(array, 0, len(array)-1)

classQuickSortTestFunctions(unittest.TestCase):

defisSorted(self, array):
iflen(array) <2:
returnTrue

prev_index=0

foriinxrange(1, len(array)):
ifarray[prev_index] >array[i]:
returnFalse
prev_index=i

returnTrue

defsort_and_test(self, array):
quicksort(array)
returnself.isSorted(array)

deftest_sorted_empty(self):
self.assertTrue(self.sort_and_test([]))

deftest_sorted_one(self):
self.assertTrue(self.sort_and_test([1]))

deftest_sorted_two(self):
self.assertTrue(self.sort_and_test([2,1]))
self.assertTrue(self.sort_and_test([1,1]))

deftest_random(self):
foriinxrange(0, 100):
array= [ random.randint(-1000000, 1000000) forjinxrange(0, random.randint(20,100))]
self.assertTrue(self.sort_and_test(array))

if__name__=="__main__":

array= [ random.randint(0, 100) foriinxrange(0, 20) ]

print("Initial array is:", array)
quicksort(array)
print("Quicksorted array is:", array)

unittest.main()
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
importrandom
importunittest

defquicksort(array):
defswap(a, b):
temp=array[a]
array[a] =array[b]
array[b] =temp

defpartition(array, begin, end):
# pick pivot elem and move to end
pivotIndex=random.randint(begin, end)
pivotElem=array[pivotIndex]
swap(pivotIndex, end)

swapindex=begin
foriinxrange(begin, end):
ifarray[i] <pivotElem:
swap(swapindex, i)
swapindex+=1

swap(swapindex, end)
returnswapindex

defdoquicksort(array, begin, end):
arraylen=end-begin+1

ifarraylen<2:
return

pivotIndex=partition(array, begin, end)

doquicksort(array, begin, pivotIndex-1)
doquicksort(array, pivotIndex+1, end)

doquicksort(array, 0, len(array)-1)

classQuickSortTestFunctions(unittest.TestCase):

defisSorted(self, array):
iflen(array) <2:
returnTrue

prev_index=0

foriinxrange(1, len(array)):
ifarray[prev_index] >array[i]:
returnFalse
prev_index=i

returnTrue

defsort_and_test(self, array):
quicksort(array)
returnself.isSorted(array)

deftest_sorted_empty(self):
self.assertTrue(self.sort_and_test([]))

deftest_sorted_one(self):
self.assertTrue(self.sort_and_test([1]))

deftest_sorted_two(self):
self.assertTrue(self.sort_and_test([2,1]))
self.assertTrue(self.sort_and_test([1,1]))

deftest_random(self):
foriinxrange(0, 100):
array= [ random.randint(-1000000, 1000000) forjinxrange(0, random.randint(20,100))]
self.assertTrue(self.sort_and_test(array))

if__name__=="__main__":

array= [ random.randint(0, 100) foriinxrange(0, 20) ]

print("Initial array is:", array)
quicksort(array)
print("Quicksorted array is:", array)

unittest.main()
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
importrandom
importunittest

defquicksort(array):
defswap(a, b):
temp=array[a]
array[a] =array[b]
array[b] =temp

defpartition(array, begin, end):
# pick pivot elem and move to end
pivotIndex=random.randint(begin, end)
pivotElem=array[pivotIndex]
swap(pivotIndex, end)

swapindex=begin
foriinxrange(begin, end):
ifarray[i] <pivotElem:
swap(swapindex, i)
swapindex+=1

swap(swapindex, end)
returnswapindex

defdoquicksort(array, begin, end):
arraylen=end-begin+1

ifarraylen<2:
return

pivotIndex=partition(array, begin, end)

doquicksort(array, begin, pivotIndex-1)
doquicksort(array, pivotIndex+1, end)

doquicksort(array, 0, len(array)-1)

classQuickSortTestFunctions(unittest.TestCase):

defisSorted(self, array):
iflen(array) <2:
returnTrue

prev_index=0

foriinxrange(1, len(array)):
ifarray[prev_index] >array[i]:
returnFalse
prev_index=i

returnTrue

defsort_and_test(self, array):
quicksort(array)
returnself.isSorted(array)

deftest_sorted_empty(self):
self.assertTrue(self.sort_and_test([]))

deftest_sorted_one(self):
self.assertTrue(self.sort_and_test([1]))

deftest_sorted_two(self):
self.assertTrue(self.sort_and_test([2,1]))
self.assertTrue(self.sort_and_test([1,1]))

deftest_random(self):
foriinxrange(0, 100):
array= [ random.randint(-1000000, 1000000) forjinxrange(0, random.randint(20,100))]
self.assertTrue(self.sort_and_test(array))

if__name__=="__main__":

array= [ random.randint(0, 100) foriinxrange(0, 20) ]

print("Initial array is:", array)
quicksort(array)
print("Quicksorted array is:", array)

unittest.main()
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
importrandom
importunittest

defquicksort(array):
defswap(a, b):
temp=array[a]
array[a] =array[b]
array[b] =temp

defpartition(array, begin, end):
# pick pivot elem and move to end
pivotIndex=random.randint(begin, end)
pivotElem=array[pivotIndex]
swap(pivotIndex, end)

swapindex=begin
foriinxrange(begin, end):
ifarray[i] <pivotElem:
swap(swapindex, i)
swapindex+=1

swap(swapindex, end)
returnswapindex

defdoquicksort(array, begin, end):
arraylen=end-begin+1

ifarraylen<2:
return

pivotIndex=partition(array, begin, end)

doquicksort(array, begin, pivotIndex-1)
doquicksort(array, pivotIndex+1, end)

doquicksort(array, 0, len(array)-1)

classQuickSortTestFunctions(unittest.TestCase):

defisSorted(self, array):
iflen(array) <2:
returnTrue

prev_index=0

foriinxrange(1, len(array)):
ifarray[prev_index] >array[i]:
returnFalse
prev_index=i

returnTrue

defsort_and_test(self, array):
quicksort(array)
returnself.isSorted(array)

deftest_sorted_empty(self):
self.assertTrue(self.sort_and_test([]))

deftest_sorted_one(self):
self.assertTrue(self.sort_and_test([1]))

deftest_sorted_two(self):
self.assertTrue(self.sort_and_test([2,1]))
self.assertTrue(self.sort_and_test([1,1]))

deftest_random(self):
foriinxrange(0, 100):
array= [ random.randint(-1000000, 1000000) forjinxrange(0, random.randint(20,100))]
self.assertTrue(self.sort_and_test(array))

if__name__=="__main__":

array= [ random.randint(0, 100) foriinxrange(0, 20) ]

print("Initial array is:", array)
quicksort(array)
print("Quicksorted array is:", array)

unittest.main()
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
importrandom
importunittest

defquicksort(array):
defswap(a, b):
temp=array[a]
array[a] =array[b]
array[b] =temp

defpartition(array, begin, end):
# pick pivot elem and move to end
pivotIndex=random.randint(begin, end)
pivotElem=array[pivotIndex]
swap(pivotIndex, end)

swapindex=begin
foriinxrange(begin, end):
ifarray[i] <pivotElem:
swap(swapindex, i)
swapindex+=1

swap(swapindex, end)
returnswapindex

defdoquicksort(array, begin, end):
arraylen=end-begin+1

ifarraylen<2:
return

pivotIndex=partition(array, begin, end)

doquicksort(array, begin, pivotIndex-1)
doquicksort(array, pivotIndex+1, end)

doquicksort(array, 0, len(array)-1)

classQuickSortTestFunctions(unittest.TestCase):

defisSorted(self, array):
iflen(array) <2:
returnTrue

prev_index=0

foriinxrange(1, len(array)):
ifarray[prev_index] >array[i]:
returnFalse
prev_index=i

returnTrue

defsort_and_test(self, array):
quicksort(array)
returnself.isSorted(array)

deftest_sorted_empty(self):
self.assertTrue(self.sort_and_test([]))

deftest_sorted_one(self):
self.assertTrue(self.sort_and_test([1]))

deftest_sorted_two(self):
self.assertTrue(self.sort_and_test([2,1]))
self.assertTrue(self.sort_and_test([1,1]))

deftest_random(self):
foriinxrange(0, 100):
array= [ random.randint(-1000000, 1000000) forjinxrange(0, random.randint(20,100))]
self.assertTrue(self.sort_and_test(array))

if__name__=="__main__":

array= [ random.randint(0, 100) foriinxrange(0, 20) ]

print("Initial array is:", array)
quicksort(array)
print("Quicksorted array is:", array)

unittest.main()
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
importrandom
importunittest

defquicksort(array):
defswap(a, b):
temp=array[a]
array[a] =array[b]
array[b] =temp

defpartition(array, begin, end):
# pick pivot elem and move to end
pivotIndex=random.randint(begin, end)
pivotElem=array[pivotIndex]
swap(pivotIndex, end)

swapindex=begin
foriinxrange(begin, end):
ifarray[i] <pivotElem:
swap(swapindex, i)
swapindex+=1

swap(swapindex, end)
returnswapindex

defdoquicksort(array, begin, end):
arraylen=end-begin+1

ifarraylen<2:
return

pivotIndex=partition(array, begin, end)

doquicksort(array, begin, pivotIndex-1)
doquicksort(array, pivotIndex+1, end)

doquicksort(array, 0, len(array)-1)

classQuickSortTestFunctions(unittest.TestCase):

defisSorted(self, array):
iflen(array) <2:
returnTrue

prev_index=0

foriinxrange(1, len(array)):
ifarray[prev_index] >array[i]:
returnFalse
prev_index=i

returnTrue

defsort_and_test(self, array):
quicksort(array)
returnself.isSorted(array)

deftest_sorted_empty(self):
self.assertTrue(self.sort_and_test([]))

deftest_sorted_one(self):
self.assertTrue(self.sort_and_test([1]))

deftest_sorted_two(self):
self.assertTrue(self.sort_and_test([2,1]))
self.assertTrue(self.sort_and_test([1,1]))

deftest_random(self):
foriinxrange(0, 100):
array= [ random.randint(-1000000, 1000000) forjinxrange(0, random.randint(20,100))]
self.assertTrue(self.sort_and_test(array))

if__name__=="__main__":

array= [ random.randint(0, 100) foriinxrange(0, 20) ]

print("Initial array is:", array)
quicksort(array)
print("Quicksorted array is:", array)

unittest.main()
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
importrandom
importunittest

defquicksort(array):
defswap(a, b):
temp=array[a]
array[a] =array[b]
array[b] =temp

defpartition(array, begin, end):
# pick pivot elem and move to end
pivotIndex=random.randint(begin, end)
pivotElem=array[pivotIndex]
swap(pivotIndex, end)

swapindex=begin
foriinxrange(begin, end):
ifarray[i] <pivotElem:
swap(swapindex, i)
swapindex+=1

swap(swapindex, end)
returnswapindex

defdoquicksort(array, begin, end):
arraylen=end-begin+1

ifarraylen<2:
return

pivotIndex=partition(array, begin, end)

doquicksort(array, begin, pivotIndex-1)
doquicksort(array, pivotIndex+1, end)

doquicksort(array, 0, len(array)-1)

classQuickSortTestFunctions(unittest.TestCase):

defisSorted(self, array):
iflen(array) <2:
returnTrue

prev_index=0

foriinxrange(1, len(array)):
ifarray[prev_index] >array[i]:
returnFalse
prev_index=i

returnTrue

defsort_and_test(self, array):
quicksort(array)
returnself.isSorted(array)

deftest_sorted_empty(self):
self.assertTrue(self.sort_and_test([]))

deftest_sorted_one(self):
self.assertTrue(self.sort_and_test([1]))

deftest_sorted_two(self):
self.assertTrue(self.sort_and_test([2,1]))
self.assertTrue(self.sort_and_test([1,1]))

deftest_random(self):
foriinxrange(0, 100):
array= [ random.randint(-1000000, 1000000) forjinxrange(0, random.randint(20,100))]
self.assertTrue(self.sort_and_test(array))

if__name__=="__main__":

array= [ random.randint(0, 100) foriinxrange(0, 20) ]

print("Initial array is:", array)
quicksort(array)
print("Quicksorted array is:", array)

unittest.main()