Oppgave 1
public static <T> void innsettingssortering(T[] a, Comparator<? super T> c) { for (int i = 1; i < a.length; i++) { T temp = a[i]; // flytter a[i] til en hjelpevariabel int j = i-1; // starter med neste tabellposisjon // en og en verdi flyttes inntil rett sortert plass er funnet for (; j >= 0 && c.compare(temp,a[j]) < 0; j--) a[j+1] = a[j]; a[j+1] = temp; // temp legges inn på rett plass } } // innsettingssortering
public static <T> int maks(T[] a, Comparator<? super T> c) { return maks(a, 0, a.length, c); // kaller metoden under } public static <T> int maks(T[] a, int fra, int til, Comparator<? super T> c) { fratilKontroll(a.length,fra,til); if (fra == til) throw new NoSuchElementException ("fra(" + fra + ") = til(" + til + ") - tomt tabellintervall!"); int m = fra; // indeks til største verdi T maksverdi = a[fra]; // største verdi for (int i = fra + 1; i < til; i++) // går gjennom intervallet { if (c.compare(a[i],maksverdi) > 0) // bruker komparatoren { maksverdi = a[i]; // største verdi oppdateres m = i; // indeks til største verdi oppdateres } } return m; // posisjonen til største verdi } // maks
Oppgave 2 a)
Utvalgssortering er kodet vha. metodene min() og bytt(). Det betyr at vi må lage en komparator-versjon av
min() og en generisk versjon av bytt():
public static <T> void bytt(T[] a, int i, int j) { T temp = a[i]; a[i] = a[j]; a[j] = temp; } public static <T> int min(T[] a, int fra, int til, Comparator<? super T> c) { if (fra < 0 || til > a.length || fra >= til) throw new IllegalArgumentException("Illegalt intervall!"); int m = fra; // indeks til minste verdi i a[fra:til> T minverdi = a[fra]; // minste verdi i a[fra:til> for (int i = fra + 1; i < til; i++) if (c.compare(a[i], minverdi) < 0) { m = i; // indeks til minste verdi oppdateres minverdi = a[m]; // minste verdi oppdateres } return m; // posisjonen til minste verdi i a[fra:til> } public static <T> int min(T[] a, Comparator<? super T> c) // bruker hele tabellen { return min(a,0,a.length,c); // kaller metoden over } public static <T> void utvalgssortering(T[] a, Comparator<? super T> c) { for (int i = 0; i < a.length - 1; i++) bytt(a, i, min(a, i, a.length, c)); // to hjelpemetoder }
Oppgave 2 b)
public static <T> int binærsøk(T[] a, int fra, int til, T verdi, Comparator<? super T> c) { Tabell.fratilKontroll(a.length,fra,til); // se Programkode 1.2.3 a) int v = fra, h = til - 1; // v og h er intervallets endepunkter while (v <= h) // fortsetter så lenge som a[v:h] ikke er tom { int m = (v + h)/2; // heltallsdivisjon - finner midten T midtverdi = a[m]; // hjelpevariabel for midtverdien int cmp = c.compare(verdi, midtverdi); if (cmp > 0) v = m + 1; // verdi i a[m+1:h] else if (cmp < 0) h = m - 1; // verdi i a[v:m-1] else return m; // funnet } return -(v + 1); // ikke funnet, v er relativt innsettingspunkt } public static <T> int binærsøk(T[] a, T verdi, Comparator<? super T> c) { return binærsøk(a,0,a.length,verdi,c); // bruker metoden over }
Oppgave 2 c)
public static <T> int parter(T[] a, int v, int h, T skilleverdi, Comparator<? super T> c) { while (v <= h && c.compare(a[v],skilleverdi) < 0) v++; while (v <= h && c.compare(skilleverdi,a[h]) <= 0) h--; while (true) { if (v < h) Tabell.bytt(a,v++,h--); else return v; while (c.compare(a[v],skilleverdi) < 0) v++; while (c.compare(skilleverdi,a[h]) <= 0) h--; } } public static <T> int parter(T[] a, T skilleverdi, Comparator<? super T> c) { return parter(a,0,a.length-1,skilleverdi,c); // kaller metoden over } public static <T> int sParter(T[] a, int v, int h, int k, Comparator<? super T> c) { if (v < 0 || h >= a.length || k < v || k > h) throw new IllegalArgumentException("Ulovlig parameterverdi"); bytt(a,k,h); // bytter - skilleverdien a[k] legges bakerst int p = parter(a,v,h-1,a[h],c); // partisjonerer a[v:h-1] bytt(a,p,h); // bytter for å få skilleverdien på rett plass return p; // returnerer posisjonen til skilleverdien } public static <T> int sParter(T[] a, int k, Comparator<? super T> c) // bruker hele tabellen { return sParter(a,0,a.length-1,k,c); // v = 0 og h = a.lenght-1 } private static <T> void kvikksortering(T[] a, int v, int h, Comparator<? super T> c) { if (v >= h) return; // hvis v = h er a[v:h] allerede sortert int p = sParter(a,v,h,(v + h)/2,c); kvikksortering(a,v,p-1,c); kvikksortering(a,p+1,h,c); } public static <T> void kvikksortering(T[] a, Comparator<? super T> c) // sorterer hele tabellen { kvikksortering(a,0,a.length-1,c); }
Oppgave 2 d)
private static <T> void flett(T[] a, T[] b, int fra, int m, int til, Comparator<? super T> c) { int n = m - fra; // antall elementer i a[fra:m> System.arraycopy(a,fra,b,0,n); // kopierer a[fra:m> over i b[0:n> int i = 0, j = m, k = fra; // løkkevariabler og indekser while (i < n && j < til) // fletter b[0:n> og a[m:til>, legger a[k++] = c.compare(b[i],a[j]) <= 0 ? b[i++] : a[j++]; // resultatet i a[fra:til> while (i < n) a[k++] = b[i++]; // tar med resten av b[0:n> } public static <T> void flettesortering(T[] a, T[] b, int fra, int til, Comparator<? super T> c) { if (til - fra <= 1) return; // a[fra:til> har maks ett element int m = (fra + til)/2; // midt mellom fra og til flettesortering(a,b,fra,m,c); // sorterer a[fra:m> flettesortering(a,b,m,til,c); // sorterer a[m:til> flett(a,b,fra,m,til,c); // fletter a[fra:m> og a[m:til> } public static <T> void flettesortering(T[] a, Comparator<? super T> c) { T[] b = Arrays.copyOf(a, a.length/2); flettesortering(a,b,0,a.length,c); // kaller metoden over }
Oppgave 3 b)
Tabell.innsettingssortering(punkt, (p1, p2) -> { int d = p1.x - p2.x; // forskjellen mellom x-koordinatene if (d != 0) return d; return p1.y - p2.y; // forskjellen mellom x-koordinatene } );
Oppgave 3 c)
Tabell.innsettingssortering(punkt, Comparator.comparing((Point p) -> p.x).thenComparing(p -> p.y));
og
Tabell.innsettingssortering(punkt, Comparator.comparingInt((Point p) -> p.x).thenComparingInt(p -> p.y));
Oppgave 3 d)
Hvis vi bruker koden under, får vi en feilmelding. Kompilatoren klarer ikke avgjøre hva som er typen til variabelenp. Det løses ved å ha (Point p) -> p.x.
Tabell.innsettingssortering(punkt, Comparator.comparing(p -> p.x).thenComparing(p -> p.y));
Oppgave 3 e)
Tabell.innsettingssortering(punkt, Comparator.comparingDouble(Point::getX).thenComparingDouble(Point::getY));
Oppgave 3 f)
Tabell.innsettingssortering(punkt, (p1,p2) -> { int d = (p1.x*p1.x + p1.y*p1.y) - (p2.x*p2.x + p2.y*p2.y); if (d != 0) return d; else return p1.y - p2.y; } );
Oppgave 3 g)
Tabell.innsettingssortering(punkt, (p1,p2) -> { int d = p2.x*p1.y - p1.x*p2.y; if (d != 0) return d; if (p1.x != 0) return p1.x - p2.x; if (p1.y != 0) return p1.y - p2.y; // nå må p1 == (0,0) if (p2.x == 0 && p2.y == 0) return 0; // p1 == p2 == (0,0) return -1; // p1 == (0,0) og p2 != (0,0) gir p1 mindre enn p2 } );
Oppgave 4 b)
Tabell.innsettingssortering(d, Comparator.naturalOrder());
Oppgave 4 d, e, f
public class Dato implements Comparable<Dato> { private final int dag, mnd, år; // instansvariabler // Verdiene bør testes. F.eks. kan ikke dag være mindre // enn 1 eller større en 31, 31. april finnes ikke, osv. public Dato(int dag, int mnd, int år) // konstruktør { this.dag = dag; this.mnd = mnd; this.år = år; } public Dato(int dag, Måned måned, int år) // konstruktør { this.dag = dag; mnd = måned.mndnr(); this.år = år; } @Override public int compareTo(Dato d) // compareTo { if (år < d.år) return -1; else if (år > d.år) return 1; else if (mnd < d.mnd) return -1; else if (mnd > d.mnd) return 1; else return dag - d.dag; } @Override public boolean equals(Object o) // equals { if (o == this) return true; if (!(o instanceof Dato)) return false; Dato d = (Dato)o; return år == d.år && mnd == d.mnd && dag == d.dag; } public boolean equals(Dato d) // equals { return år == d.år && mnd == d.mnd && dag == d.dag; } @Override public int hashCode() // laget av Netbeans { int hash = 3; hash = 89 * hash + dag; hash = 89 * hash + mnd; hash = 89 * hash + år; return hash; } @Override public String toString() // toString { StringBuilder s = new StringBuilder(); s.append(dag).append('.').append(' '). append(Måned.toString(mnd)).append(' ').append(år); return s.toString(); } } // class Dato
Oppgave 5
public class Klokkeslett implements Comparable<Klokkeslett> { private int timer,minutter; // klokkeslett på formen 12:21, 00:00, 09:09 osv. public Klokkeslett(String klokkeslett) { if (klokkeslett.length() != 5 || klokkeslett.charAt(2) != ':') throw new IllegalArgumentException("Klokkeslett må ha formen tt:mm"); timer = Integer.parseInt(klokkeslett.substring(0,2)); if (timer < 0 || timer > 23) throw new IllegalArgumentException ("Timetallet " + timer + " er ulovlig!"); minutter = Integer.parseInt(klokkeslett.substring(3)); if (minutter < 0 || minutter > 59) throw new IllegalArgumentException ("Minutt-tallet " + minutter + " er ulovlig!"); } @Override public int compareTo(Klokkeslett k) { if (timer < k.timer) return -1; else if (timer > k.timer) return 1; else return minutter - k.minutter; } @Override public boolean equals(Object o) { if (o == this) return true; if (!(o instanceof Klokkeslett)) return false; Klokkeslett k = (Klokkeslett)o; return timer == k.timer && minutter == k.minutter; } public boolean equals(Klokkeslett k) { return timer == k.timer && minutter == k.minutter; } @Override public int hashCode() // generert av NetBeans { int hash = 7; hash = 29 * hash + this.timer; hash = 29 * hash + this.minutter; return hash; } @Override public String toString() { StringBuilder s = new StringBuilder(); if (timer < 10) s.append('0'); s.append(timer); s.append(':'); if (minutter < 10) s.append('0'); s.append(minutter); return s.toString(); } } // class Klokkeslett // Programeksempel: Klokkeslett[] k = new Klokkeslett[5]; k[0] = new Klokkeslett("23:56"); k[1] = new Klokkeslett("09:09"); k[2] = new Klokkeslett("07:00"); k[3] = new Klokkeslett("00:00"); k[4] = new Klokkeslett("19:01"); Tabell.innsettingssortering(k); for (Klokkeslett x : k) System.out.print(x + " "); // Utskrift: 00:00 07:00 09:09 22:56 23:59
Oppgave 6
public class Tid implements Comparable<Tid> { private Dato dato; private Klokkeslett klokkeslett; public Tid(int dag, int mnd, int år, String klokkeslett) { dato = new Dato(dag,mnd,år); this.klokkeslett = new Klokkeslett(klokkeslett); } public Tid(Dato dato, Klokkeslett klokkeslett) { this.dato = dato; this.klokkeslett = klokkeslett; } @Override public int compareTo(Tid tid) { int cmp = dato.compareTo(tid.dato); if (cmp != 0) return cmp; return klokkeslett.compareTo(tid.klokkeslett); } @Override public boolean equals(Object o) // equals { if (o == this) return true; if (!(o instanceof Tid)) return false; return equals((Tid)o); } public boolean equals(Tid tid) // equals { return klokkeslett.equals(tid.klokkeslett) && dato.equals(tid.dato); } @Override public int hashCode() { int hash = 7; hash = 97 * hash + dato.hashCode(); hash = 97 * hash + klokkeslett.hashCode(); return hash; } @Override public String toString() { return dato + " kl. " + klokkeslett; } } // Tid // Testprogram Tid[] tider = new Tid[4]; tider[0] = new Tid(24,12,2014,"15:30"); tider[1] = new Tid(24,12,2014,"12:00"); tider[2] = new Tid(23,12,2014,"12:00"); tider[3] = new Tid(23,12,2014,"09:00"); Tabell.innsettingssortering(tider); for (Tid tid : tider) System.out.println(tid);