Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement