6. cas

#6.cas
#Selection sort i Quick sort

#Selection sort
#PSEUDOKOD
Selection-Sort(A)
n = length(A)
    for i=1 to n-1

    min_idx = i

    for j=i+1 to n

    if A[j] < A[min_idx]

    min_idx = j

    temp = A[min_idx]

    A[min_idx]=A[i]

    A[i] = temp
end

#redovan kod
function selectionSort!(A)
    n = length(A)
    for i=1:n-1
    minIdx = i
    for j=i+1:n
    if A[j] < A[minIdx]
    minIdx = j
    end
    end
    if i!=minIdx
    A[[i minIdx]] = A[[minIdx i]];
    end
    end
end

# Zadatak 6.1.
#Implementirati Selection sort u Julia-i koji sortira elemente niza
#brojeva u opadajućem redosledu. Pronaći najveću razliku između
#dva susedna broja u sortiranom nizu

function selectionSort!(A)
    n = length(A)
    for i=1:n-1
    minIdx = i
        for j=i+1:n
            if A[j] > A[minIdx]
            minIdx = j
            end
        end
        if i!=minIdx
        A[[i minIdx]] = A[[minIdx i]];
        end
    end
end

A=[7 4 5 2]
selectionSort!(A)
println("Sortirani niz izgleda ovako: $A")
max_razlika = A[1]-A[2] #poredimo susedne
n=length(A) #definisemo kraj
for i=2:n-1
    if A[i]-A[i+1] > max_razlika
        max_razlika = A[i]-A[i+1]
    end
end

println("Najveca razlika susednih elemenata je $max_razlika")


#Zadatak 6.2. Sortirati rastuće niz struktura koje predstavljaju
#studente prema broju indeksa, upotrebom Selection sort algoritma.
#Struktura koja predstavlja studenta sadrži polja ime, prezime i
#brojIndeksa.

struct Student
    ime::String
    prezime::String
    brojIndeksa::Int
end

function ispisStudenata(studenti)
   for i in 1:length(studenti)
      println("$i. $(studenti[i].ime), $(studenti[i].prezime), $(studenti[i].brojIndeksa)");
   end
end

studenti = []
push!(studenti, Student("Marko", "Markovic", 13))
push!(studenti, Student("Nikola", "Tomic", 8))
push!(studenti, Student("Srdjan", "Knezevic", 5))
push!(studenti, Student("Branislav", "Tomic", 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 selectionSort!(A, za_uporedi)
    n = length(A)
    for i=1:n-1
    minIdx = i
        for j=i+1:n
            if (za_uporedi(A[j], A[minIdx]))
            minIdx = j
            end
        end
        if i!=minIdx
        A[[i minIdx]] = A[[minIdx i]];
        end
    end
end

function uporedi(stud1,stud2)
    return stud1.brojIndeksa<stud2.brojIndeksa
end

println("Nesortirani studenti")
ispisStudenata(studenti)

selectionSort!(studenti, uporedi)
println("Sortirani studenti")
ispisStudenata(studenti)


# Qucik sort ~ Merge sort, podeli i osvoji paradigma, najtezi
#PSEUDOKOD, tesko
#redovan kod

function quickSort!(A)
    quickSortStep!(A, 1, length(A));
    end

function quickSortStep!(A, p, r)
    if p < r
    q = partition!(A, p, r);
    quickSortStep!(A, p, q-1);
    quickSortStep!(A, q+1, r);
    end
end

function partition!(A, p, r)
    x = A[r];
    i = p - 1;
    for j = p:r-1
    if A[j] <= x
    i = i + 1;
    A[[i j]] = A[[j i]];
    end
    end
    A[[i+1 r]] = A[[r i+1]];
    return i + 1;
end


#Zadatak 6.3. Implementirati Quick sort u Julia-i tako da sortira
#elemente niza brojeva u opadajućem redosledu. Prebrojati koliko
#različitih brojeva postoji.

function quickSort!(A)
    quickSortStep!(A, 1, length(A));
end

function quickSortStep!(A, p, r)
    if p < r
    q = partition!(A, p, r);
    quickSortStep!(A, p, q-1);
    quickSortStep!(A, q+1, r);
    end
end

function partition!(A, p, r)
    x = A[r];
    i = p - 1;
    for j = p:r-1
        if A[j] >= x    #opadajuci redosled
        i = i + 1;
        A[[i j]] = A[[j i]];
        end
    end
    A[[i+1 r]] = A[[r i+1]];
    return i + 1;
end

B = [2 19 5 19 7 1 14 9 1 1 22 1 8]
quickSort!(B)
println("Sortirani niz izgleda ovako $B")
br=1
for i in 1:length(B)-1
    if  B[i] != B[i+1]
        br=br+1
    end
end
println("Broj razlicitih je $br")   #imamo 9 razlicitih


#Zadatak 6.4. Sortirati niz struktura koje predstavljaju studente
#prema prezimenu, upotrebom Quick sort algoritma. Ukoliko dva
#studenta imaju isto prezime, sortirati ih po imenu. Studente sa
#istim imenom i prezimenom sortirati po broju indeksa. Struktura
#koja predstavlja studenta sadrži polja ime, prezime i brojIndeksa.

function quickSort!(A, za_uporedi)
    quickSortStep!(A, 1, length(A), za_uporedi);
    end

function quickSortStep!(A, p, r, za_uporedi)
    if p < r
    q = partition!(A, p, r, za_uporedi);
    quickSortStep!(A, p, q-1, za_uporedi);
    quickSortStep!(A, q+1, r, za_uporedi);
    end
end

function partition!(A, p, r, za_uporedi)
    x = A[r];
    i = p - 1;
    for j = p:r-1
    if za_uporedi(A[j], x)
    i = i + 1;
    A[[i j]] = A[[j i]];
    end
    end
    A[[i+1 r]] = A[[r i+1]];
    return i + 1;
end

function uporedi(s1, s2)
    return s1.prezime < s2.prezime || s1.prezime == s2.prezime && s1.ime < s2.ime ||
    s1.prezime == s2.prezime && s1.ime == s2.ime && s1.brojIndeksa < s2.brojIndeksa;
end