#biblioteki
import random
from timeit import timeit
import copy
import  numpy

#Zmienna zakresu testów:
### UWAGA ###
# Dla wartosci 999 wykonanie testow trwa dosc dlugo!!!!!!!! #
testRange= 99;

#definicje
def quick_sort(inputList: list, start: int, stop: int):
    i=start;
    j=stop;


    pivot = inputList[int((stop+start-1)/2)]
    while(i<j):
        while(inputList[i]<pivot):
            i=i+1;
        while(inputList[j]>pivot):
            j=j-1;
        if(i<=j):
            inputList[i], inputList[j]=inputList[j], inputList[i];
            i=i+1;
            j=j-1;
    if(start<j):
        quick_sort(inputList, start, j);
    if (i<stop):
        quick_sort(inputList, i, stop);



def bubble_sort(inputList: list) :
    n = len(inputList)
    sortFlag = 0
    while(n>1):
        for i in range(1,n):
            if(inputList[i-1]>inputList[i]):
                sortFlag = 1
                inputList[i-1], inputList[i] = inputList[i], inputList[i-1]
        n=n-1;
    if(sortFlag == 1):
       return




                                                                          ####TESTY#########

#listy z czasami prob:
bubbleTime =[0] * (testRange+1);
quickTime = [0] * (testRange+1);




#lista posortowana:
list1=list(range(0, (testRange+1)));
list2=list(range(0, (testRange+1)));
for i in range(0,testRange):
    t1_bubble = timeit ( "bubble_sort(list1)" , number =1 , globals = globals ())
    t2_quick = timeit ( "quick_sort(list2,0, testRange)" , number =1 , globals = globals ())
    bubbleTime[i]=t1_bubble;
    quickTime[i]=t2_quick;
print('Sredni czas sortowania listy juz posortowanej dla quick-sort to: {:f}ms, a dla bubble-sort to: {:f}ms'.format(numpy.average(quickTime)*1000,numpy.average(bubbleTime)*1000));


#lista posortowana odwrotnie:
list1=list(range(testRange, -1, -1));
list2=list(range(testRange, -1, -1));
for i in range(0,testRange):
    t1_bubble = timeit ( "bubble_sort(list1)" , number =1 , globals = globals ())
    t2_quick = timeit ( "quick_sort(list2,0, testRange)" , number =1 , globals = globals ())
    bubbleTime[i]=t1_bubble;
    quickTime[i]=t2_quick;
print('Sredni czas sortowania listy posortowanej odwrotnie dla quick-sort to: {:f}ms, a dla bubble-sort to: {:f}ms'.format(numpy.average(quickTime)*1000,numpy.average(bubbleTime)*1000));



#lista elementow o tej samej wartosci:
x=random.sample(range(10),k=1);
list1 = [x] *(testRange+1) ;
list2=copy.deepcopy(list1);
for i in range(0,testRange):
    t1_bubble = timeit ( "bubble_sort(list1)" , number =1 , globals = globals ())
    t2_quick = timeit ( "quick_sort(list2,0, testRange)" , number =1 , globals = globals ())
    bubbleTime[i]=t1_bubble;
    quickTime[i]=t2_quick;
print('Sredni czas sortowania listy o tych samych elementach dla quick-sort to: {:f}ms, a dla bubble-sort to: {:f}ms'.format(numpy.average(quickTime)*1000,numpy.average(bubbleTime)*1000));




#rozne wartosci:
for i in range(0,testRange):
    list1 = random.sample(range((testRange+1)*10),k=(testRange+1));
    list2=copy.deepcopy(list1);
    t1_bubble = timeit ( "bubble_sort(list1)" , number =1 , globals = globals ())
    t2_quick = timeit ( "quick_sort(list2, 0, testRange)", number =1 , globals = globals ())
    bubbleTime[i]=t1_bubble;
    quickTime[i]=t2_quick;
print('Sredni czas sortowania listy o roznych wartosciach dla quick-sort to: {:f}ms, a dla bubble-sort to: {:f}ms'.format(numpy.average(quickTime)*1000,numpy.average(bubbleTime)*1000));