Bogosort (ohne Methoden, nur Main Funktion)

S

Sekiro24

Mitglied
Hallo Community.
Ich stehe vor einer Aufgabe und weiss nicht ganz wie ich das realisieren soll.
Ich soll den Bogosort Allgorithmus programmieren ohne zusätzliche Funktionen zu benutzen.
Ich habe mir bereits Gedanken gemacht.
Also das Array hat 8 Felder bzw. 8 Elemente, diese sind vom Typ Int.
Die Elemente der Felder sind -1,0,-25,100,6,-3,-2,25.
Jetzt habe ich mir das so vorgestellt, dass ich zuerst eine For-Schleife schreibe, die von i = 1 mit der Bedingung i <= 8 bei i++ das Array durchläuft.
In der For-Schleife ist dann eine If Anweisung, die dann guckt ob das Element an der Stelle i größer ist als an der Stelle i + 1.
Falls das der Fall ist soll dann an der Zuffälligen Stelle r = rand() % 8 , die Elemente des Feldes an der Stelle r mit dem der Stelle i tauschen.

Also wie folgt.
C: 
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>

main()
{
        
        int unsortiert[] = {-1,0,-25,100,6,-3,-2,25};
        int temp, r, r;
        printf("unsortiertes Array:\n");
        printf("---------------------\n");
        for(i = 1; i <= sizeof(unsortiert)/sizeof(int); i++){
            printf("%d. %d\n", i ,unsortiert[i-1]);
        }
        /* Vertauschung und Abfrage soll hier passieren.
        srand(time(NULL));
        for(j = 1; j <= 8; j++){
            if(unsortiert[j-1] > unsortiert[j]){
                temp = unsortiert[j];
                r = rand()%8;
                unsortiert[j] = unsortiert[r];
                unsortiert[r] = temp;
            }       
        }
        */

}
Die Frage ist, wie kann ich das so schreiben, dass zuerst die Vertauschung kommt und dann die Abfrage ob die Elemente des Arrays an der i-ten Stelle kleiner ist als die i+1 Stelle. Daraufhin sollen alle Stellen auch die unsortierten Stellen nach der Vertauschung ausgegeben werden. Sobald das Array sortiert wurde, soll das Array ein letztes mal ausgegeben werden.
Ich hoffe das ich das Problem so gut wie möglich darstellen konnte.

freundliche Grüße :)
 
Hi

Sekiro24 hat gesagt.:
In der For-Schleife ist dann eine If Anweisung, die dann guckt ob das Element an der Stelle i größer ist als an der Stelle i + 1.
Falls das der Fall ist soll dann an der Zuffälligen Stelle r = rand() % 8 , die Elemente des Feldes an der Stelle r mit dem der Stelle i tauschen.
Zum Vergrößern anklicken....
Dein jetziger Code beendet nach höchstens 8 Iterationen und du hast einen out-of-bounds-Access bei j = 8.
Sekiro24 hat gesagt.:
Die Frage ist, wie kann ich das so schreiben, dass zuerst die Vertauschung kommt und dann die Abfrage ob die Elemente des Arrays an der i-ten Stelle kleiner ist als die i+1 Stelle.
Zum Vergrößern anklicken....
Rein objektiv gesehen bringt das nichts - aber du kannst die Randomisierung ja einfach vor die if-Bedingung schreiben?

ich sehe in deinem Code einige Probleme.
1. Das ist kein Bogosort. Du vertauschst immer nur mit der ersten nicht-sortierten Stelle - damit bist du schon ein ziemliches bisschen schneller als Bogosort, welches irgendwelche Stellen vertauscht
2. Der schon angesprochene OOB-Access bei j=8 auf unsortiert.
3. Der schon angesprochene äussere Loop, der zu früh beendet.
4. In C (und allen anständigen Programmiersprachen ;) ) ist das erste Element 0. Daher iteriert man normalerweise von i=0 bis i < size.
5. Deine Variablen i und j sind nicht deklariert. Dafür 2x r? Und bitte kein C89 mehr - wir schreiben for-loops modern (aka C99 - auch schon 20 Jahre alt...):
C: 
for(int i = ...)
(Es gibt noch ewiggestrige Lehrer und Professoren, die das so wollen - aber sofern nicht klar C89 vorgeschrieben ist, ist C99 sehr viel einfacher zu lesen und verstehen).


Als Blaupause für Bogosort dient Wikipedia recht gut: Bogosort – Wikipedia
Das solltest du recht leicht in C übersetzen können.

Gruss
cwriter
 
cwriter hat gesagt.:
Hi


Dein jetziger Code beendet nach höchstens 8 Iterationen und du hast einen out-of-bounds-Access bei j = 8.

Rein objektiv gesehen bringt das nichts - aber du kannst die Randomisierung ja einfach vor die if-Bedingung schreiben?

ich sehe in deinem Code einige Probleme.
1. Das ist kein Bogosort. Du vertauschst immer nur mit der ersten nicht-sortierten Stelle - damit bist du schon ein ziemliches bisschen schneller als Bogosort, welches irgendwelche Stellen vertauscht
2. Der schon angesprochene OOB-Access bei j=8 auf unsortiert.
3. Der schon angesprochene äussere Loop, der zu früh beendet.
4. In C (und allen anständigen Programmiersprachen ;) ) ist das erste Element 0. Daher iteriert man normalerweise von i=0 bis i < size.
5. Deine Variablen i und j sind nicht deklariert. Dafür 2x r? Und bitte kein C89 mehr - wir schreiben for-loops modern (aka C99 - auch schon 20 Jahre alt...):
C: 
for(int i = ...)
(Es gibt noch ewiggestrige Lehrer und Professoren, die das so wollen - aber sofern nicht klar C89 vorgeschrieben ist, ist C99 sehr viel einfacher zu lesen und verstehen).


Als Blaupause für Bogosort dient Wikipedia recht gut: Bogosort – Wikipedia
Das solltest du recht leicht in C übersetzen können.

Gruss
cwriter
Zum Vergrößern anklicken....
Genau so wie bei Wikipedia gestellt, soll ich ja keine Funktion mit dem Datentyp boolean schreiben.
Also alles soll in der main Funktion geschrieben werden.
Also müsste die Randomisierung vor der if Anweisung stehen und dann anschließend die if Bedingung dann kommen. Wie folgt:

C: 
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>

main()
{
        
        int unsortiert[] = {-1,0,-25,100,6,-3,-2,25};
        int temp, r, j;
        printf("unsortiertes Array:\n");
        printf("---------------------\n");
        for(i = 1; i <= sizeof(unsortiert)/sizeof(int); i++){
            printf("%d. %d\n", i ,unsortiert[i-1]);
        }
        srand(time(NULL));
        for(j = 0; j < 8; j++){
                temp = unsortiert[j];
                r = rand()%8;
                unsortiert[j] = unsortiert[r];
                unsortiert[r] = temp;
               if(unsortiert[j] > unsortiert[j+1]){
                /*Was müsste ich hier machen */
            }       
        }

}
Das Ding ist, wenn in der For-Schleife die If Anweisung kommt wird ja nur einmal geguckt ob die i-te Stelle größer ist als die i+1te Stelle. Nach der If Anweisung, wird i um eins erhöht und im Anschluß wird das Array wieder nach zufälliger Position mit der 1-ten Stelle getauscht. Das heisst, es wird hier ständig getauscht, aber zum Ende hin nie richtig sortiert, da die Variable j immer um 1 inkrementiert wird und die Schleife irgendwann verlässt. Das heisst, man müsste irgendwie aus der For-Schleife in eine andere For-Schleife, die guckt ob das Array sortiert ist und dann wieder zurück in die For-Schleife springen. Ich habe da an Sprungmarken wie goto oder break continue gedacht, nur weiss ich nicht ganz ob das möglich ist und wenn ja, wie man da heran geht.
Danke bis hierhin schon mal :)
 
Sekiro24 hat gesagt.:
Genau so wie bei Wikipedia gestellt, soll ich ja keine Funktion mit dem Datentyp boolean schreiben.
Also alles soll in der main Funktion geschrieben werden.
Zum Vergrößern anklicken....
Na, was macht denn isSorted()? Ob du das mit einer Funktion baust oder direkt in einen Loop integrierst, spielt doch keine Rolle?

Sekiro24 hat gesagt.:
Also müsste die Randomisierung vor der if Anweisung stehen und dann anschließend die if Bedingung dann kommen.
Zum Vergrößern anklicken....
Ich weiss nicht, woraus du das folgerst. Der Wikipedia-Code besteht aus einer Schleife, die unendlich lange läuft, es sei denn, der Array ist schon sortiert.

Also müsste dein Programm aus einer Endlosschleife bestehen, die ein break auf der Bedingung hat, dass der Array sortiert ist.
Und erst, wenn der Array nicht sortiert ist, dann willst du shufflen.


Sekiro24 hat gesagt.:
Das Ding ist, wenn in der For-Schleife die If Anweisung kommt wird ja nur einmal geguckt ob die i-te Stelle größer ist als die i+1te Stelle. Nach der If Anweisung, wird i um eins erhöht und im Anschluß wird das Array wieder nach zufälliger Position mit der 1-ten Stelle getauscht. Das heisst, es wird hier ständig getauscht, aber zum Ende hin nie richtig sortiert, da die Variable j immer um 1 inkrementiert wird und die Schleife irgendwann verlässt.
Zum Vergrößern anklicken....
Genau.

Sekiro24 hat gesagt.:
Das heisst, man müsste irgendwie aus der For-Schleife in eine andere For-Schleife, die guckt ob das Array sortiert ist und dann wieder zurück in die For-Schleife springen. I
Zum Vergrößern anklicken....
Jain. Du kannst die for-Schleifen auch ineinanderpacken. Wobei du eigentlich nicht for benutzen solltest, sondern while. for ist eher zu nutzen, wenn man über einen begrenzten Bereich iteriert (z.B. eben über einen Array). Auch wenn for und while (in C89 sowieso) einander ersetzen können.

Ok. ich gebe dir einfach einen Hinweis:

C: 
int sorted;
while(1 == 1)
{
    sorted = 1;
    for(i=0...)
    {
        if(unsortiert[i] > unsortiert[i+1])
            sorted = 0;
    }
    if(sorted == 1)
        break; // Beende die while-Schleife

    // Randomisiere...
}
Natürlich ist das alles recht krude, aber ich will dir ja nicht die Arbeit wegnehmen ;)

Gruss
cwriter
 
cwriter hat gesagt.:
Na, was macht denn isSorted()? Ob du das mit einer Funktion baust oder direkt in einen Loop integrierst, spielt doch keine Rolle?


Ich weiss nicht, woraus du das folgerst. Der Wikipedia-Code besteht aus einer Schleife, die unendlich lange läuft, es sei denn, der Array ist schon sortiert.

Also müsste dein Programm aus einer Endlosschleife bestehen, die ein break auf der Bedingung hat, dass der Array sortiert ist.
Und erst, wenn der Array nicht sortiert ist, dann willst du shufflen.



Genau.


Jain. Du kannst die for-Schleifen auch ineinanderpacken. Wobei du eigentlich nicht for benutzen solltest, sondern while. for ist eher zu nutzen, wenn man über einen begrenzten Bereich iteriert (z.B. eben über einen Array). Auch wenn for und while (in C89 sowieso) einander ersetzen können.

Ok. ich gebe dir einfach einen Hinweis:

C: 
int sorted;
while(1 == 1)
{
    sorted = 1;
    for(i=0...)
    {
        if(unsortiert[i] > unsortiert[i+1])
            sorted = 0;
    }
    if(sorted == 1)
        break; // Beende die while-Schleife

    // Randomisiere...
}
Natürlich ist das alles recht krude, aber ich will dir ja nicht die Arbeit wegnehmen ;)

Gruss
cwriter
Zum Vergrößern anklicken....
Perfekt, dass war es was ich gesucht habe.
Ich kam halt nicht darauf wo ich das break verwenden soll.
Besten Dank :)
 
Hmm ich weiss nicht was ich falsch mache aber irgendwie bricht der die Schleife dann nicht ab.
Ich habe mal einfach ein bereits sortiertes Array angelegt, jedoch wird trotzdem randomisiert die Elemente vertauscht. Hmm.
C: 
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>

main()
{
        
        int unsortiert[] = {-1,0,-25,100,6,-3,-2,25};
        int unsortiert1[] = {-25,-3,-2,-1,0,6,25,100};
        
        int temp, i,r;
        int sortiert;
        srand(time(NULL));
        while(1 == 1){
            sortiert = 1;
            for(i = 0; i < 8; i++){
                if(unsortiert1[i] > unsortiert1[i+1])
                    sortiert = 0;
            }
            for(i = 0; i < 8; i++)printf("%d.%d\n", i, unsortiert1[i]);
            if(sortiert == 1)
                break;
            
            for(i = 0; i < 8; i++){
                    temp = unsortiert1[i];
                    r = rand()%8;
                    unsortiert1[i] = unsortiert1[r];
                    unsortiert1[r] = temp;
            }
            for(i = 0; i < 8; i++)printf("%d.%d\n", i, unsortiert1[i]);
        }
}
 
Sekiro24 hat gesagt.:
Hmm ich weiss nicht was ich falsch mache aber irgendwie bricht der die Schleife dann nicht ab.
Zum Vergrößern anklicken....
Du iterierst von i=0 bis i=7 (bzw. i < 8).
Innerhalb des Loops ist der höchste Zugriffsindex i+1. D.h. du greifst auf unsortiert[8] zu, was out-of-bounds ist. Das Verhalten des Vergleichs ist also undefiniert.
Fix: i < 8 => i + 1 < 8 => i < 7

Gruss
cwriter
 
Deine Implementierung ist aber immer noch anders als das Bogosort von Wikipedia, gell?

Im Bogosort-Beispiel wird pro Iteration nur ein zufälliges Paar getauscht, also mit 2 zufälligen Indizes. Du tauschst momentan 8 Paare, aber jeden Index mindestens 1x pro Iteration.

Gruss
cwriter
 
cwriter hat gesagt.:
Deine Implementierung ist aber immer noch anders als das Bogosort von Wikipedia, gell?

Im Bogosort-Beispiel wird pro Iteration nur ein zufälliges Paar getauscht, also mit 2 zufälligen Indizes. Du tauschst momentan 8 Paare, aber jeden Index mindestens 1x pro Iteration.

Gruss
cwriter
Zum Vergrößern anklicken....
Ich glaube du meinst die innere letzte for schleife.
Die habe ich jetzt mal raus genommen und anstelle dafür die zwei variablen für die randomisierten zahlen wie auf der von dir genannten Wikipedia Seite angelegt. Ich glaube das meintest du oder ?

C: 
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>

main()
{
        int unsortiert[] = {-1,0,-25,100,6,-3,-2,25};
        /*int sortiert[] = {-25,-3,-2,-1,0,6,25,100};*/
        
        int temp, i,r1, r2;
        int sortiert;
        
        while(1 == 1){
            sortiert = 1;
            for(i = 0; i < 7; i++){
                if(unsortiert[i] > unsortiert[i+1])
                    sortiert = 0;
            }
            for(i = 0; i < 8; i++)printf("%d.%d\n", i+1, unsortiert[i]);
            if(sortiert == 1)
                break;
            
            r1 = rand()%8;
            r2 = rand()%8;
            temp = unsortiert[r1];
            unsortiert[r1] = unsortiert[r2];
            unsortiert[r2] = temp;
            for(i = 0; i < 8; i++)printf("%d.%d\n", i+1, unsortiert[i]);
        }
}
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück