Drei eingegebene Zahlen sortieren

knivil schrieb:

Kann man den Code auch verkürzen?

Ja: http://en.wikipedia.org/wiki/Sorting_network . Beim Beispiel fuer 4 Eingaenge den letzten weglassen. Pseudocode:
swap_if(c < a, a, c)
swap_if(b < a, a, b)
swap_if(c < b, c, b)

Wie kann man allgemeiner n Zahlen mit einer minimalen Anzahl von Vergleichen/swaps sortieren? Ich hatte das mal im "Rund um die Programmierung" gefragt und einen template-Code als Antwort bekommen, finde den Thread aber nicht mehr.

dsffsdfds schrieb:

knivil schrieb:
Kann man den Code auch verkürzen?

Ja: http://en.wikipedia.org/wiki/Sorting_network . Beim Beispiel fuer 4 Eingaenge den letzten weglassen. Pseudocode:
swap_if(c < a, a, c)
swap_if(b < a, a, b)
swap_if(c < b, c, b)
Wie kann man allgemeiner n Zahlen mit einer minimalen Anzahl von Vergleichen/swaps sortieren? Ich hatte das mal im "Rund um die Programmierung" gefragt und einen template-Code als Antwort bekommen, finde den Thread aber nicht mehr.

Gefunden: https://www.c-plusplus.net/forum/331825-full

TGGC

dsffsdfds schrieb:

Wie kann man allgemeiner n Zahlen mit einer minimalen Anzahl von Vergleichen/swaps sortieren?

Man kann sie auch ohne Vergleiche sortieren.

Andromeda

TGGC schrieb:

dsffsdfds schrieb:

Wie kann man allgemeiner n Zahlen mit einer minimalen Anzahl von Vergleichen/swaps sortieren?

Man kann sie auch ohne Vergleiche sortieren.

Bogosort, oder wie?

TGGC

Ein Beispiel: mit Bittests. Hoechstwertiges Bit anschauen und gesamtes Set in zwei Haelften teilen mit bit gesetzt oder nicht. Rekursiv fortsetzen mit den Teilmengen mit dem naechstniedrigen Bit.

Ich glaub Anzahl der Vergleiche ist kein gutes Kriterium. Ich kann mir z.B. Vergleiche sparen, indem ich Folgendes ausnuzte: Wenn a < b und b < c dann gilt a < c. Wenn ich alle Vergleichsergebnisse abspeichere und dann statt zu vergleichen vorher versuche das Ergebnis daraus zu folgern, wird der Algorithmus bestimmt nicht schneller, aber er brauche weniger Vergleiche.

Andromeda

TGGC schrieb:

Ein Beispiel: mit Bittests.

Soso, ohne Vergleiche ...

TGGC

Dir ist klar, das man das z.b. so formuliert:

list<int[2];
list[(a >> x) & 1].push_back(a);

Oder sind das auch Vergleich für dich?

Andromeda

TGGC schrieb:

Dir ist klar, das man das z.b. so formuliert:
list<int[2];
list[(a >> x) & 1].push_back(a);

Nö, was macht das?
Wie C-Code sieht das jedenfalls nicht aus.

TGGC

Es nimmt ein bestimmtes Bit als Index in einem Array als Listen. Hier eine allgemeinere Beschreibung https://de.wikipedia.org/wiki/Radixsort

Andromeda

TGGC schrieb:

Es nimmt ein bestimmtes Bit als Index in einem Array als Listen. Hier eine allgemeinere Beschreibung https://de.wikipedia.org/wiki/Radixsort

Danke!
Das ist ein wirklich sehr interessanter Algorithmus.
Und tatsächlich: kein "if" oder sowas. An seine Stelle tritt eben die Berechnung eines Array-Index.

rustyoldguy

Hallo StudentOhneAhnung!

Warum nicht die Werte zuerst in ein Array einlesen und dann sortieren. Dabei kannst du ja auch gleich den Medianwert ermitteln:

// Sortiert ein Array von float-Werten der Größe nach aufsteigend und gibt den Medianwert zurück.
double Sortiere(double (*messwerte)[100], int anzahl)
{
 int slei, sleib;
 int mw, mwr;
 double rewer = 0;

 for (slei = 0; slei < anzahl; slei++)
   for (sleib = slei; sleib < anzahl; sleib++)
    if ((*messwerte)[slei] > (*messwerte)[sleib])
     swap((*messwerte)[slei], (*messwerte)[sleib]);

     mw  = anzahl / 2;
     mwr = anzahl % 2;

 if (mwr != 0)  rewer = (*messwerte)[mw];
  else          rewer = ((*messwerte)[mw - 1] + (*messwerte)[mw]) / 2;

return rewer;
}

Die Sache hat nur einen gewaltigen Hacken:

Wenn du Messwerte hast, mußt du zuerst diese vom Orginal-Array in ein zweites
kopieren. Meistens hat man auch ein mehrdimensionales Array dafür, da
oft das Datum und Uhrzeit der Erfassung, der Name dessen der den Messwert eingetragen hat auch abgespeichert wird. Dazu noch die Daten der Lieferung,
bzw wann und von wen geliefert wurde, die vereinbarte AQL(annehmbare Qualitätslage) und das Prüfniveau, also entweder S-1,S-2,S-3,S-4,I,II,III.
Ebenso die Prüfanweisung, wie etwa

32 - 3/4

die Zum Beispiel sagt das bei dieser Stichprobe 32 Teile kontrolliert werden sollen, 3 fehlerhafte Einheiten sind erlaubt, bei der 4ten erfolgt
die Rückweisung der Lieferung. Aus Losumfang, AQL und vereinbartes Prüfniveau, welche Rückschlüsse auf die Eigenschaften der Grundgesamtheit zulassen, wird dann mit der Binomialverteilung die
Rückweise- bzw Annahmewahrscheinlichkeit errechnet.

Arbeite wenn es geht niemals am Orginal.

Sorry Qualitätsfachmann für Längenprüftechnik WAR (thanks God a lot of that's the past!) mal mein Beruf!

DirkB

@rustyoldguy
Der Thread ist fast drei Jahre alt, ich hoffe dass der Student mittlerweile Ahnung hat.

Warum nicht das Standard qsort ?
Warum die Einschränkung auf 100 Werte?
- Die du auch nicht überprüfst.

rustyoldguy

Bei 100 Werten beginnt die vorläufige Prozeßanalyse.
Zwar sind bei Grundgesamtheiten bis zu 1250 Werte als Stichprobenumfang
möglich, aber normalerweise geht man über einen bestimmten Bereich nicht hinaus,
um die Kosten zu drücken.
Sonst müßte man ja zum Beispiel bei einer Lieferung den gesamten LKW ausräumen um wirklich jedes Teil zu kontrollieren.
Daher ist der cpk-Wert so wichtig.
Als Grenze sieht man 1.33 beim cpk an.
1.33 sind +- 4 sigma bei der Normalverteilung
1.67 sind +- 5 sigma verlangt.
Bei 1,67 sigma sind das erfasste 99.99994 % innerhalb des Gut-Bereichs und ein Fehleranteil von
0,6 ppm, also 0,6 Parts per Million.
Bei 1,33 sind das noch 64 Parts per Million Fehleranteil.

Redet einer davon "Wir produzieren nach six sigma" heißt das,
hier hat man einen Fehleranteil von 2700 ppm. Dann liegen also
etwa 99,73 % innerhalb des Gut-Bereichs.

Zusammenhang von cpk-Wert und sigma:

+-3 sigma sind ein cpk von 1(3/3)
+-4 sigma sind ein cpk vom 1,33 (= 4/3)
+-5 sigma sind ein cpk von 1,67 (= 5/3)
+-6 sigma sind ein cpk von 2 (=6/3)

solche geringen Fehlerquoten sind zum Beispiel bei der Produktion von Medikamenten wichtig!

Man sollte als Mitarbeiter sehr hellhörig werden, wenn ein Kunde
plötzlich den cpk-Wert verlangt und noch dazu die letzten Messprotokolle.
Darüber sind schon einige gestolpert. Man hatte die fehlenden Messprotokolle
einfach nachgeschrieben mit Phantasiewerten.
Das habe ich einmal selbst beobachtet. Bei einem Hersteller für Tauchrohre(Stoßdämpfer-Aussenrohre)aus Edelstshl eines Unterlieferanten einer Zuliefer-Firma einer sehr sehr sehr bekannten deutschen Firma die Sportwagen herstellt......

Ist aber schon mehr als 10 Jahre her und ich war damals noch Facharbeiter.

rustyoldguy schrieb:

[blablabla]

Früher war ich auch ein Facharbeiter,
aber dann habe ich einen Pfeil ins Knie bekommen...

supertux

Wieso einfach wenn es schwieriger geht?

int main(void)
{
    int zahlen[3];

    printf("Geben Sie drei Zahlen an. Diese werden dann sortiert wieder ausgegben.\n"); 

    printf ("Zahl 1:");
    scanf ("%d", zahlen);

    printf ("Zahl 2:");
    scanf ("%d", zahlen + 1); 

    printf ("Zahl 3:");
    scanf ("%d", zahlen + 2); 

    int comp(const void *a, const void *b) 
    {   
        int ia = *((int*) a); 
        int ib = *((int*) b); 

        if(ia < ib) 
            return -1; 

        if(ia == ib) 
            return 0;

        return 1;
    }   

    qsort(&zahlen, sizeof zahlen / sizeof *zahlen, sizeof *zahlen, comp);
    printf ("Die groesste Zahl ist die %d, die zweitgroesste ist die %d und die kleinste Zahl ist die %d.\n",
            zahlen[0], zahlen[1], zahlen[2]);

    return 0;
}

SG1

supertux schrieb:

Wieso einfach wenn es schwieriger geht?

Weil "beliebig viele Zahlen sortieren" ein komplizierteres Problem als "genau 3 Zahlen sortieren" ist.
Weil der Aufruf von qsort() auf dem Wissensstand des OPs vermutlich eben NICHT einfacher ist.

Wutz

Zeile 30 ist UB,
in Zeile 18+19 wird const weggecastet -> Schrott

Andromeda

Die Compare-Funktion lässt sich noch dramatisch verkürzen:

int comp(const void *a, const void *b)
    {
        return *(int*)b - *(int*)a;
    }

SG1

Aber nur, wenn man noch Zusatzinformationen über die zu sortierenden Zahlen hat - ansonsten kann das potentiell underflowen.

Andromeda

SG1 schrieb:

Aber nur, wenn man noch Zusatzinformationen über die zu sortierenden Zahlen hat - ansonsten kann das potentiell underflowen.

Das kapiere ich nicht. Bei welchen Zahlen passiert ein Underflow?