sortering af objekter i et array

Jeg havde noget liggende der ligner:

import java.util.*;

class By {

  private String by;
  private int indbyggere;

  public By(String by, int indbyggere) {
    this.by=by;
    this.indbyggere=indbyggere;
  }

  public int getIndbyggere() {
    return indbyggere;
  }

  public String toString() {
    return by+\" \"+indbyggere;
  }

  public static class ByComparator1 implements java.util.Comparator  {
    public int compare(Object o1,Object o2) {
      return ((By)o1).getIndbyggere()-((By)o2).getIndbyggere();
    }
  };

  public static class ByComparator2 implements java.util.Comparator  {
    public int compare(Object o1,Object o2) {
      return ((By)o2).getIndbyggere()-((By)o1).getIndbyggere();
    }
  };

    public static void main(String[] args)
    {
        By mitArray[] = new By[10];

        mitArray[0] = new By(\"Horsens\",55000);
        mitArray[1] = new By(\"Randers\",75000);
        mitArray[2] = new By(\"Enslev\",20);
        mitArray[3] = new By(\"Århus\",255000);
        mitArray[4] = new By(\"København\",10000);
        mitArray[5] = new By(\"Odense\",195000);
        mitArray[6] = new By(\"Vejle\",45000);
        mitArray[7] = new By(\"Esbjerg\",80000);
        mitArray[8] = new By(\"Grenå\",35000);
        mitArray[9] = new By(\"Peoria\",355000);

        for (int i=0;i<10;i++) {
          System.out.println(mitArray[i]);
        }
 
        System.out.println(\"------\");

        Arrays.sort(mitArray,new ByComparator1());

        for (int i=0;i<10;i++) {
          System.out.println(mitArray[i]);
        }
 
        System.out.println(\"------\");
       
        Arrays.sort(mitArray,new ByComparator2());

        for (int i=0;i<10;i++) {
          System.out.println(mitArray[i]);
        }
 
    }
}

Du må gerne uddybe lidt mere, det er ikke klart hvad du har foran dig. Er der kun et array? I så fald hvilke elementer ligger idet, det må være en klasse af en eller anden art idet du taler om både en String og en int?

ja jeg har en klasse by
class By {

String navn;
int indbygere;

osv. osv.
}

så har jeg en klasse

class Landsdel {
String navn;

By [] landsbyer = new By[3];

}
og sidst min main klasse
class Land {

public static void main(String[] args) {
By aalborg = new By ();
By aarhus = new By ();
By horsens = new By();
Landsdel jylland = new Landsdel();

jylland.landsbyer[0] = aalborg;
jylland.landsbyer[1] = aarhus;
jylland.landsbyer[2] = horsens;
}
så har jeg selvfølgelig nogle metoder osv. til at ændre antal indbyggere i en by - men jeg vil så gerne have sorteret det array landsbyer jeg har lavet udfra hvem der har flest indbyggere.

kan det ikke lade sig gøre på den måde det er delt op på her eller ???

Kan du ikke bruge det jeg har lavet? Du skal bare gøre det på
dine landsbyer i stedet for.

jeg prøver lige og ser om jeg kan få det til at virke

class By {

    String navn;
    int indbygere;

    public By(String navn, int indb) {
        this.navn = navn;
        indbygere = indb;
    }

    public String toString() {
        return( navn + \": \" + indbygere );
    }

    public int compareTo(By by) {
        return( indbygere - by.indbygere );
    }
}

class Land {

    public static void main(String[] args) {
        By aarhus = new By (\"Aarhus\", 500000);
        By horsens = new By(\"Horsens\", 50000);
        By aalborg = new By (\"Aalborg\", 200000);
        By soenderborg = new By (\"Sønderborg\", 30000);
        Landsdel jylland = new Landsdel();

        jylland.landsbyer[0] = aalborg;
        jylland.landsbyer[1] = aarhus;
        jylland.landsbyer[2] = horsens;
        jylland.landsbyer[3] = soenderborg;
        jylland.sort();
        System.out.println( jylland.landsbyer[0] );
        System.out.println( jylland.landsbyer[1] );
        System.out.println( jylland.landsbyer[2] );
        System.out.println( jylland.landsbyer[3] );
    }
}

class Landsdel {
    String navn;

    By [] landsbyer = new By[4];

    public void sort() {
        int maxIndex = landsbyer.length - 1;
        while (maxIndex >= 0) {
            for ( int i = 0 ; i < maxIndex ; i++ ) {
                if ((landsbyer[i].compareTo(landsbyer[i +1]) > 0)){
                    By temp = landsbyer[i];
                    landsbyer[i] = landsbyer[i + 1];
                    landsbyer[i + 1] = temp;
                }
            }
            maxIndex--;
        }
    }
}

Sorteringsrutinen er simpel, men den kan jo ændres til noget smartere.

Hvorfor lave sin egen sortering, når Java har en indbygget der er
langt bedre?

Fordi det er nemmere at forstå, hvad der foregår.
Personligt ville jeg som nybegynder ikke have fattet en lyd af hvad der foregår i dit eksempel.
Desuden er jeg tilhænger af at lægge metoder, der arbejder på instansvariable i den klasse, hvor variablerne er. Det er mig bekendt et af formålene med objektorienteret programmering at gøre hver klasse og helst også hvert objekt ansvarlig for behandlingen af egne variable.
Hvad effektiv sortering angår, så er det relativt nemt at implementere en quicksort, og da der bliver færre parameteroverførsler, vil sorteringen formentlig i så fald blive mere effektiv end javas egen.

Ok, der er programmering, og så er der Javas måde at gøre det på. Jeg synes nu
nok man bør overveje at lære at gøre det på Javas måde, når man nu gør det
i Java. Og kan man ikke forstå mit eksempel, kan man jo spørge :)

Og bevis lige, at du kan lave en sortering, der er hurtigere end Javas.

class Landsdel {
    String navn;

    By [] landsbyer = new By[500000];

    public void sort() {
        qsort(landsbyer, 0, landsbyer.length-1);
    }
   
    private static void qsort ( By[] tabel , int l , int r )
  {
    int i = l;
    int j = r;
    By x = (tabel [( l + r ) /2]);
    By y;
    do
    {
        while ( tabel[i].compareTo(x) < 0) {
            i++;
        }
      while( tabel[j].compareTo(x) > 0) {
          j--;
      }
        if ( i<=j)
        {
            y=tabel[i];
        tabel[i]=tabel[j];
          tabel[j]=y;
        i++;
        j--;
          }
      }while ( j>=i);
      if (l<j)
    {
        qsort(tabel,l,j);
    }
    if (i<r)
    {
        qsort(tabel,i,r );
    }
     
  }
}

Tidsforbrug til sortering Af 500.000 random objekter: ca. 1 sek.

Hvis jeg sætter 500.000 random objekter ind i dit eksempel tager 1. sortering mellem 1,1 og 1,2 sek. og 2. sortering mellem 1,4 og 1,5 sek.

Er det bevis nok??

Er din sortering også stabil, som Javas er?

Du kan jo prøve selv :-)

Greybeard>> Du bevæger dig ud på gyngende grund, både hvad angår objektorientering og javas sort metode.

Mht. sort, så er det en generel ting, som kan ske på alle objekter, og tilhører derfor ingen generelt.

Du skriver en nydelig quicksort, og påstår at det er den bedste.
Lad mig sige det sådan, at den bedste sorteringsalgoritme er den, som gør arbejdet bedst med det datagrundlag, man har, og der kan du ikke altid forudsætte, at quicksort er hurtigtst. Der er faktisk situationer, med 500.000 objekter, hvor en modificeret bubble-sort er bedst.

Nok om det. Arrays.sort, som sorterer objekter anvender insertionsort og mergesort som bagvedliggende algoritmer, og er endda en \"tunet\" mergesort.
Mergesort = nlog(n)
quicksort = (næsten) nlog(n).


erikjacobsen>> Lad dog være med at kalde comparatorerne ByComparator1 og ByComparator2. Tænk på at nogle skal kunne forstå det. Hvad med at kalde den ByComparatorAscending og ByComparatorDescending?

Logical>> Jeg påstod faktisk ikke at det var den bedste, kun at en fornuftig sorteringsalgoritme, placeret det rigtige sted, formentlig ville være ligeså hurtig eller hurtigere end at bruge indbyggede Javarutiner, som typisk kræver mange procedurekald. I tilfældet med byer i en landsdel er det temmelig ligegyldigt, hvilken rutine der bruges. Der er næppe byer nok til at forskellen kan måles.

Hvis vi endelig skal diskutere sortering, så skal det lige med at mergesort har det handicap at den kræver en kopi af array\'et, med deraf følgende ekstra arbejde og memoryforbrug.

Sjovt nok så havner vi her i en diskussion om sorteringsalgoritmer, og hvilke algoritmer Java bruger. Men hvis alle skal starte med at bruge Javas indbyggede sortering, så er der snart ikke flere tilbage, der ved hvad en sorteringsalgoritme er. Da man stadig bruger tid på uddannelsesinstitutionerne på at lære bl.a. sorteringsalgoritmer, må der være nogen der er enige med mig i at det ikke er en heldig udvikling.

Problemet med Eriks eksempel er at strukturen ikke er nem at overskue, og vi skal alle begynde et sted. Et godt sted at begynde er efter min mening med noget, hvor man kan forstå, hvordan det virker.

Huha det var ellers en del svar der var kommet her natten over - men jeg prøver at ser hvad jeg kan få mest ud af - jeg kan ikke lige snakke med om hvad der er mest effektivt osv. når det kommer til sortering af objekter - så jeg går bare efter den der er mest effektiv for mig :)
Ormholt

ormholt >> Det er efter min mening en fornuftig holdning :-)

Jeg ved da heller ikke om der er nogen der behøver at kende til sorteringsalgoritmer
længere. Der er så meget andet vi heller ikke behøver at kende til.

Hov hov ... For det første er Arrays.sort() en tunet QuickSort, ikke MergeSort - men Arrays.sort() virker ikke på den måde at den er rigtig langsom hvis objekterne allerede er sorteret, ligesom Greybeard\'s quicksort formentlig ville.

Desuden har jeg for nylig sammenlignet standard QuickSort, BubbleSort, InsertionSort, SelectionSort og MergeSort med Arrays.sort. Jeg fandt ud af at I alle tilfælde er Arrays.sort mellem 2 og 4 gange hurtigere end sin nærmeste konkurrent, som er enten QuickSort eller MergeSort.

Big-O på både MergeSort, QuickSort og Arrays.sort er n*log(n) men fordi Arrays.sort er realiseret genialt, er den så mange gange hurtigere. Tag selv et kig i Arrays ... man må godt :-)

Beklager, men denne implementattion af Quicksort er hurtigere, hvis elementerne er sorteret i forvejen.
Iøvrigt er der i mange teoretiske studier af sorteringalgoritmers tidskompleksitet, det problem at der ikke tages højde for det overhead, der kommer i form af kontrolstrukturer.
Der findes utroligt mange eksempler på klodset strukturerede sorteringalgoritmer i lærebøger.
Jeg løb for nylig ind i en såkaldt Quicksort, hvor kompleksiteten nærmede sig n^2, hvis der var mange ens elementer.

Set fra min synsvinkel er det afgørende for en algoritme, hvor hurtigt den performer i realtime, indenfor det elementinterval den skal anvendes på.

Her spiller sådan noget som metodekald også en rolle, i og med at de indebærer et kraftigt overhead.

Selvfølgelig bliver det afgørende, hvor tæt man kan komme på n*log(n), hvis datamængden er stor nok, men hvor tit er den det.
Samtidigt bliver også overheadet vigtigt ved store datamængder.

Hummm. Det her ligner mere en diskutionsklub for sortering end en lønsning på ormholt's problem.

Problemet er vel ikke så stort :-)

Du skal implemtere

public class By implements Comparable
  .
  .
  .
  public int compareTo(Object a)
  {
    if (this.indbyggere < ((By)(a)).indbyggere)
      return -1;
    else
    if this.indbyggere == ((By)(a)).indbyggere)
      return 0;
    else
      return 1;
  }

Det der er vigtig er "implements Comparable" som fortæller at objekterne er sammenlignelige. Og af metoden compareTo er implementeret.

Her efter kan du bruge funktionen Arrays.sort(mitArray); fra java.util.*
Vær opmærksom op NullPointerReference i ikke initialiserede tabelelementer.

Og så kan du jo tage tabellen bagfra bagefter....

P.s.
Jeg er ikke en ørn til java faktisk er jeg nybegynder, men jeg har arbejdet med programmering i snar 20 år, og min erfaring siger af indbyggede funktioner i langt de fleste tilfælde er bedst - ikke kun hastighed men de skal IKKE veligeholdes... ( Evt svar på denne PS kommenteres ikke...)