Hallo Leute,
ich hatte vor einiger Zeit in Informatik das Thema Sortieralgorithmen.
Wir Programmieren eigentlich immer nur in Java und meistens mit der Oberfläche BlueJ.
Im Unterricht haben verschieden Algorithmen besprochen, wie den Insertion-Sort, den Bubble-Sort, usw.
Da mir die Laufzeit aber immer etwas zu lang war, dachte ich mir das ich einfach mal einen eigenen Sortieralgorithmus schreibe, der NICHT auf Vertauschungen basiert.
Nachdem das Programm geschrieben war und alle Bugs beseitigt waren, konnte ich stolz einen Algorithmen präsentieren, der positive, ganze Zahlen extrem schnell (25 Mio zufällige Zahlen von 0- 10 Mio werden in weniger als 1 Sekunde sortiert) sortiert, leider nur positive Integers...
Ich hab auch eine Idee wie ich negative sortieren kann, nur wird das mit den Kommazahlen schwer, da ein Array in Java den Index 1,2 nicht besitzt.
Vielleicht kennt sich einer von euch damit etwas besser aus und hat ein par Ideen, hier ist der komplette Quellcode:
/**
* Switch-Sort:
* Ein nicht auf Vertauschungen basierender Algorhytmus der ohne (direkte) Vergleiche und mit nur 3 durchläufen
* einen Array mit belibig vielen Zahlen sortiert.
*/
public class SwitchSort
{
private int pAnzahlZahlen;
private int pZahlengröße;
private int ÜbertragsArray[];
private int StartArray [];
private int merker = 0;
public SwitchSort(int anzahlZahlen, int zahlengröße)
{
pAnzahlZahlen = anzahlZahlen;
pZahlengröße = zahlengröße;
StartArray = new int [pAnzahlZahlen];
for(int i=0; i != pAnzahlZahlen; i++)
{
int p = 0;
p = (int) (Math.random()*pZahlengröße); //Array wird zufällig befüllt
StartArray[i] = p;
}
}
public int größteZahl() //Diese Methode sucht die größte Zahl aus dem Array
{
int merker = StartArray[0];
for(int i=0; i < pAnzahlZahlen; i++)
{
if(StartArray[i] > merker)
{
merker = StartArray[i];
}
}
return merker;
}
public void DoTheMath()
{
int i; //Universal-Variable
merker=this.größteZahl(); //Variable wird mit dem Wert der größten Zahl belegt
i = merker+1;
ÜbertragsArray = new int [i++]; //Hier wird ein Array Declariert, der die größe der größten Zahl hat
int Zähler=0; //Zähler geht die eingelnen Indiezes im StartArray durch
for(int t = StartArray.length-1 ; t >=0 ; t--) //Diese Schleife schreibt eine 1 in den passenden Index, wenn er nicht schon belegt ist, dann ADDIERT er eine 1 an den selben Index im MehrfachArray.
{
if(StartArray[t] >= 0)
{
ÜbertragsArray[StartArray[t]]++;
}
}
for(int t=0;ÜbertragsArray.length != t; t++) //Diese Schleife Setzte die werte aus dem ÜbertragsArray nacheinander in den StartArray zurück, und erhöht dabei immer den Zähler,
{ //der auf den Index im StartArray zeigt, in den geschreiben werden darf. Sollte am selben Index etwas im MehrfachArray stehen,
while(ÜbertragsArray[t] !=0) //wird der selbe Wert immer wieder in den Startarray geschriben (immer eine Stelle weiter) und dabei der MehrfachArray -1 gerechnet,bis dieser den Wert 0 annimmt.
{
StartArray[Zähler] = t;
ÜbertragsArray[t] --;
Zähler++;
}
}
}
}
Wie gesagt das Programm vergleicht keine Zahlen sondern schreibt für eine 5 im ersten Array, eine 1 an den 5. Index im 2. Array (besser gesagt es wird 1 addiert).
Was sagt ihr zum Programm? Lässt sich das so optimieren das ich auch negative und Kommazahlen sortieren kann und weiterhin nach dem selben Prinzip arbeiten kann?
