Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // 1 a)
- def swap(tab: Array[Int], i: Int, j: Int): Unit ={
- val aux = tab(i) //przyjmuje tablice i nr indeksow ktore zamieni
- tab(i) = tab(j)
- tab(j) = aux
- }
- // 1 b)
- def choose_pivot(tab: Array[Int], m: Int, n: Int): Int =
- tab((m + n) / 2) //m - (index) poczatek tab n - (index)koniec
- //zwraca element srodkowy - pivot
- def partition(tab: Array[Int], l: Int, r: Int): (Int, Int) ={
- var i = l
- var j = r
- val pivot = choose_pivot(tab, l, r)
- while (i <= j) { //ustawia elem
- while (tab(i) < pivot) i += 1 //mniejsze przed pivotem
- while (pivot < tab(j)) j -= 1 //wieksze po pivocie
- if (i <= j) {
- swap(tab, i, j)
- i += 1
- j -= 1
- }
- }
- (i, j) //para ktora dzieli tablice
- //na elem wieksze i mniejsze od pivota
- }
- //1 c)
- def quick(tab: Array[Int], l: Int, r: Int): Unit =
- if (l < r) { //sprawdza czy index poczatku
- //na pewno jest mniejszy od indexu konca
- val (i, j) = partition(tab, l, r) //bierze pare dzielaca
- if ((j - l) < (r - i)) { //sprawdza ktora podtablica jest krotsza
- quick(tab, l, j) //sortuje rekurencyjnie
- quick(tab, i, r)//najpierw krotsza, potem dluzsza
- } //dzieki temu zlozonosc lg n
- else {
- quick(tab, i, r)
- quick(tab, l, j)
- }
- }
- //1 d)
- def quicksort(tab: Array[Int]) =
- quick(tab, 0, tab.length - 1) //wywoluje sortwanie dla calej tablicy
- //2
- def whileLoop(war: => Boolean, akcja: => Unit): Unit =
- if (war) {
- akcja
- whileLoop(war, akcja)
- }
- var z = 0 //nie moze byc val, bo jest niemodyfikowalna
- whileLoop( z<10, { printf(z.toString) ;z=z+1 } )
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement