pejst

#5. cas
#Kreiranje niza sa zadatim brojem elemenata, npr.
# niz = Array{Int64}(undef, 10)
#Kreiranje niza sa nula elemenata, npr.
# niz = []
#M = typemax(Int64), M postaje najveći ceo broj

# Insertion sort
# poredimo 2. element sa 1. i ako je 1. veci od 2. menjamo mesta
# i to radi sa celim nizom, poredi sledeci sa prethodnim
# i ako ti je prethodni veci od sledeceg, menjaju im se mesta
# i tako proverava ceo niz :)

    1 6 4 6 5 8 2 9 1
j = 1 2 3 4 5 6 7 8 9
i = 1 2 3 4 5 6 7 8 9
#PSEUDOKOD
for j = 2 to length(A)
     key = A[j]
     i = j-1
     while i>0 and A[i]>key #guranje elemenata, A[i]<key ovo ti je
                            #za opadajuce sortiranje
    A[i+1] = A[i]
    i -= 1
     end
     A[i+1] = key
    end
end

#redovan kod
function insertionSort!(A)
    for j in 2:length(A)
    key = A[j]
    i = j-1
    while(i>0 && A[i]>key)
    A[i+1] = A[i]
    i = i-1
    end
    A[i+1] = key
    end
    end
end

# Insertion sort, strukture
# Primer 5.1. Modifikovati Insertion Sort algoritam tako da
# sortira niz struktura studenti prema broju indeksa.

struct Student
    ime::String
    brojIndeksa::Int
end
# f-ja za ispis svih studenata
function ispisStudenata(studenti)
        for i in 1:length(studenti)
        println("$i. $(studenti[i].ime), $(studenti[i].brojIndeksa)");
    end
end

# kreiramo niz
#za pravljenje niza mozes da koristis i onaj drugi nacin
#sa praznim array i onda dodajest student[1]......
studenti = []
push!(studenti,Student("Marko Markovic", 13))
push!(studenti,Student("Nikola Tomic", 8))
push!(studenti,Student("Srdjan Knezevic", 5))
push!(studenti,Student("Vanja Kovacevic", 17))
push!(studenti,Student("Nenad Nikolic", 16))
push!(studenti,Student("Ivana Ivanovic", 2))
push!(studenti,Student("Branislav Tomic", 9))
push!(studenti,Student("Stefan Zivkovic", 3))

function manji(student1, student2)
    return student1.brojIndeksa < student2.brojIndeksa;
end

function insertionSortStudenti!(studenti, jeManji)
    for j = 2:length(studenti);
    key = studenti[j];
    i = j-1;
    while(i>0 && jeManji(key, studenti[i]))
    studenti[i+1] = studenti[i];
    i = i-1;
    end
    studenti[i+1] = key;
    end
end

#pokretanje sortiranja
println("Nesortirani spisak studenata:\n")
ispisStudenata(studenti)
insertionSortStudenti!(studenti, manji)
println("Sortirani spisak studenata:\n")
ispisStudenata(studenti)
# Napomena: Na početku skripte neophodno je uvesti sve korišćene
#fajlove u kojima se nalaze strukture podataka i funkcije,
#koristeći naredbu include()

# Merge sort
#vizuelno na YT, geeksforgeeks(zelen)
    L          R
   2 3 (max)| 4 5 (max) #min pisemo za opadajuci niz
                        #max i min su pomocni clanovi
da li je 2>4
nije, pa smestamo 2 na pocetak niza
2
da li je 3>4
nije pa smestamo 3 posle 2
2 3
da li je max>4
jeste, max je uvek veci
stavljamo 4 posle 3
2 3 4
da li je max>5
jeste, max je uvek veci
smestamo 5 posle 4
2 3 4 5
#imamo levu i desnu stranu niza (p i r) i sredinu q
#leva polovina ide od p do q
#desna polovina ide od q+1 do r

#poredimoo prvi element u levoj polovini sa prvim elementom
#desne polovine, ako je manji, smestamo ga u niz i rekurzija