4. Array sortieren mit qsort

Array sortieren mit qsort

  • D

    Hi Leute,

    vor kurzem sollte ich ein Programm erweitern, bei dem man die Anzahl der Elemente vom Vektor selbst eingeben kann. Dann wurden Zufallswerte erzeugt.
    Das habe ich letztlich hinbekommen. Und das Programm sieht so aus:

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

void ausgabe(int b[], int n);

main()
{

  int *value;
  int size, i = 0;

   printf("Anzahl eingeben : ");
   scanf("%d", &size);
   value = (int *)malloc(size*sizeof(int));

  /* Initialisierung mit Zufallszahlen */
  for (i = 0; i < size; i++)
    value[i] = rand();

  /* Ausgabe des Vektors */
  ausgabe(value, size);

  return 0;
}

void ausgabe(int b[], int n)
{
  int i;

  for (i = 0; i < n; i++)
    printf("%d.tes Element: %d\n", i , b[i]);
}

    Jetzt soll ich das nochmal so erweitern, dass die Elemente sortiert ausgegeben werden.
    Dazu darf ich die qsort() benutzen.

    Ich habe zwar den Hinweis,
    Prototyp:

    void qsort (void *base, unsigned nelem, unsigned width,
                   int (*fcmp) (const void*, const void*));

    base: zeigt auf den Anfang des zu sortierenden Vektors
    nelem: gibt die Anzahl der Vektorelemente an
    width: gibt die Größe eines einzelnen Vektorelements in Bytes an.
    fcmp: zeigt auf eine Vergleichsfunktion, welche von qsort() aufgeruden wird. Dabei werden als Argumente 2 Zeiger elem1 und elem2 übergeben, welche zwei zu vergleichende Vektorelemente verweisen.

    Eigentlich muss doch nur die Ausgabefunktion "ausgabe" verändert werden. Aber wie? Die Syntax verstehe ich nicht.
    nelem (anzahl der vektorelemente) ist ja in dem Programm "size", aber wie kann ich das insgesamt übergeben, dass es sortiert zurückgegeben wird?

    Vielen Dank!!

    0
  • R

    Der Prototyp sieht so aus

    void
     qsort(void *base, size_t nmemb, size_t size,
         int (*compar)(const void *, const void *));

    qsort sortiert das Array, was du im in base übergibst.

    man: qsort(3)

    0
  • K

    So funktioniert es auch mit der Nachbarelementin:

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

void ausgabe(int *b, int n)
{
  int i;

  for (i = 0; i < n; i++)
      printf("%d.tes Element: %d\n", i , b[i]);
}

int fcmp(const void *A, const void *B)
{
  int *a = (int *)A;
  int *b = (int *)B;

  if (*a < *b)
	  return -1;
  if (*a > *b)
	  return +1;
  return 0;
}

int main()
{
  int *base;
  int nelem, i;

  printf("nelem eingeben : ");
  scanf("%d", &nelem);
  base = (int *)malloc(nelem*sizeof(int));
  for (i = 0; i < nelem; i++)
      base[i] = rand();
  qsort(base, nelem, sizeof(int), fcmp);
  ausgabe(base, nelem);
  free(base);
  getch();
  return 0;
}
    0
  • D

    Ist ja Wahnsinn, wie schnell das manch einer hinbekommen kann...
    Ich muss mir das mal genau ansehen und nachvollziehen.

    Vielen Dank dir!

    Um zunächst mal keinen neuen Thread aufzumachen, hab ich noch eine andere Frage.

    Und zwar, wenn ich ein eigenes qsort Verfahren schreiben will, wo ich einen Zeiger zum Durchlaufen einer linear gespeicherten Liste verwende, sieht das dann so aus?

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

void einfügen(int *array, int elemente) {
   int index,index_klein,wert_klein;

   for(index=1; index<=elemente; index++) {

      wert_klein=array[index]; //Position speichern

      for( index_klein=index; //kleineren Wert suchen als wert_klein
           array[index_klein-1] > wert_klein&&index_klein > 0;
           index_klein-- )

         array[index_klein] = array[index_klein-1];
      // gespeichertes Element an neue Position ->
       // Lücke auffüllen
      array[index_klein]=wert_klein;
   }
}

int main() {
   int i;

   int test_array[] = { 10,2,8 };
   int N = sizeof(test_array)/sizeof(int);

   einfügen(test_array, N-1);

   for(i = 0; i < N; i++)
      printf("%d ", test_array[i]);
   printf("\n");
   return 0;
}

    Danke fürs Lesen!

    0
  • V

    keksekekse schrieb:

    base = (int *)malloc(nelem*sizeof(int));

    http://c-faq.com/malloc/mallocnocast.html
    😉

    0
  • K

    Sry, hab ich aus dem Originaltext übernommen.
    Es gäbe noch mehr zu meckern:
    - malloc(); (Borland: malloc.h, MS: alloc.h) ist bereits in stdlib.h definiert
    - getch(); ist nicht ANSI C

    0
  • K

    dprzon schrieb:

    wenn ich ein eigenes qsort Verfahren schreiben will

    http://de.wikipedia.org/wiki/Quicksort

    0
  • D

    keksekekse schrieb:

    dprzon schrieb:

    wenn ich ein eigenes qsort Verfahren schreiben will

    http://de.wikipedia.org/wiki/Quicksort

    Danke für den Link.
    Ich habe ja eine quicksort Lösung vorhin gepostet.

    Speziell geht es mir darum, ob es so richtig ist, wenn man einen "Zeiger zum Durchlaufen einer linear gespeicherten Liste" benutzt.
    Das wäre in meinem Fall *array, oder?

    0
Anmelden zum Antworten