Frage zu generischen Arrays

[Shizmo]

Hallo, wir sollen Merge-Sort generisch implementieren.

        T[] L = T[n1];
        T[] R = T[n2];
        
        for(int i = 1; i < L.length; i++)
            L[i-1] = a[p+i-1];
        for(int j = 1; j < R.length; j++)
            R[j-1] = a[q+j];
       
        L[n1] = UNENDLICH;
        R[n2] = UNENDLICH;

Also rein theoretisch sollte es so ausschauen, ein T[]-Array namens a wird uebergeben und wird halt immer wieder aufgeteilt, also in L und R, d.h. L und R sollen natuerlich auch generisch sein. Wir duerfen keine Packages verwenden, also auch keine Listen.

So funktioniert es nicht.

Und das unendlich soll ein sehr hoher Wert sein (es geht ums Vergleichen, so dass der Wert immer hoeher wie alle anderen sind), fuer Integer ist das kein Problem, aber wie definiere ich einen sehr hohen generischen Wert?

Vielleicht hat wer eine Idee.
LG

 

[InfectedBytes]

für mergesort brauchst du keinen "unendlich" wert. Mergesort vergleicht immer nur zwei werte.
Um das mit generics zu lösen, brauchst du entweder einen Comparator oder dein generischer Typ muss Comparable implementieren.

 

[Shizmo]

Laut unserem Pseudocode brauch ich einen Wert der zumindest höher ist, als alle anderen Werte im Array.
Problem1 funktioniert so weit, mit ein paar unschoenen Typecasts, das Problem ist nur noch das Unendlich, also ich brauch fuer L[n1] und R[n2] einen hohen Wert, der für alle gilt, für Strings und für Zahlen, wie mach ich das am besten? Mit Integer.MAX_VALUE hab ich einen hohen Zahlenwert, der mir aber nichts fuer Strings bringt zum Vergleichen.

PS: Mein generischer Typ implementiert Comparable, sonst koennte ich ja sowieso nicht vergleichen.

 

[InfectedBytes]

vielleicht hast du den falschen pseudocode erwischt.
Schau dir am besten mal den wikipedia eintrag an: https://de.wikipedia.org/wiki/Mergesort

funktion mergesort(liste);
  falls (Größe von liste <= 1) dann antworte liste
  sonst
     halbiere die liste in linkeListe, rechteListe
     linkeListe = mergesort(linkeListe)
     rechteListe = mergesort(rechteListe)
     antworte merge(linkeListe, rechteListe)

funktion merge(linkeListe, rechteListe);
  neueListe
  solange (linkeListe und rechteListe nicht leer)
  |    falls (erstes Element der linkeListe <= erstes Element der rechteListe)
  |    dann füge erstes Element linkeListe in die neueListe hinten ein und entferne es aus linkeListe
  |    sonst füge erstes Element rechteListe in die neueListe hinten ein und entferne es aus rechteListe
  solange_ende
  solange (linkeListe nicht leer)
  |    füge erstes Element linkeListe in die neueListe hinten ein und entferne es aus linkeListe
  solange_ende
  solange (rechteListe nicht leer)
  |    füge erstes Element rechteListe in die neueListe hinten ein und entferne es aus rechteListe
  solange_ende
  antworte neueListe