Alternative Array-Sortierung

[Hawk23]

Hallo zusammen,

Ich bin hier neu im Forum und hoffe, dass ich ein paar Denkanstöße bekomme.

Mit den bisherigen Themen bezüglich Hausaufgaben bin ich sehr gut klargekommen, allerdings habe ich momentan ein kleines Problem. Ich erwarte nicht, dass ich hier Lösungen bekomme sondern ich möchte einfach nicht weiterhin so auf dem Schlauch stehen wie schon den ganzen Tag ???:L

Wir behandeln zur Zeit das Thema der Felder in Java. Ich hab es Theoriemäßig soweit verstanden denke ich. Auch das Implementieren von BubbleSort war nach einiger Zeit klar und hat gut funktioniert.

Nun soll ich ein Array anlegen und zufällig füllen (soweit getan) dann das Array durchlaufen und die kleinste Zahl herausfinden ( auch geschafft ) und sofort ausgeben. Dann die nächst größere ( oder gleiche? ) usw.

Nur bin ich jetzt etwas verwirrt und mir unschlüssig wie ich denn das vernünftig weiterführe bis ich alle Zahlen durch habe.


Ich bedank mich schonmal für eure Hilfe!

 

[nillehammer]

Es gibt in der Java-API die Klasse Arrays (Arrays (Java Platform SE 6)), welche diverse sort-Methoden zur Verfügung stellt. Erstelle eine Kopie Deines Arrays (dafür hat Arrays auch Methoden) und wende auf dieser Kopie die passende sort-Methode an. Falls Du das nicht benutzen darfst, schaue Dir für Denkanstöße den Quellcode dieser Klasse an.

 

[SlaterB]

das unsortierte Array auf diese Weise zu durchlaufen ist in der Tat nicht ganz leicht,
du musst dir den alten Wert merken und wie oft bisher schon ausgegeben (B),

dann beim neuen Durchgang den nächsthöheren Wert finden, also von allen höheren den kleinsten, durch Vergleiche,
sowie noch mitzählen wieviele es vom aktuellen Wert gibt,
wenn es noch mehr aktuelle gibt als bisher ausgegeben, dann wieder diesen und (B) erhöhen, sonst den nächsten Wert

falls nicht so Schritt-orientiert, dann in jeder Runde einen tatsächlich höheren Wert suchen sowie dessen Anzahl und ihn gleich mehrfach ausgeben

-----
viel leichter ist es natürlich, wenn du sortierst, dann der Reihe nach durchgehen

 

[TryToHelp]

Als eine Variante das Array sortieren, zum Beispiel durch dein Bubble Sort ;-)
Ansonsten durch dein Array gehen und nach der Zahl suchen

Also erste Zahl nehmen, und position speichern
durchlaufen und mit der Zahl vergleichen, ist sie kleiner diese nhemen und die position speichern
wenn am ende der Liste, dann diese Zahl ausgeben und an diese position ein marker setzen, bei z.b. nur positiven Zahlen -1
nun das ganze wiederholen bis nur noch diese marker drinnen stehen
fertig

 

[hüteüberhüte]

...
int max = max;
int current = 5;
for (...)
  if (a[i] > current && a[i] < max)
    max = a[i]
sout(max);
current = max;
max = max;
...

insofern da durch steigst. gibt gleiche elemente nur einmal aus.

Edit: Hier etwas ausführlicher:

        Integer[] a = {1, 2, 3, 4};
        List<Integer> l = Arrays.asList(a);
        Collections.shuffle(l);
        l.toArray(a);
        System.out.println("a = " + Arrays.toString(a));

        int current = Integer.MAX_VALUE;
        int previous = Integer.MIN_VALUE;
        for (int j = 0; j < a.length; j++) {
            for (int i = 0; i < a.length; i++) {
                if (a[i] > previous && a[i] < current) {
                    current = a[i];
                }
            }
            System.out.println(current);
            previous = current;
            current = Integer.MAX_VALUE;
        }

        System.out.println("a = " + Arrays.toString(a));

Funktioniert NICHT mit zwei gleichen Elementen (kommt ein Element zweimal vor, wird es nur einmal ausgegeben), Integer.MIN und MAX_VALUE

Sonst wie sonst auch... sortieren oder elemente markieren/entfernen

 

[Hawk23]

Also danke erstmal für die schnellen Antworten!

Ich seh mir das jetzt noch einmal in aller Ruhe an und gebe dann Bescheid, fall etwas unklar ist oder ich weiter Hilfe brauche

 

[Hawk23]

Also es hat jetzt alles hingehauen nachdem ich mich nochmal davorgesetzt habe

Ich habe allerdings bevor ich das Thema schließe noch eine Frage

Lieg ich richtig, dass der Algorithmus deutlich länger braucht sagen wir mal wenn er Zahlen bis 100.000 sortieren muss als zB ein BubbleSort?

 

[TryToHelp]

ich würde sagen, beide sind in O(n²) also eher kleich lang. Außer man verwendet den optimierten Bubblesort, dann müsste dieser schneller sein, vorallem wenn man schon durch Zufall ein sortiertes Array hat ;-) da er dann bei O(n) ist =)

 

[Hawk23]

Also ich hab mal beiden richtig viele Zahlen zugewiesen und hatte den Eindruck, dass der BubbleSort doch um einiges schneller war!

 

[hüteüberhüte]

Nimm Merge- oder QuickSort, die arbeiten in O(n log n). Bubblesort hat wahrscheinlich eine kleinere Konstante als das Finden der Elemente oben. Beide sind aber in O(n^2) und tun sich deshalb in Hinblick auf die asymptotische Laufzeit nichts. Jedenfalls ist das vorherige Sortieren und die anschließende(n) Ausgabe(n) korrekter und schneller.

 

[Hawk23]

Ok!

Dann vielen Dank nochmal für die Hilfe!