Основи програмирања: вежбе - 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))