Sortier Algorythmus

[Alex747]

Hallo erstmal ich bin neu hier
kann mir einer schreiben wie in C++ ein sortier algorythmus funktioniert=?
aber bitte kein quick sort
komm leider nicht drauf
Einfach zum sortieren von Array Elementen

[CarstenJ]

http://www.sortieralgorithmen.de/

[akari]

Hallo

Schau mal hier

bis bald
akari

[LordSash]

//n=anzahl der array einträge
for(i=0;i<n;i++) {
    for(j=0;j<n-i;j++) {
       if(zahl[j] > zahl[j+1]) {
           puffer = zahl[j];
           zahl[j] = zahl[j+1];
           zahl[j+1] = puffer);
       }
    }
}

sowas?

[.filmor]

Oder so?

template <typename IteratorT, typename CompareT>
    IteratorT sort (IteratorT first, IteratorT last, CompareT c)
    {
        while (!impl::is_sorted (first, last, c))
            std::next_permutation (first, last, c);
    }

[Windalf]

[...............]

[doppelmuffe]

[volkard]

statt next_permutation konnte man einfacher random_shufffle nehmen.

[AJ_Styles]

Aber random_shuffle liefert doch auch immer die gleiche Verteilung der Zufallszahlen, oder?

[volkard]

AJ_Styles schrieb:

Aber random_shuffle liefert doch auch immer die gleiche Verteilung der Zufallszahlen, oder?

glaub ich eher nicht. wäre auch ziemlich unintuitiv, sie dann random_shuffle zu nennen.

[templäd]

volkard schrieb:

glaub ich eher nicht. wäre auch ziemlich unintuitiv, sie dann random_shuffle zu nennen.

Der Unterschied ist doch, dass ich bei next_permutation nicht zweimal die gleiche Folge rausbekomme. Leider reichen wohl meine Grundlagen nicht, um die lexikograohische Ordnung von Permutationen zu verstehen... Wäre aber über einen kurzen Tipp dankbar.

http://www.sgi.com/tech/stl/next_permutation.html

[otze]

.filmor schrieb:

Oder so?

template <typename IteratorT, typename CompareT>
    IteratorT sort (IteratorT first, IteratorT last, CompareT c)
    {
        while (!impl::is_sorted (first, last, c))
            std::next_permutation (first, last, c);
    }

hieß der algorithmus nicht shaker sort?

eine glorreiche Laufzeit von O(!n)

[ajax]

Also wenn es Shakersort ist, dann wäre Big O von n quadrat.

[volkard]

otze schrieb:

hieß der algorithmus nicht shaker sort?

nein. shaker-sort ist die variante von bubble-sort, wo die einzelnen läufe immer in abwechselnder richtung geschehen.

dieser alsgo ist unter slow-sort bekannt.

eine glorreiche Laufzeit von O(!n)

O(n!)

[.filmor]

Ne, geht eher in Richtung Bogosort (bei dem allerdings random_shuffle angebrachter wäre ;)). Ich würds unter Brute-Force einordnen. BTW, Best-Case is immerhin $O(n-1)$ (einfacher Test ob es sortiert ist), Worst-Case $O(n \cdot n!) = O(n^2(n-1)!)$ (Test und Permutationen).

SlowSort is aber auch extrem stylisch, zu dessen Implementierung und Laufzeit scheints aber widersprüchliche Daten zu geben.