Skip to content

Instantly share code, notes, and snippets.

@WangYihang

WangYihang/Sorting.py

Last active July 23, 2019 10:45
Show Gist options
  • Save WangYihang/f1e17a643e8a3e921356c1ed0e91cca2 to your computer and use it in GitHub Desktop.
Save WangYihang/f1e17a643e8a3e921356c1ed0e91cca2 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
Sorting.py
#!/usr/bin/env python
# encoding:utf-8
'''
[2019-07-23 18:45:06.387377] Prepare sorting by BubbleSortV1
[2019-07-23 18:45:06.387377] Sorting started
Swap Times: 42
Loop Times: 225
****************************************************************
****************************************************************
****************************************************************
****************************************************************
****************************************************************
****************************************************************
****************************************************************
****************************************************************
****************************************************************
****************************************************************
****************************************************************
****************************************************************
****************************************************************
****************************************************************
****************************************************************
[2019-07-23 18:45:06.391374] Sorting finished
[2019-07-23 18:45:06.391374] Cost: 0:00:00.003997
[2019-07-23 18:45:06.391374] Prepare sorting by BubbleSortV2
[2019-07-23 18:45:06.391374] Sorting started
Swap Times: 42
Loop Times: 135
****************************************************************
****************************************************************
****************************************************************
****************************************************************
****************************************************************
****************************************************************
****************************************************************
****************************************************************
****************************************************************
[2019-07-23 18:45:06.395372] Sorting finished
[2019-07-23 18:45:06.395372] Cost: 0:00:00.003998
[2019-07-23 18:45:06.395372] Prepare sorting by BubbleSortV3
[2019-07-23 18:45:06.396371] Sorting started
Swap Times: 42
Loop Times: 120
****************************************************************
***********************************************************
*******************************************************
***************************************************
**********************************************
******************************************
**************************************
**********************************
*****************************
*************************
*********************
*****************
************
********
****
[2019-07-23 18:45:06.400369] Sorting finished
[2019-07-23 18:45:06.401368] Cost: 0:00:00.003998
[2019-07-23 18:45:06.401368] Prepare sorting by BubbleSortV4
[2019-07-23 18:45:06.401368] Sorting started
Swap Times: 42
Loop Times: 99
****************************************************************
***********************************************************
*******************************************************
***************************************************
**********************************************
******************************************
**************************************
**********************************
*****************************
[2019-07-23 18:45:06.405366] Sorting finished
[2019-07-23 18:45:06.405366] Cost: 0:00:00.003998
[2019-07-23 18:45:06.405366] Prepare sorting by BubbleSortV5
[2019-07-23 18:45:06.405366] Sorting started
Swap Times: 42
Loop Times: 77
****************************************************************
***********************************************************
*******************************************************
***************************************************
*****************************
*************************
*********************
************
********
[2019-07-23 18:45:06.409364] Sorting finished
[2019-07-23 18:45:06.409364] Cost: 0:00:00.003998
'''
import datetime
import time
class Sorter:
def __init__(self, benchmark=0, display=False):
self.benchmark = benchmark
self.display = display
def _BubbleSortV1(self, x):
swap_times = 0
external_loop = []
for i in range(len(x) - 1):
internal_loop = 0
for j in range(len(x) - 1):
internal_loop += 1
time.sleep(self.benchmark)
a = x[j]
b = x[j + 1]
if a > b:
swap_times += 1
x[j] = b
x[j + 1] = a
external_loop.append(internal_loop)
print("Swap Times: %d" % (swap_times))
print("Loop Times: %d" % (sum(external_loop)))
if self.display:
self.Display(external_loop)
return x
def _BubbleSortV2(self, x):
swap_times = 0
external_loop = []
for i in range(len(x) - 1):
swaped = False
internal_loop = 0
for j in range(len(x) - 1):
internal_loop += 1
time.sleep(self.benchmark)
a = x[j]
b = x[j + 1]
if a > b:
swaped = True
swap_times += 1
x[j] = b
x[j + 1] = a
external_loop.append(internal_loop)
if not swaped:
break
print("Swap Times: %d" % (swap_times))
print("Loop Times: %d" % (sum(external_loop)))
if self.display:
self.Display(external_loop)
return x
def _BubbleSortV3(self, x):
swap_times = 0
external_loop = []
for i in range(len(x) - 1):
internal_loop = 0
for j in range(len(x) - 1 - i):
internal_loop += 1
time.sleep(self.benchmark)
a = x[j]
b = x[j + 1]
if a > b:
swap_times += 1
x[j] = b
x[j + 1] = a
external_loop.append(internal_loop)
print("Swap Times: %d" % (swap_times))
print("Loop Times: %d" % (sum(external_loop)))
if self.display:
self.Display(external_loop)
return x
def _BubbleSortV4(self, x):
swap_times = 0
external_loop = []
for i in range(len(x) - 1):
internal_loop = 0
swaped = False
for j in range(len(x) - 1 - i):
internal_loop += 1
time.sleep(self.benchmark)
a = x[j]
b = x[j + 1]
if a > b:
swaped = True
swap_times += 1
x[j] = b
x[j + 1] = a
external_loop.append(internal_loop)
if not swaped:
break
print("Swap Times: %d" % (swap_times))
print("Loop Times: %d" % (sum(external_loop)))
if self.display:
self.Display(external_loop)
return x
def _BubbleSortV5(self, x):
swap_times = 0
external_loop = []
last_swap = len(x) - 1
for i in range(len(x) - 1):
internal_loop = 0
swaped = False
for j in range(last_swap):
internal_loop += 1
time.sleep(self.benchmark)
a = x[j]
b = x[j + 1]
if a > b:
swaped = True
last_swap = j
swap_times += 1
x[j] = b
x[j + 1] = a
external_loop.append(internal_loop)
if not swaped:
break
print("Swap Times: %d" % (swap_times))
print("Loop Times: %d" % (sum(external_loop)))
if self.display:
self.Display(external_loop)
return x
def Display(self, loops):
SIZE = 0x40
for i in loops:
print("*" * int((i / loops[0]) * SIZE))
def Sort(self, func, data):
result = []
try:
print("[%s] Prepare sorting by %s" % (datetime.datetime.now().strftime('%Y-%m-%d %H:%M:%S.%f'), func))
start = datetime.datetime.now()
print("[%s] Sorting started" % (start.strftime("%Y-%m-%d %H:%M:%S.%f")))
result = getattr(self, "_%s" % (func))(data)
end = datetime.datetime.now()
print("[%s] Sorting finished" % (end.strftime("%Y-%m-%d %H:%M:%S.%f")))
print("[%s] Cost: %s" % (datetime.datetime.now().strftime('%Y-%m-%d %H:%M:%S.%f'), (end - start)), end="\n\n")
except Exception as e:
print("[%s] %r" % (datetime.datetime.now().strftime('%Y-%m-%d %H:%M:%S.%f'), e))
return result
def main():
sorter = Sorter(benchmark=0, display=True)
x = [122, 284, 382, 474, 24, 102, 812, 15, 573, 344, 46, 258, 398, 788, 798, 684]
sorter.Sort("BubbleSortV1", x)
x = [122, 284, 382, 474, 24, 102, 812, 15, 573, 344, 46, 258, 398, 788, 798, 684]
sorter.Sort("BubbleSortV2", x)
x = [122, 284, 382, 474, 24, 102, 812, 15, 573, 344, 46, 258, 398, 788, 798, 684]
sorter.Sort("BubbleSortV3", x)
x = [122, 284, 382, 474, 24, 102, 812, 15, 573, 344, 46, 258, 398, 788, 798, 684]
sorter.Sort("BubbleSortV4", x)
x = [122, 284, 382, 474, 24, 102, 812, 15, 573, 344, 46, 258, 398, 788, 798, 684]
sorter.Sort("BubbleSortV5", x)
if __name__ == '__main__':
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment