ArrayList Elemente verknüpfen

[locolukas]

Hallo Gemeinde,

ich arbeite im Moment spasseshalber an einem Algorithmus der Zahlen in einer ArrayList sortiert.
Mich interessert vor allem wieviele Versuche man braucht und wie man einen Standard Algorithmus möglichst perfomant machen kann ohne auf BubbleSort o.ä. zurückgreifen zu müssen.
In einfacher Form funtioniert das ganze schon, und zwar so:
Die gemischte List wird bottom-up durchlaufen indem einzelen Zahlen verglichen werden bis die höchste Zahl am Ende oben liegt. Diese muss nun nichtmehr verglichen werden und aus der List gelöscht.
Im zweiten Schritt wird die nun oberste Zahl in eine neue List gespeichert und nach und nach mit allen Zahlen der ersten List(die in die zweite wandern) nach ähnlichem Prinzip verglichen, bis diese zweite List nun sortiert ist und ausgegeben werden kann.
Im Schnitt werden etwa 600-700 Vergleiche benötigt.

Der Code sieht so aus:

import java.util.ArrayList;
import java.util.Collections;
//diese Klasse erzeugt eine Anzahl Zahlen, speichert sie in eine ArrayList, mischt sie durch und sortiert sie wieder 
//Version 1.0; September/2011
//
public class Sortierer 
{	
static int zaehler = 0;					//Zählervariable		
	public static void main(String[] args) 
	{
		//erzeuge die beiden ArryLists in denen die Zahlen gespeichert werden
		ArrayList<Integer> stapelEins = new ArrayList<Integer>();
		ArrayList<Integer> stapelZwei = new ArrayList<Integer>();
		//erzeuge 52 Zahlen in die Array List stapelEins
		for(int i=0; i<52; i++)
		{
			stapelEins.add(i);
		}
		System.out.println(stapelEins);
		//Mische die Zahlen
		Collections.shuffle(stapelEins);
		System.out.println(stapelEins);
		
		//diese Schleife sortiert die Liste von unten nach oben durch und ermittelt somit die höchste Zahl
		for(int i=51; i>0; i--)
		{
			if (stapelEins.get(i)>stapelEins.get(i-1))
			{
				Collections.swap(stapelEins, i, i-1);				//swap wechselt die Plätz zweier Zahlen
				zaehler++;
			}
			else
			{
				break;
			}
		}
		//die oberste höchste Zahl wird nun vom Stapel entfernt
		stapelEins.remove(0);	
		//die darauf folgende Zahl wird nun auf den zweiten Stapel gelegt
		stapelZwei.add(stapelEins.get(0));
		//diese Schleife fügt eine Zahl nach der anderen dem zweiten Stapel hinzu, während die zweite
		//Schleife diesen neuen Stapel bottom-up durchsortiert und so jede neue Zahl an die höchstmöglich Position bringt
			for(int i=1; i<51; i++)
			{	
				stapelZwei.add(i, stapelEins.get(i));				//neue Zahl hinzufügen

					for(int j = stapelZwei.size(); j>1; j--)
					{
						
						if(stapelZwei.get(j-1)>stapelZwei.get(j-2))	//vergleich solange Karte eins kleiner als die folgende 
						{
							Collections.swap(stapelZwei, j-1, j-2);	//swap wechselt die Plätz zweier Zahlen
							zaehler++;								//Zähler wird erhöht
							System.out.println(stapelZwei);  	// <--- ermöglicht die Nachvollziehbakeit der Sortiervorgänge
						}
						else
						{
							break;
						}	
					}		
	    	}
			//nun wird die höchste Karte wieder hinzugefügt
			stapelZwei.add(0, 51);	
			//und Stapel wie Zähler ausgegeben 
			System.out.println(stapelZwei);
			System.out.println("insgesamt " + zaehler + " Vergleiche");	
	}	
}

Um die Anzahl der Versuch nun weiter zu reduzieren würde es sich anbieten, wenn man nicht nur qualitative sondern auch quantitative Vergleiche anstellen könnte. Will heissen, dass zwei Zahlen, die sich genau um 1 unterscheiden, bei zukünftigen Vergleichen nichtmehr einzeln verglichen werden müssen sondern nur noch eine diese Paars, Trios, Quartetts etc. verglichen werden muss um eine Aussage treffen zu können.
Leider bietet eine ArrayList keine Standardmethode um das zu implementieren und mir fällt trotz vielem Grübeln keine Lösung für das Problem ein.
Hat jemand ne Idee?

 

[JCODA]

Eine weniger algorithmische sonder objektorientierte Lösung wäre: Du schreibst dir eine Klasse für ein Zahlenpaar:

public class Zahlenpaar{

private int zahl;
private int anzahl;

public Zahlenpaar(int zahl, int anzahl){
this.zahl = zahl;
this.anzahl=anzahl;
}
//getter und setter
}

 

[locolukas]

Danke!
Hatte mir auch schon überlegt das über eine Klasse zu Lösen:
Wenn ich dich richtig verstehe:
Ein Objekt speichert sowohl den Wert Zahl(wird sortiert) als auch den Wert Anzahl(Platz in der Reihenfolge)
ArrayList wird nur zum Mischen und Initialisieren der Variablen verwendet und übergibt dann Wert und Platz an die Objekte.
Oder die Objekte werden mit Math.random mit Werten belegt.
Bleibt aber noch das Problem:

if(objekt1.getZahl - objekt2.getZahl = 1){
   //wie kann hier nun erreicht werden, dass objekt1 beim weiteren sortieren nichtmehr berücksichtigt wird(einfach)
   //aber trotzdem mit objekt2 den Platz in der Reihenfolge verändert(auch möglich)
   //jedoch ohne weiteren objekten in die quere zu kommen, die während des sortierens evt. den
   //Platz hinter objekt2 einnehmen (möglich?)
}

Oder übersehe ich hier was wesentliches?