Z3-Rešenja

1. Zadatak 1
2. Zadatak 2

Zadatak 1

# file: 'z3-1.py'
import sys
import random
import time
from math import inf
from math import floor

def random_list(min, max, elements):
    list = random.sample(range(min, max), elements)
    return list

def merge(A, p, q, r):
    n1 = q - p + 1
    n2 = r - q
    L, R = [], []
    i, j = 0, 0
    for i in range(n1):
        L.append(A[p + i])
    for j in range(n2):
        R.append(A[q + j + 1])
    L.append(inf)
    R.append(inf)
    i = 0
    j = 0
    for k in range(p, r + 1):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def merge_sort(A, p, r):
    if p < r:
        q = (p + r) // 2
        merge_sort(A, p, q)
        merge_sort(A, q + 1, r)
        merge(A, p, q, r)

def test(elements):
    l = random_list(1, elements + 1, elements)
    start_time = time.clock()
    
    merge_sort(l, 0, len(l) - 1)

    end_time = time.clock() - start_time
    print("Elements:", elements, "Duration: ", end_time)

if __name__ == "__main__":
    for i in range(500, 10000, 500):
        test(i)

Zadatak 2

# file: 'z3-2.py'

import sys
import random
import time

def random_list(min, max, elements):
    list = random.sample(range(min, max), elements)
    return list

def partition(A, p, r):
    x = A[r]
    i = p
    for j in range(p, r):
        if A[j] <= x:
            A[i], A[j] = A[j], A[i]
            i += 1
    A[i], A[r] = A[r], A[i]
    return i

def randomized_partition(A, p, r):
    i = random.randint(p, r)
    A[r], A[i] = A[i], A[r]
    return partition(A, p, r)

def quicksort(A, p, r):
    if p < r:
        q = randomized_partition(A, p, r)
        quicksort(A, p, q - 1)
        quicksort(A, q + 1, r)

def test(elements):
    l = random_list(1, elements + 1, elements)
    start_time = time.clock()
    
    quicksort(l, 0, len(l) - 1)

    end_time = time.clock() - start_time
    print("Elements:", elements, "Duration: ", end_time)

if __name__ == "__main__":
    for i in range(500, 10000, 500):
        test(i)