4. Quicksort geht nicht - Struktogramm falsch ?

Quicksort geht nicht - Struktogramm falsch ?

  • I

    Hallo!

    Wir machen in der schule gerade Quicksort durch.

    Hier das Struktogramm, so haben wir es in der Schule aufgeschrieben:

    http://www.imagebanana.com/view/u7ucp8f3/Unbenannt.png

    Befüllen und Ausgeben des Arrays funktioniert.

    Ich komme einfach nicht dahinter, das Programm friert immer ein 😉

    #include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define N 7

void menu();
void initArray(int feld[], size_t n);
void printArray(int feld[], size_t n);
void quicksort(int feld[], size_t n, int li, int re);

int main(void)
{
    menu();
    return 0;
}

void menu()
{
    int feld[N];
    int re = N-1;
    int li = 0;

    printf("Quicksort\n\n");
    initArray(feld,N);

    printf("Feld initialisieren:\n");
    printArray(feld,N);
    printf("\n");

    quicksort(feld, N, li, re);
    printf("Feld nach qsort:\n");
    printArray(feld,N);

    printf("\n\n\n");
}

void initArray(int feld[], size_t n)
{
  // befüllt Array mit Zufallszahlen von 0-9
}

void printArray(int feld[], size_t n)
{
   //Ausgabe des Arrays
}

void quicksort(int feld[], size_t n, int li, int re)
{
    int p;  //pivot
    int i,k;
    int temp;

    if(re > li)
    {
        p = feld[re];
        i = li-1;
        k = re;

        do
        {
            do
            {
               i++;
            }while(! feld[i] >= p);

            do
            {
                k = k-1;
            }while(! feld[k] <= p);

            if(i < k)
            {
                temp = feld[i];
                feld[i] = feld[k];
                feld[k] = temp;
            }
        }while(! i >= k);

        temp = feld[i];
        feld[i] = feld[re];
        feld[re] = temp;

        quicksort(feld, n, li, i-1);
        quicksort(feld, n, i+1, re);
    }
}

    Helft mir bitte 😃

    0
  • V

    Erst immer den Code reparieren. Dann nachträglich das Struktogramm anpassen.

    Hab zum Debuggen ein printf eingebaut. Ganz wichtig.
    Und !(a>=b) statt !a >=b.

    Ob es jetzt schon klappt, weiß ich nicht, stürzt aber nicht mehr ab. Und mit so Debug-Auisgaben kriegste den Rest sicher hin.
    Wenn nicht, einfach wieder fragen, immer mit dem kompletten aktuellen Code, damit wir ihn nur reinkopieren müssen zum Rumprobieren.

    #include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define N 7

void menu();
void initArray(int feld[], size_t n);
void printArray(int feld[], size_t n);
void quicksort(int feld[], size_t n, int li, int re);

int main(void)
{
    menu();
    return 0;
}

void menu()
{
    int feld[N];
    int re = N-1;
    int li = 0;

    printf("Quicksort\n\n");
    initArray(feld,N);

    printf("Feld initialisieren:\n");
    printArray(feld,N);
    printf("\n");

    quicksort(feld, N, li, re);
    printf("Feld nach qsort:\n");
    printArray(feld,N);

    printf("\n\n\n");
}

void initArray(int feld[], size_t n)
{
  // befüllt Array mit Zufallszahlen von 0-9
}

void printArray(int feld[], size_t n)
{
   //Ausgabe des Arrays
}

void quicksort(int feld[], size_t n, int li, int re)
{
    printf("%d-%d\n",li,re);
    int p;  //pivot
    int i,k;
    int temp;

    if(re > li)
    {
        p = feld[re];
        i = li-1;
        k = re;

        do
        {
            do
            {
               i++;
            }while(! (feld[i] >= p));

            do
            {
                k = k-1;
            }while(! (feld[k] <= p));

            if(i < k)
            {
                temp = feld[i];
                feld[i] = feld[k];
                feld[k] = temp;
            }
        }while(! (i >= k));

        temp = feld[i];
        feld[i] = feld[re];
        feld[re] = temp;

        quicksort(feld, n, li, i-1);
        quicksort(feld, n, i+1, re);
    }
}
    0
  • I

    volkard schrieb:

    Erst immer den Code reparieren. Dann nachträglich das Struktogramm anpassen.

    Hab zum Debuggen ein printf eingebaut. Ganz wichtig.
    Und !(a>=b) statt !a >=b.

    Danke, jetzt funktioniert es 😉

    0
  • V

    iN3verM1nd schrieb:

    Hier das Struktogramm, so haben wir es in der Schule aufgeschrieben:
    http://www.imagebanana.com/view/u7ucp8f3/Unbenannt.png

    Das Bildchen für if ist falsch.
    Das müßte so gehen:
    http://www.lehrer.uni-karlsruhe.de/~za1309/gif/Struktogramm_if_switch.gif

    0
  • I

    volkard schrieb:

    iN3verM1nd schrieb:

    Hier das Struktogramm, so haben wir es in der Schule aufgeschrieben:
    http://www.imagebanana.com/view/u7ucp8f3/Unbenannt.png

    Das Bildchen für if ist falsch.
    Das müßte so gehen:
    http://www.lehrer.uni-karlsruhe.de/~za1309/gif/Struktogramm_if_switch.gif

    Okay. 😃

    0
  • V

    Wenn Dir jetzt langweilig ist, und das sollte es sein, dann probier mal was ganz modernes:
    Statt

    void quicksort(int feld[], size_t n, int li, int re)
nebst
quicksort(feld, N, li, re);

    könntest Du auch machen

    void quicksort(int* begin, int* end)//end zeigt eins hinter das letzte Element
nebst
quicksort(feld, feld+N);

    Oft, sehr oft, werden dadurch Algorithmen erheblich eleganter. Die C++-Chaoten machen den Trick den lieben langen Tag lang, nennen es iteratoren und stl und so.

    Ist aber das erste mal sicher ziemlich schwierig. 😉

    0
Anmelden zum Antworten