def divide(list, start, end):
i = start
border_value = list[end]
for j in range(start, end):
if list[j] <= border_value:
list[i], list[j] = list[j], list[i]
i += 1
list[i], list[end] = list[end], list[i]
return i
def quick_sort(list, start, end):
if start < end:
border_index = divide(list, start, end)
quick_sort(list, start, border_index -1)
quick_sort(list, border_index + 1, end)
list = [20, 7, 5, 8, 9, 8, 22, 34, 6, 18, 15]
quick_sort(list, 0, len(list)-1)
list
import time
import random
#declarations
max_limit = 20000
my_list1 = [random.randint(0, max_limit) for i in range(max_limit)]
my_list2 = my_list1.copy()
my_list3 = my_list1.copy()
my_list4 = my_list1.copy()
my_list5 = my_list1.copy()
my_list6 = my_list1.copy()
# functions
def sort_bubble(list):
is_change = True
while is_change:
is_change = False
for i in range(len(list)-1):
if list[i] > list[i+1]:
list[i],list[i+1] = list[i+1],list[i]
is_change = True
def sort_bubble2(list):
# don't compare values at the end of the list - they are already sorted
max_index = len(list) - 1
for max_not_sorted_index in range(max_index,0,-1):
is_change = False
for i in range(max_not_sorted_index):
if list[i] > list[i+1]:
list[i],list[i+1] = list[i+1],list[i]
is_change = True
if not is_change:
break
def sort_insert(list):
# starting from 1, because this first element is already "sorted"
# all items need to be put in place, so this loop needs to iterate for every element
for sort_border in range(1,len(list)):
# we will try to put the new item into the sublist of sorted elements
curr_idx = sort_border - 1
value = list[curr_idx+1] # next value to be inserted into data
while list[curr_idx] > value and curr_idx >= 0:
list[curr_idx+1] = list[curr_idx]
curr_idx = curr_idx-1
#now the good position has been found and we put there the considered element
list[curr_idx+1] = value
def sort_select(list):
for run in range(len(list)):
min_index = run
for i in range(run+1, len(list)):
if list[i] < list[min_index]:
min_index = i
list[run], list[min_index] = list[min_index], list[run]
def sort_merge(list):
list_len = len(list)
sorted_list = []
if list_len <= 1:
sorted_list = list
else:
middle_point = list_len // 2
list_left = sort_merge(list[:middle_point])
list_right = sort_merge(list[middle_point:])
idx_left = idx_right = 0
while idx_left < len(list_left) and idx_right < len(list_right):
if list_left[idx_left] < list_right[idx_right]:
sorted_list.append(list_left[idx_left])
idx_left += 1
else:
sorted_list.append(list_right[idx_right])
idx_right += 1
sorted_list.extend(list_left[idx_left:])
sorted_list.extend(list_right[idx_right:])
return sorted_list
def quick_sort_divide(list, start, end):
i = start
border_value = list[end]
for j in range(start, end):
if list[j] <= border_value:
list[i], list[j] = list[j], list[i]
i += 1
list[i], list[end] = list[end], list[i]
return i
def quick_sort(list, start, end):
if start < end:
border_index = quick_sort_divide(list, start, end)
quick_sort(list, start, border_index -1)
quick_sort(list, border_index + 1, end)
# checking time - case sort_bubble
start = time.time()
sort_bubble(my_list1)
stop = time.time()
print(f'Sorting duration for function sort_bubble: {stop - start}')
# checking time - case sort_bubble2
start = time.time()
sort_bubble2(my_list2)
stop = time.time()
print(f'Sorting duration for function sort_bubble2: {stop - start}')
# checking time - case sort_insert
start = time.time()
sort_insert(my_list3)
stop = time.time()
print(f'Sorting duration for function sort_insert: {stop - start}')
# checking time - case sort_select
start = time.time()
sort_select(my_list4)
stop = time.time()
print(f'Sorting duration for function sort_select: {stop - start}')
# checking time - case sort_merge
start = time.time()
sort_merge(my_list5)
stop = time.time()
print(f'Sorting duration for function sort_merge: {stop - start}')
# checking time - case quick_sort
start = time.time()
quick_sort(my_list6, 0, len(my_list6)-1)
stop = time.time()
print(f'Sorting duration for function quick_sort: {stop - start}')