Zadatak 1
Zadatak 2
Zadatak 3
Zadatak 4
Zadatak 1
# file: 'z2-1.py'
import random
import time
def random_list ( min , max , elements ):
list = random . sample ( range ( min , max ), elements )
return list
def insertion_sort ( arr ):
for j in range ( 1 , len ( arr )):
key = arr [ j ]
i = j - 1
while i >= 0 and arr [ i ] > key :
arr [ i + 1 ] = arr [ i ]
i = i - 1
arr [ i + 1 ] = key
def test ( elements ):
l = random_list ( 1 , elements + 1 , elements )
start_time = time . clock ()
insertion_sort ( l )
end_time = time . clock () - start_time
print ( "Elements:" , elements , "Duration: " , end_time )
if __name__ == "__main__" :
for i in range ( 500 , 5000 , 500 ):
test ( i )
Zadatak 2
# file: 'z2-2.py'
import random
import time
def random_list ( min , max , elements ):
list = random . sample ( range ( min , max ), elements )
return list
def bubble_sort ( arr ):
for i in range ( len ( arr ) - 1 ):
for j in range ( i , len ( arr )):
if arr [ i ] > arr [ j ]:
t = arr [ i ]
arr [ i ] = arr [ j ]
arr [ j ] = t
def test ( elements ):
l = random_list ( 1 , elements + 1 , elements )
start_time = time . clock ()
bubble_sort ( l )
end_time = time . clock () - start_time
print ( "Elements:" , elements , "Duration: " , end_time )
if __name__ == "__main__" :
for i in range ( 500 , 5000 , 500 ):
test ( i )
Zadatak 3
# file: 'z2-3.py'
import random
import time
def random_list ( min , max , elements ):
list = random . sample ( range ( min , max ), elements )
return list
def linear_search ( arr , val ):
for i in range ( len ( arr )):
if arr [ i ] == val :
return i
return - 1
def test ( elements ):
l = list ( set ( random_list ( 1 , elements + 1 , elements )))
start_time = time . clock ()
ind = linear_search ( l , random . randint ( 1 , elements ))
end_time = time . clock () - start_time
print ( "Elements:" , elements , "Index:" , ind , "Duration: " , end_time )
if __name__ == "__main__" :
for i in range ( 5000 , 50000 , 5000 ):
test ( i )
Zadatak 4
# file: 'z2-4.py'
import random
import time
def generate_list ( min , max ):
list = [ x for x in range ( min , max )]
return list
def binary_search ( arr , val , left , right ):
i = int (( left + right ) / 2 )
if arr [ i ] == val :
return i
elif left >= right or i == left or i == right :
return - 1
elif arr [ i ] > val :
return binary_search ( arr , val , left , i )
else :
return binary_search ( arr , val , i , right )
def test ( elements ):
l = generate_list ( 1 , elements )
start_time = time . clock ()
ind = binary_search ( l , random . randint ( 1 , elements ), 0 , len ( l ))
end_time = time . clock () - start_time
print ( "Elements:" , elements , "Index:" , ind , "Duration: " , end_time )
if __name__ == "__main__" :
for i in range ( 10000 , 500000 , 10000 ):
test ( i )
Comments 💬
© 2018 - 2023 Milovan Tomašević. All rights reserved.
Impress
|
Cookies Policy
Powered by MT v9.1.4