Računalništvo 1 (PRA)

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 uredimo po velikosti 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.)

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 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; } }

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]

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]

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;
    }
}

> java Meritev a b c d

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;
    }
}

Stoparca s = new Stoparca();
...
s.start();
uredi_z_izbiranjem(a);
double cas = s.poglej(); // cas v sekundah
...

{
  { velikost1, cas1 },
  { velikost2, cas2 },
  ...
  { velikostN, casN }
}

podatki = Get["podatki.dat"];
ListPlot[podatki];

Urejanje z vstavljanjem bomo spoznali na vajah.

algoritem uredi_z_vstavljanjem(a):
  n = a.length - 1;
  ponavljaj za i od 1 do n:
     j = i;
     t = a[j]
     ponavljaj dokler je j > 0 in a[j-1] > t:
        a[j] = a[j-1]
        j = j -1
     konec
     a[j] = t
  konec