[Java] ComparisonCountingSort generisch ?!

[KAEPS133]

Hi,

Ich habe eine Frage zu Java bzw. zum schreiben von generischem Code.

Die Aufgabe ist Folgende:

Geben Sie eine Implementierung (des ComparisonCountingSort) als statische generische Methode in Java an. Ihre Funktion soll Arrays
mit beliebigen, aber vergleichbaren Elementen sortieren.

Ich habe also zuerst den CountingSort Algorithmus geschrieben, wie ich bis jetzt immer Code geschrieben habe.

public class ComparisonCountingSort
{
 
        public static void main(String[] args)
        {
                Integer [] arrayToSort = {9, 6, 6, 3, 2, 0, 4, 2, 9, 3};
                System.out.println(Arrays.toString(countingSort(arrayToSort)));
        }
       
        public static int[] countingSort(Integer[] arrayToSort)
        {
                 
                int[] aux = new int[arrayToSort.length];
                 
                // find the smallest and the largest value
                int min = arrayToSort[0];
                int max = arrayToSort[0];
               
                for (int i = 1; i < arrayToSort.length; i++)
                {
                        if (arrayToSort[i] < min) min = arrayToSort[i];
                        else if (arrayToSort[i] > max) max = arrayToSort[i];
                }
                 
                int[] counts = new int[max - min + 1];
                 
                for (int i = 0;  i < arrayToSort.length; i++)
                {
                        counts[arrayToSort[i] - min]++;
                }
                 
                counts[0]--;
                for (int i = 1; i < counts.length; i++)
                {
                        counts[i] = counts[i] + counts[i-1];
                }
                 
                for (int i = arrayToSort.length - 1; i >= 0; i--)
                {
                        aux[counts[arrayToSort[i] - min]--] = arrayToSort[i];
                }
                 
                return aux;
        }
}

Das Funktioniert auch wunderbar. Beim Versuch einen generischen Code zu bauen scheitere ich dann aber. Lied wohl daran das ich es noch nicht 100% Verstanden habe.
Hier ist mal mein generischer Versuch. Wenn mir da jemand bei helfen könnte und das vll auch nochmal für dumme Erklärt, wäre ich unendlich dankbar!

public class ComparisonCountingSortGeneric 
{
	public static void main(String[] args) 
	{
		Integer [] arrayToSort = {9, 6, 6, 3, 2, 0, 4, 2, 9, 3};
		//String result = Arrays.toString(countingSort(arrayToSort));
		//System.out.println(result);
	}
	
	public static <T extends Comparable <T>> int[] countingSort (T[] arrayToSort , integerComperator c)
	{ 
		int[] aux = new int[arrayToSort.length];
		 
		T min = arrayToSort[0];
		T max = arrayToSort[0];
		
		for (int i = 1; i < arrayToSort.length; i++) 
		{
			if (c.compare(arrayToSort[i], min) < 0) min = arrayToSort[i];
			else if (c.compare(arrayToSort[i], max) > 0) max = arrayToSort[i];
		}
		 
		int[] counts = new int[max - min + 1];
		 
		for (int i = 0;  i < arrayToSort.length; i++) 
		{
			counts[arrayToSort[i] - min]++;
		}
		 
		counts[0]--;
		for (int i = 1; i < counts.length; i++) 
		{
			counts[i] = counts[i] + counts[i-1];
		}
		 
		for (int i = arrayToSort.length - 1; i >= 0; i--) 
		{
			aux[counts[arrayToSort[i] - min]--] = arrayToSort[i];
		}
		 
		return aux;
		
	}
	
	public static class integerComperator<T> implements Comparator < T > 
	{
		@Override
		public int compare ( Integer  o1 , Integer  o2 ) 
		{
			if (o1 < o2) return -1;
			else if (o1 > o2) return 1;
			return 0;
		}
	}
}

Ich habe die meisten Probleme lösen können indem ich alles zu (Integer) caste, aber ich glaube das das nicht der Sinn von generischem Code sein soll.

 

[Crysis nerd]

Du kannst einfach überall statt int oder integer T benutzen. Nur musst du Vergleiche ala "a < b" ändern zu "a.compareTo(b)". Dabei auch das im Blick behalten, damit man das richtig abfragt: Comparable (Java Platform SE 6)

Ich hab nicht durch den ganzen Code durchgeguckt, aber T[] arrayToSort als Argument zu nehmen, war doch schon der richtige Anfang.

EDIT:
Der Anfang sollte so aussehen:

public static <T extends Comparable <T>> T[] countingSort (T[] arrayToSort)
	{ 
		T[] aux = new T[arrayToSort.length];
		 
		T min = arrayToSort[0];
		T max = arrayToSort[0];
		
		for (int i = 1; i < arrayToSort.length; i++) 
		{
			if (arrayToSort[i].compareTo(min) < 0) min = arrayToSort[i];
			else if (arrayToSort[i].compareTo(max) > 0) max = arrayToSort[i];
		}

Ich habe jetzt absichtlich auf einen Comperator verzichtet, weil man es auch so machen kann, wenn T eh ein Comparable ist. Du kannst natürlich den comperator auch weiter nutzen, nur dann keinen "IntegerComperator" sondern einen Comparator<T>.


Grüße

 

[KAEPS133]

Wenn ich int[] result = new int[arrayToSort.length] in T[] result = new T[arrayToSort.length] ändere schreit Eclipse "Cannot creat a generic array of T". Lasse ich es so wie es war kann ich weiter unten aber nicht rechnen.

arrayToSort - min -> Das - Zeichen ist nicht definiert für den Typ T, T

Also so ganz alles Austauschen geht dann wohl doch nicht

 

[Crysis nerd]

Wenn ich int[] result = new int[arrayToSort.length] in T[] result = new T[arrayToSort.length] ändere schreit Eclipse "Cannot creat a generic array of T". Lasse ich es so wie es war kann ich weiter unten aber nicht rechnen.

Stimmt, das hatte ich ganz vergessen. Da Generics in Java über Type erasure gemacht wird, ist es ein wenig schwer mit new Speicherplatz zu reservieren, weil es wohl schwer ist zur Laufzeit rauszufinden, wie groß T ist. Mit dem new T[] Problem hab ich mich auch schonmal rumgeschlagen, aber es geht folgendermaßen:

T[] result= (T[]) Array.newInstance(arrayToSort[0].getClass(), arrayToSort.length);

Wenn ich mich hier nicht wieder vertue, sollte das so hinhauen.

arrayToSort - min -> Das - Zeichen ist nicht definiert für den Typ T, T

Also das darf aber auch nicht von dir aus
Der Sortieralgorithmus ist sicher so, dass alles nur per Vergleichen geht. Sonst wäre die Aufgabenstellung doof. Bei Generics soll es ja so sein dass man alle Typen annimmt. Beim Sortieren braucht man aber "spezielle" Typen, nämlich Typen, die die Methode .compareTo implementiert haben. Aber sonst muss man diese Typen wie ein Object behandeln, weil sie sonst nichts können. D.h. du kannst auch nicht subtrahieren oder sonstiges. Aber wie gesagt: Ich bin mir sicher, der Sortieralgorithmus geht auch ohne diese Substraktion.

Also so ganz alles Austauschen geht dann wohl doch nicht

Es muss austauschbar sein. Bei Generic Code ist das halt gerade die Idee dahinter, dass man sich für T jeden Typen denken kann (mit der Einschränkung dass er Comparable implementiert). Und so muss man auch den Code schreiben. Also denk erstmal nichtmehr an Integer oder so

EDIT: Okay bei dem Sortieralgorithmus scheint es wirklich nahe zu liegen, das so zu lösen, wie du das erst vor hattest. Allerdings geht das nun mit Generic Code nichtmehr. Du hast ja quasi ein Array welches einen Counter für alle möglichen Werte in dem Ursprungsarray hat. Das ist aber schon im eigentlichen Denken nicht so toll: Wenn ich deiner Funktion dann ein Array {1,3,6,10000} gebe, erstellt deine Funktion ein Array zum zählen, was 10000 Stellen hat. Nur damit dann dort drin steht {1,0,1,0,0,1,0 .... , 1}.
Vorschlag: Nutz eine HashMap<T, int>
Dort kannst du dann zu jedem vorkommendem T deine Anzahl speichern. Du hast dann außerdem nurnoch so viele Stellen, wie du wirklich brauchst.


Grüße

 

[KAEPS133]

Das mit dem new T[] werde ich mal ausprobieren.
Für das Subtrahieren ist mir aber auch was eingefallen.
Kann ich im Comperator nicht einfach sowas anfügen und das immer Aufrufen?

public int substract (T a, T b)
	{
		Integer c = (Integer)a - (Integer)b;
		return c;
	}

T[] result= (T[]) Array.newInstance(arrayToSort[0], arrayToSort.length); geht leider auch nicht wirklich. newInstance nörget und macht den Vorschlag T[] arrayToSort in Class<?> arrayToSort zu ändern =/

 

[Crysis nerd]

Das mit dem new T[] werde ich mal ausprobieren.
Für das Subtrahieren ist mir aber auch was eingefallen.
Kann ich im Comperator nicht einfach sowas anfügen und das immer Aufrufen?

public int substract (T a, T b)
	{
		Integer c = (Integer)a - (Integer)b;
		return c;
	}

Trenn dich von der Vorstellung, dass es ein Int ist!
Nimm einfach an du kannst T nicht subtrahieren, fertig. Du hast jetzt lediglich die Funktionen, die Comparable hat. Damit musst du auskommen. Kein Substrahieren, kein addieren oder ähnliches. Man soll in deine Funktion auch komplexe Objecte reinwerfen können, die irgendwie vergleichbar sind. Also: Ich will gleich nirgendwo mehr int sehen
Im übrigen: guck dir den Edit in meinem vorherigen Post an.

 

[KAEPS133]

Dann werd ich das irgendwie mal versuchen müssen. Hab jetzt auch mal nach paar Code Beispielen gegoogelt und auf die schnelle keines ohne Subtrahieren gefunden. Dann versuch ich es mal mit ner Hashmap xD

 

[Crysis nerd]

So ich habs jetzt...

import java.lang.reflect.Array;
import java.util.SortedMap;
import java.util.TreeMap;
import java.util.Map;

public class TestC 
{
  public static void main(String[] args) 
  {
    Integer [] arrayToSort = {9, 6, 6, 3, 2, 0, 4, 2, 9, 3};
    Integer[] sorted = TestC.countingSort(arrayToSort);

    for(Integer n : arrayToSort)
    {
      System.out.print(n + ", ");
    }
    System.out.println("");

    for(Integer n : sorted)
    {
      System.out.print(n + ", ");
    }
    System.out.println("");
  }
  

  public static <T extends Comparable <T>> T[] countingSort(T[] arrayToSort)
  { 
    T[] result= (T[]) Array.newInstance(arrayToSort[0].getClass(), arrayToSort.length);
     
    SortedMap<T, Integer> counter = new TreeMap<T, Integer>();

     
     
    for (int i = 0;  i < arrayToSort.length; i++) 
    {
      T key = arrayToSort[i];

      // if map contains a value for key increment it
      // else: set it to one
      if(!counter.containsKey(key))
        counter.put(key, 1);
      else
        counter.put(key, counter.get(key) + 1);
    }
    

    int pos = 0;
    for(Map.Entry tCount : counter.entrySet())
    {
      // insert value n times
      for(int n = 0; n < (Integer)tCount.getValue(); n++, pos++)
      {
        result[pos] = (T)tCount.getKey();
      }
    }
    return result;    
  }
}

Ist irgendwie ein wenig panne, weil das eigentliche sortieren in der SortedMap abläuft.. aber da müsste man wohl dann mal gucken, was die Aufgabe wirklich verlangt.

 

[KAEPS133]

Ok schon mal danke. Das Schau ich mir dann mal genauer an, Ich hab auch nochmal angefangen alles von ganz vorne zu machen, aber bin leider noch nicht ganz so weit

Die gesamte Aufgabenstellung:

Man kann ein Feld sortieren indem man die Elemente nach der Zahl der kleineren Elemente anordnet. Man
zählt dazu für jedes Element die Zahl derer die kleiner sind und ordnet sie dann entsprechend diesem Zähler in
ein sortiertes Feld ein:

[Pseudocode]

1. Ist der Algorithmus korrekt? Wenn nicht, dann korrigieren Sie ihn.
2. Geben Sie eine Implementierung als statische generische Methode in Java an. Ihre Funktion soll Arrays
mit beliebigen, aber vergleichbaren Elementen sortieren.
3. Geben Sie eine zweite Implementierung als statische generische Methode an, die ein Feld von Objekten
beliebiger Art sortiert, deren Ordnung über ein zusätzlich übergebenen Comparator definiert wird.
4. Erstellen Sie passende Unit-Tests für Ihre Implementierung.
5. Geben Sie eine Abschätzung der Laufzeitkomplexität des Algorithmus’ an.

 

[Crysis nerd]

Ich denke, dass es hierbei mehr um das Lernen von Generics geht, als um den eigentlichen Algorithmus. Allerdings, wenn das nutzen der SortedMap nicht gewünscht ist, kann man immer noch eine ganz normale HashMap nutzen, und dann nach dem Zählen jedes Elements einmal ein int[myHashMap.size()] zu erstellen und dort dann alle gezählten Werte in richtiger Reihenfolge eintragen.
Laufzeitkomplexitätsklasse zu bestimmen ist.. mh. Kommt nunmal drauf an, wie man es macht. Das Zählen aller Elemente ist O(n), nachher das zusammensetzen des result Arrays ist auch O(n). Das schwierige ist wohl, wie man die Counter speichert. Wenn man es macht wie du und in O(n) min und max bestimmt und dann ein array komplett von min bis max hat, ist das auch innerhalb von O(n). Allerdings ist der zusätzliche Speicherplatz, der dafür benötigt wird, teilweise schrecklich hoch. Wenn man nur so viel Elemente speichert wie viele unterschiedliche Werte es im Ausgangsarray gibt, muss man irgendwie feststellen, ob es ein Element schon gibt. Das kann, wenn man es dumm anstellt, in o(n^2) liegen, mit einer SortedMap oder einem Tree in O(n log n) und mit einer Hashmap sogar in O(n), solange die Hashmap gute interne Verwaltung betreibt.
Im besten Fall also O(n), meiner Meinung nach.

 

[KAEPS133]

Ich werd heute in der Hochschule mal Nachfragen wie genau das aussehen soll. Wenn ich mehr weiß schreibe ich das hier rein

Edit: Ich habe mal die Lösung als Quelltext angehängt. Vielleicht Kann es ja nochmal jemand gebrauchen.