Java: Generischer Bubblesort Algorithmus #3

Zurück zum letzten Post.
Die drei Lösungen:

  1. Bubblesort abstrakt, abstrakte Methode für Vergleichsfunktion
  2. Comparator.compare, dem Bubblesort im Konstruktor ein Comparator Objekt übergeben.
  3. Comarable.compareTo, die Objekte Comparable mit Methode compareTo implementieren lassen.


1) Das Konzept der Objektorientierung, bietet mit der Vererbung und abstrakten Methoden, die Möglichkeit der dynmaischen Spezialisierung:

Abstraktion gibt mir hier ein allgemeines Lösungsschema, zumal ich eine Methode, mit bestimmter Funktion in der Klasse, nur allgemeingültig deklariere, diese aber zuerst noch in der späteren Spezialisierung, in einer Kind-Klasse, definieren muss.
Die Methode für den Größenvergleich wird ausgelagert, sie muss in der spezialisierten Kind-Klasse für den gewählten Datentyp definiert werden.
Insofern wird der Fehler
The operator > is undefined for the argument type(s) T, T

umgangen, der Datentyp in der Kind-Klasse ist logischerweise kein generischer Datentyp.

Main

public static void main(String[] args) {
    Bubblesort bubblesort = new BubblesortInteger(new ArrayList<Integer>(Arrays.asList(7, 3, 88, 8, 1, 5, 0)));
    ArrayList<Integer> sortedList = bubblesort.sort();

    for (Integer v : sortedList)
        System.out.println(v);
}


Bubblesort

import java.util.ArrayList;

public abstract class Bubblesort<T> {

    protected ArrayList<T> arrayList;
    
    public Bubblesort(ArrayList<T> arrayList){
        this.arrayList = arrayList;
    }
    
    public ArrayList<T> sort() {
        T tmp;
        boolean shifted = true;
    
        while (shifted) {
            shifted = false;
            for (int i = 0; i < arrayList.size() - 1; i++) {
                if (isGreaterThan(arrayList.get(i), arrayList.get(i + 1))) {
                    tmp = arrayList.get(i + 1);
                    arrayList.set(i + 1, arrayList.get(i));
                    arrayList.set(i, tmp);
                    shifted = true;
                }
            }
        }
        return arrayList;
    }
    
    # Abstrakte Methode
    public abstract boolean isGreaterThan(T o1, T o2);
    
}


BubblesortInteger, eine spezialisierte Kind-Klasse, die Listen des Typs Integer verarbeitet.

import java.util.ArrayList;

public class BubblesortInteger extends Bubblesort {

    public BubblesortInteger(ArrayList<Integer> arrayList) {
        super(arrayList);
    }

    #Implementierung der abstrakten Methode
    @Override
    public boolean isGreaterThan(Object o1, Object o2) {
        return((Integer)o1 > (Integer)o2);
    }
    
}



2. Möglichkeit: Ich schmeiß' ein Comparator Objekt rein. Etwas unschön in einer anonymen Klasse, dafür aber schnell, es kann ja bei Bedarf auch eine Child-Klasse definiert werden:

Die Main

public static void main(String[] args) {
    Bubblesort bubblesort = new Bubblesort<Integer>(new ArrayList<Integer>(Arrays.asList(7, 3, 88, 8, 1, 5, 0)), new Comparator<Integer>(){
        public int compare(Integer o1, Integer o2){
            return (o1.compareTo(o2));
        }
    });
    ArrayList<Integer> sortedList = bubblesort.sort();

    for (Integer v : sortedList)
        System.out.println(v);
}


Bubblesort

import java.util.ArrayList;
import java.util.Comparator;

public class Bubblesort<T> {

    protected ArrayList<T> arrayList;
    protected Comparator<T> comparator;
    
    public Bubblesort(ArrayList<T> arrayList, Comparator<T> comparator){
        this.arrayList = arrayList;
        this.comparator = comparator;
    }
    
    public ArrayList<T> sort() {
        T tmp;
        boolean shifted = true;
    
        while (shifted) {
            shifted = false;
            for (int i = 0; i < arrayList.size() - 1; i++) {
                if (comparator.compare(arrayList.get(i), arrayList.get(i + 1)) == 1) {
                    tmp = arrayList.get(i + 1);
                    arrayList.set(i + 1, arrayList.get(i));
                    arrayList.set(i, tmp);
                    shifted = true;
                }
            }
        }
        return arrayList;
    }
}


3) So macht man es richtig:
Wie am Afang schon erwähnt, Bubblesort ist ineffizient.
Ich rate nun zu Shift+Entf im Bezug auf den Sortieralgorithmus, Sortierung gibt es nämlich bereits:

Collections.sort(arraylist)
Collections.reverse(arraylist)
Arrays.sort(array)

Das schöne an Java, sehr viele Bibliotheken, es gibt schon fast alles.
Mit einer Zeile wäre die Aufgabenstellung gelöst, ArrayList<Typ> ist selbst ja schon generisch.
Die große Frage, die noch bleibt, ist, wie das dann mit der Sortierung funktioniert.

Das Objekt muss dafür Comparable implementieren, genauer gesagt, die compareTo Methode.
Damit sehen andere Entwickler an implements Comparable sofort, dass das entsprechende Objekt sortierbar ist.
Beim 2. Beispiel mit dem Comparator sieht man das sehr schön,
public int compare(Integer o1, Integer o2){
    return (o1.compareTo(o2));
}

im Grunde rufe ich dort nur die compareTo Methode der Integer Klasse auf, welche Comparable implementiert.

Alles ganz einfach mit Java 😍

ArrayList<Integer> list = new ArrayList<Integer>(Arrays.asList(7, 3, 88, 8, 1, 5, 0));
Collections.sort(list);

for (Integer v : list)
    System.out.println(v);


Vor Java5, vor der Einführung von Generics, wäre erstens die Typensicherheit dahin, dort könnte man dann mit instanceof prüfen.

PHP-Style 😂, mixed datatype:

ArrayList<Object> list = new ArrayList<Object>(Arrays.<Object>asList(new Integer(7), "3", "88", 8, "888.123", 1.0, 5.4432, 0.12345));
    Bubblesort<Object> bubblesort = new Bubblesort<Object>(list){
        @Override
        public boolean isGreaterThan(Object c1, Object c2) {
            return (Double.valueOf(c1.toString()) > Double.valueOf(c2.toString()));
        }
    };
    
    bubblesort.sort();

    for (Object v : list)
        System.out.println(v);

0.12345
1.0
3
5.4432
7
8
88
888.123


Sobald ein nicht-numerischer String mit dabei ist, java.lang.NumberFormatException. Kaputt.