Računalništvo 1 (PRA)

lekcije / Urejanje podatkov

Urejanje podatkov

V tokratni lekciji si bomo ogledali preprost algoritem (računski postopek) za urejanje podatkov. Urejanje je eno najpogostejših opravil v računalniški praksi (urejanje po abecedi, urejanje po velikosti, ipd.) in znanih je kar nekaj algoritmov za urejanje.
Obravnavali bomo najpreprostejši primer urejanja: dana je tabela a celih števil, ki jih želimo urediti po velikosti. Na primer, števila
5 9 8 2 3 1 7 6 0 4
uredimo po velikosti
0 1 2 3 4 5 6 7 8 9
Lahko bi tudi urejali tudi nize znakov po abecedi, ali pare števil v leksikografskem redu. Pomembna predpostavka je, da so podatki shranjeni v tabeli, tako da lahko do poljubnega podatka dostopamo hitro. (Če bi bili podatki v seznamu, ali v podatkovni bazi, ki je prevelika, da bi jo shranili v pomnilnik, bi morali uporabljati postopke, ki jih tu ne bomo obravnavali.)

Mešanje

Preden se posvetimo urejanju napišimo še metodo, ki naredi prav nasprotno od urejanja. Potrebujemo jo, da bomo lahko preizkusili, ali metoda za urejanje deluje. Dana je tabela števil
a[0] a[1] a[2] ... a[k]
ki jo želimo dobro premešati. Kako to storimo? Dostikrat se pojavi ideja za naslednji algoritem (take algoritme sem dejansko videl v raznih programih in avtorjem programov se ni dalo dopovedati, da so slabi):
algoritem zmešaj_tabelo(a):
  N = 100000
  ponovi N-krat:
     izberi dva naključna elementa tabele a in ju zamenjaj
Tako nekako mešamo tarok karte, le da postopka ne ponovimo 100000-krat. Vendar pa je to zelo slab računski postopek:
  1. Če ima tabela a več kot N elementov, bo slabo premešana.
  2. Če ima tabelo a zelo malo elementov, ni nobene potrebe, da premesamo 100000-krat.
  3. Po nepotrebnem bomo isti element z veliko verjetnostjo prestavili večkrat.
Boljši postopek za mešanje vsak element premeša natanko enkrat, in sicer takole:
algoritem zmesaj_tabelo(a):
  n = a.length - 1;
  ponavljaj za i od 0 do n:
     j := nakljucno stevilo med i in n;
     zamenjaj a[i] in a[j];
Ta algoritem najprej izbere naključni element in ga postavi v a[0]. Izmed preostalih elementov izbere naključni element in ga postavi v a[1]. Izmed preostalih elementov izbere naključni element in ga postavi v a[2]. In tako naprej. Algoritem opravi natanko toliko dela, kot je treba:
  1. Na i-to mesto zapiše naključno izbrani element samo enkrat.
  2. Vedno opravi ravno toliko zamenjav, kot je potrebno.
  3. Algoritem zagotavlja, da je na koncu tabela naključno premešana.
Algoritem spremenimo v metodo. V Javini standardni knjižnici java.util najdemo razred Random, s katerim dobimo naključna števila. Najprej naredimo objekt razreda Random, nato pa generiramo naključna cela števila z metodo nextInt(int n).
public static void zmesaj(int[] a) {
    Random r = new Random();

    for (int i = 0; i < a.length; i = i + 1) {
        int j = i + r.nextInt(a.length - i);
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}
Naloga 1: Verjetnostno določanje števila π
Naloga 2: Izbiranje točke v krogu

Urejanje z izbiranjem

Študenti matematike radi igrajo tarok (tudi med predavanji). Zagotovo zna vsak študent matematike urediti tarok karte po velikosti. Kako to naredi? Izbere najmanjšo karto in jo postavi na prvo mesto. Nato izbere drugo najmanjšo karto in jo postavi na drugo mesto. Nato izbere tretjo najmanjšo karto in jo postavi na tretjo mesto. In tako naprej. Temu postopku pravimo urejanje z izbiranjem:
algoritem uredi_z_izbiranjem(a): (*slaba verzija*)
  n = a.length - 1;
  ponavljaj za i od 0 do n:
    j = mesto, na katerem stoji i-ti najmanjši element;
    zamenjaj a[i] in a[j]
Ta algoritem deluje, a smo ga nekoliko nerodno zapisali. Ko premislimo, ugotovimo, da ni tako lahko najti i-tega najmanjšega elementa v tabeli. Lažje pa najdemo najmanjši element, zato algoritem nekoliko predelamo:
algoritem uredi_z_izbiranjem(a):
  n = a.length - 1;
  ponavljaj za i od 0 do n:
    j = mesto, na katerem stoji najmanjši izmed a[i], a[i+1], ..., a[n];
    zamenjaj a[i] in a[j]
Naloga 3
Algoritem prevedemo v Javo:
public static void uredi_z_izbiranjem(int[] a) {
    for (int i = 0; i < a.length; i = i + 1) {
        int j = i;
        for (int k = i; k < a.length; k = k + 1) {
    	    if (a[k] < a[j]) {
    	        j = k;
    	    }
        }
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}
Naloga 4
Zanima nas, kako hitro deluje urejanje z izbiranjem. Koliko časa potrebuje metoda uredi_z_izbiranjem, da uredi tabelo dolžine n? Ali nekatere tabele uredi hitreje kot druge? Ali hitreje uredi tabelo, ki je že urejena, ali tabelo, ki je naključno premešana?
Z odgovori na taka vprašanja se ukvarja veja računalništva, ki se imenuje računska zahtevnost algoritmov. Čas izvajanja metode, se imenuje časovna zahtevnost. Čas je seveda odvisen od velikosti argumentov in argumentov samih.
Časovno zahtevnost lahko dobimo na dva načina: analiziramo metodo in preštejemo, koliko korakov bo opravila, ali pa preprosto izmerimo, koliko časa potrebuje in narišemo graf odvisnosti časa od velikosti tabele.
Meritve je lažje opraviti. Povejo nam, kako se metoda zares obnaša v praksi na pravem računalniku. S teoretično analizo pa predvsem razumemo, zakaj ima metoda dano časovno zahtevnost. Včasih po opravljeni analizi časovne zahtevnosti dobimo idejo, kako je mogoče algoritem izboljšati. Tokrat se posvetimo teoretični analizi časovne zahtevnosti uredi_z_izbiranjem, na vajah po bomo izmerili koliko časa potrebuje metoda.
Metoda uredi_z_izbiranjem je dvojna for zanka. Zunanja zanka šteje s števcem i od 1 do n = a.length - 1, notranja pa s števcem j od i do n. Znotraj notranje zanke se izvedeta največ dve osnovni operaciji (eno primerjanje in eno prirejanje). Ob koncu zunanje zanke se izvedejo tri osnovne operacije (tri prirejanja). To seštejemo:
(n * 2 + 3) + ((n-1) * 2 + 3) + ... + (1 * 2 + 3) =
2 * (n + (n-1) + ... + 2 + 1) + n * 3 =
n * (n + 1) + n * 3 = n * (n + 4) =
n2 + 4 * n
Urejanje z izbiranjem torej potrebuje kvečjemu n2 + 4 * n korakov. Korake smo šteli zelo približno, saj na primer nismo šteli korakov, ki so potrebni za primerjanja v for zanki in povečevanje števcev. Pri ugotavljanju časovne zahtevnosti je običajno, da ne štejemo vsakega najmanjšega koraka. Pravilno pa moramo prešteti, koliko korakov ima vsaka for in while zanka, ter kolikokrat se pokliče kaka metoda.
Časovna odvisnost urejanja z izbiranjem je pravzaprav enaka
C * (n2 + 4 * n)
kjer je C neznana konstana, ki pove koliko osnovnih korakov se zgodi v eni sekundi. To konstanto bi lahko izmerili s poskusi, a je odvisna od računalnika, na katerem poganjamo program. Zato ponavadi namesto neznane konstante C zapišemo časovno odvisnost takole:
O(n2)
To preberom "veliki O n kvadrat" in pomeni, da je časovna odvisnost manjša od n2 krat neka neznana konstanta. Zanemarili smo tudi linearni člen, saj je bistveno manjši od n2.
Naloga 5
Za merjenje časa uporabi razred Stoparca.java:
Stoparca.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.*;

public class Stoparca {
    private long zacetek;

    public Stoparca() {
	zacetek = (new GregorianCalendar()).getTimeInMillis();
    }

    public void start() {
	zacetek = (new GregorianCalendar()).getTimeInMillis();
    }

    public double poglej() {
	long konec = (new GregorianCalendar()).getTimeInMillis();
	return (double)(konec - zacetek)/1000.0;
    }
}
Uporabi jo takole:
Stoparca s = new Stoparca();
...
s.start();
uredi_z_izbiranjem(a);
double cas = s.poglej(); // cas v sekundah
...
Podatke zapiši tako, da jih boš lahko narisal z Mathematico. Predlagam naslednji format zapisa:
{
  { velikost1, cas1 },
  { velikost2, cas2 },
  ...
  { velikostN, casN }
}
Poleg tega, da podatke zapisuješ v datoteko, jih izpisuj še na ekran, da bomo videli, kaj se dogaja. V Mathematici lahko narišeš graf odvisnosti časa od velikosti takole:
podatki = Get["podatki.dat"];
ListPlot[podatki];
Kako bi preizkusil, ali je časovna odvisnost res O(n2)?

Urejanje z vstavljanjem

Urejanje z vstavljanjem bomo spoznali na vajah.
Naloga 6: Urejanje z vstavljanjem