Quicksort und Rekursion. Fehler beim Index, aber wie soll ich es machen?

bimbambino

Hallo zusammen,

ich möchte Quicksort per Rekursion lösen.
Ich habe irgendwo einen Fehler mit der Übergabe des Index,
weiß aber nicht, wie ich es lösen soll.
Einmal funktioniert die Umgruppierung.

Hat jemand ne Idee?

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

void Grupp1(int anfang, int ende, float a[], int ind);
void Quicksort(int anfang, int ende, float a[]);

void Quicksort (int anfang, int ende, float a[])
{
  int ind=0;
  if (anfang < ende)
  {
    Grupp1 (anfang, ende, a, ind);	
    Quicksort(anfang,ind-1,a);	
    Quicksort(ind+1,ende,a);
  }
}

void Grupp1(int anfang, int ende, float a[], int ind)
{
  int i=0; int k=ende; float temp=0;
  ind=anfang;

  while (ind < k)
  {
    if (a[ind+1] < a[ind])
    {
      temp=a[ind];
      a[ind]=a[ind+1];
      a[ind+1]=temp;
      ind++;
    } else
    {
      temp=a[ind+1];
      a[ind+1]=a[k];
      a[k]=temp;
      k--;
    }
  }
}  

main()
{
int anfang=0;
int ende=5;
int i;
int ind=0;
float a[5]={6,2,8,5,1};

printf("Ausgangszustand:\n");
for (i=0; i<5; i++) printf("%1.0f\t",a[i]);

Quicksort(0,4,a);

printf("\n\nSortiert:\n");
for (i=0; i<5; i++) printf("%1.0f\t",a[i]);
printf("\n\n");
system("PAUSE");	
}

mcr

Hi

deine Grupp1() Routine gibt die neue Position nicht zurück.

Hier meine verbesserte Version:

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

#define ANZ 10

int  Grupp1(int anfang, int ende, float a[]);
void Quicksort(int anfang, int ende, float a[]);

void Quicksort (int anfang, int ende, float a[])
{
    if (anfang < ende)
    {
        int ind = Grupp1 (anfang, ende, a);
        Quicksort(anfang,ind-1,a);
        Quicksort(ind+1,ende,a);
    }
}

int Grupp1(int anfang, int ende, float a[]) {
    int i = anfang, j = ende;

    printf("%d..%d\n", anfang, ende);

    while (i<j) {
        if (a[i+1] < a[i]) {
            float tmp = a[i];
            printf("i: %d   %2.0f <  %2.0f  tausche   %d  <--> %d", i, a[i+1], a[i], i, i+1);
            a[i] = a[i+1];
            a[i+1] = tmp;
            ++i;
            printf("   neues i: %d\n", i);
        } else {
            float tmp = a[j];
            printf("i: %d   %2.0f >= %2.0f  tausche   %d  <--> %d", i, a[i+1], a[i], i+1, j);
            a[j] = a[i+1];
            a[i+1] = tmp;
            --j;
            printf("   neues j: %d\n", j);
        }
    }

    printf("Feste Position: %d\n", i);

    for (j=0; j<ANZ; j++) printf("%1.0f\t",a[j]);
    printf("\n");

    return i;
}

int main(void)
{
    int i;
    float a[ANZ]={6,2,8,1,5,2,3,10,5,4};

    printf("Ausgangszustand:\n");
    for (i=0; i<ANZ; i++) printf("%1.0f\t",a[i]);

    printf("\n");
    Quicksort(0,ANZ-1,a);

    printf("\n\nSortiert:\n");
    for (i=0; i<ANZ; i++) printf("%1.0f\t",a[i]);
    printf("\n\n");

    return 0;
}

Gruß mcr

mcr

Eine andere Möglichkeit, Grupp1() zu implementieren, wäre die folgende:

int Grupp1(int anfang, int ende, float a[])
{
    int i=anfang-1, j=ende;
    float x = a[ende], tmp;

    printf("%d..%d   x: %1.0f\n", anfang, ende, x);

    while (1) {
        while (a[++i] <= x && i < ende);   
        while (a[--j] >= x && j > anfang); 

        printf("    i: %d a[%d]=%1.0f    a[%d]=%1.0f  j: %d\n", i, i, a[i], j, a[j], j);
        if (i >= j) break;

        tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
    tmp = a[ende];
    a[ende] = a[i];
    a[i] = tmp;

    for (j=0; j<ANZ; j++) printf("%1.0f\t",a[j]);
    printf("\n");

    return i;
}

Gruß mcr

bimbambino

vielen Dank!

hat mir sehr weitergeholfen.
ich habe das Problem nun verstanden.

Grüße
Bimbambino