Основи програмирања

БРТСИ1300 / ОЕ1-ОП

View on GitHub

Основи програмирања: вежбе - XII недеља

Алгоритми сортирања

Сортирање избором - Selection Sort

Имплементација коришћењем угнеждене while петље
def sortiranjeIzborom(N):
    for i in range(len(N) - 1):
        minIndeks = i
        minVrednost = N[i]
        j = i + 1
        while j < len(N):
           if minVrednost > N[j]:
              minIndeks = j
              minVrednost = N[j]
           j = j + 1
        privremeno = N[i]
        N[i] = N[minIndeks]
        N[minIndeks] = privremeno
Имплементација коришћењем угнеждене for петље
def sortiranje_izborom(niz):
    for i in range(len(niz)):
        for j in range(i+1, len(niz)):
            if niz[i] > niz[j]:
                niz[i], niz[j] = niz[j], niz[i]
                
#niz = [5, 2, 0, 4, 7, 9, 8, -3, 12]
#sortiranje_izborom(niz)
#print(niz)

Сортирање мехуром - Bubble Sort

Имплементација коришћењем while и for петље
def sortiranjeMehurom(N):
    zamena = False
    while not zamena:
        zamena = True
        for j in range(1, len(N)):
            if N[j-1] > N[j]:
               zamena = False
               privremeno = N[j]
               N[j] = N[j-1]
               N[j-1] = privremeno
Имплементација коришћењем for петљи
def sortiranje_mehurom(niz):
    zamena = False
    for n in range(len(niz)-1, 0, -1):
        for i in range(n):
            if niz[i] > niz[i+1]:
                zamena = True
                niz[i], niz[i+1] = niz[i+1], niz[i]
        
        if not zamena:
            return
 
#niz = [39, 12, 18, 85, 72, 10, 2, 18]
 
#sortiranje_mehurom(niz)
#print(niz)

Сортирање уметањем - Insertion Sort

Имплементација
def sortiranjeUmetanjem(N):
    for i in range(1, len(N)):
        trenutno = N[i]
        j = i - 1
        while j >= 0 and trenutno < N[j]:
           N[j+1] = N[j]
           j = j - 1
        N[j+1] = trenutno

Сортирање спајањем - Merge Sort

Имплементација
import operator

def spajanje(leva, desna, poredi):
    rezultat, i, j = [], 0, 0
    while i < len(leva) and j < len(desna):
        if poredi(leva[i], desna[j]):
            rezultat.append(leva[i])
            i = i + 1
        else:
            rezultat.append(desna[j])
            j = j + 1
    
    while (i < len(leva)):
        rezultat.append(leva[i])
        i = i + 1
    
    while (j < len(desna)):
        rezultat.append(desna[j])
        j = j + 1
    
    return rezultat

def sortiranje_spajanjem(N, poredi = operator.lt):
    if len(N) < 2:
        return N[:]
    
    sredina = int(len(N)/2)
    leva = sortiranje_spajanjem(N[:sredina], poredi)
    desna = sortiranje_spajanjem(N[sredina:],poredi)
    
    return spajanje(leva, desna, poredi)

#niz = [5, 2, 0, 4, 7, 9, 8, -3, 12]
#print(niz)
#print(sortiranje_spajanjem(niz))

Алгоритми претраге

Линеарна претрага

Имплементација - итеративно
def linearna_pretraga_iterativno(niz, x):
    for i in range(len(niz)):
        if niz[i] == x:
            return i
    
    return -1

#niz = [39, 12, 18, 85, 72, 10, 2, 18]
#print(linearna_pretraga_iterativno(niz, 85))
Имплементација - рекурзивно
def linearna_pretraga_rekurzivno(niz, trenutniIndeks, vrednost):
    if trenutniIndeks == -1:
        return -1
    if niz[trenutniIndeks] == vrednost:
        return trenutniIndeks
    return linearna_pretraga_rekurzivno(niz, trenutniIndeks-1, vrednost)

#niz = [39, 12, 18, 85, 72, 10, 2, 18]
#print(linearna_pretraga_rekurzivno(niz, len(niz)-1, 2))

Бинарна претрага

Имплементација - итеративно
def binarna_pretraga_iterativno(sortiraniNiz, x):
    low = 0
    high = len(niz) - 1
 
    while low <= high:
 
        mid = (high + low) // 2
 
        if niz[mid] == x:
            return mid

        elif niz[mid] < x:
            low = mid + 1
 
        elif niz[mid] > x:
            high = mid - 1
 
    return -1


#niz = [39, 12, 18, 85, 72, 10, 2, 18]
#sortiraniNiz = sorted(niz)
#print(sortiraniNiz)
#print(binarna_pretraga_iterativno(sortiraniNiz, 85))
Имплементација - рекурзивно
def binarna_pretraga_rekurzivno(sortiraniNiz, low, high, x):
 
    if low > high:
        return -1
    
    mid = (high + low) // 2

    if sortiraniNiz[mid] == x:
        return mid

    elif sortiraniNiz[mid] < x:
        return binarna_pretraga_rekurzivno(sortiraniNiz, mid + 1, high, x)

    else:
        return binarna_pretraga_rekurzivno(sortiraniNiz, low, mid - 1, x)

#niz = [39, 12, 18, 85, 72, 10, 2, 18]
#sortiraniNiz = sorted(niz)
#print(sortiraniNiz)
#print(binarna_pretraga_rekurzivno(sortiraniNiz, 0, len(sortiraniNiz)-1, 12))