[C] Quicksort per strutture...

[Ol3iconfini]

Salve, ho il seguente problema. Ho un insieme di valori float da ordinare. Ciascun valore è contenuto in una struttura contenente anche il nome dell'elemento.

struct Data {    char *name;    float length;  };

In pratica ho visivamente una cosa del genere:

pippo 0.412
pluto 0.341
minnie 0.123

Quello che dovrei fare è restituire le tre righe ordinate, cioè

minnie 0.123
pluto 0.341
pippo 0.412

Pensavo di utilizzare la funzione qsort... Il problema è che l'ordinamento dei valori è elementare, ma non so come associare poi i valori ai nomi... Cioè, qsort mi permette di ordinare un vettore di valori. Ma io devo ordinare un vettore di elementi strutturati secondo il loro valore...
In bash la soluzione è semplice, ma in C?
Qualche idea?

[YuYevon]

Cioè in pratica devi fare l'ordinamento di un array di strutture con un campo "name" e un altro "lenght" ordinandole secondi i loro rispettivi valori di lenght? Beh direi che è facile, basta che ordini l'array con l'algoritmo quicksort accedendo ai campi "lenght" delle strutture nel momento in cui fai il confronto...

Forse c'è qualcosa che non ho capito, scusami :|

[Ol3iconfini]

Ordinare un vettore di float è semplice. Ma poi per stampare a video l'ordine dei valori con i nomi corrispondenti?
Ad esempio, dato:

pippo 0.412
pluto 0.341
minnie 0.123

Voglio stampare a video:

minnie 0.123
pluto 0.341
pippo 0.412

[MItaly]

Crea un array di strutture Data contenente i tuoi dati, scrivi la tua funzione di confronto come richiede la funzione qsort, richiama qsort e stampa normalmente il tuo array.

[YuYevon]

Sì infatti, devi semplicemente ordinare l'array con un semplice confronto, come se fosse un array di valori numerci normali, solo che anziché confrontare direttamente gli elementi dell'array devi accedere ai loro campi "lenght". Una volta stabilito in un confronto quale valore float è il minore, scambi di conseguenza le strutture e ordini l'array, dopodiché lo stampi.

[Ol3iconfini]

Questo?
Ho un puntatore:

Data *ptrLen

Ogni elemento lo punto con

ptrLen[count].name

ptrLen[count].length

Ma cosa gli passo a qsort?

  qsort (ptrLen[???].length, 100, sizeof(float), compare);

[MItaly]

Non l'ho collaudato, ma dovrebbe andare.

#include <stdio.h>
#include <stdlib.h>
#define ARRSIZE(arr) ((size_t)(sizeof(arr)/sizeof(*arr)))
typedef struct tagData
{
    const char *name;
    float length;
} Data;

int DataCompare(const void * elem1, const void * elem2);

int main(void)
{
    Data dt[3];
    dt[0].name = "pippo";
    dt[0].length = 0.412
    dt[1].name = "pluto";
    dt[1].length = 0.341
    dt[2].name = "minnie";
    dt[2].length = 0.123
    qsort(dt,ARRSIZE(dt),sizeof(*dt),DataCompare);
    for(int i=0;i<ARRSIZE(dt);i++)
        printf("%s %f",dt[i].name,dt[i].length);
    return 0;
}

int DataCompare(const void * elem1, const void * elem2)
{
    return (int)((const Data *)elem1->length-(const Data *)elem2->length);
}

[YuYevon]

Ah ma voi parlavate del qsort predefinito del C? Io pensavo dovessi scrivere tu la funzione... comunque qui ho la mia soluzione adattata al tuo caso, è un po' rozza perché non mi ci sono soffermato tanto ma funziona (il pivot viene scelto staticamente, cosa non proprio tra le migliori ma comunque efficace)

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

typedef struct {
        char nome[20];
        float x;
        } struttura;

void sort(struttura *, int, int);
void swap(struttura *, struttura *);
void immissione_dati(struttura *, int);
void visualizza_dati(struttura *, int);

int main(void)
{
  struttura *array;
  int i, n;
  
  printf("Immettere il numero delle componenti dell'array da ordinare: ");
  scanf("%d%*c", &n);
  
  array = (struttura *)malloc(n*sizeof(struttura));
  
  immissione_dati(array, n);

  puts("\n");
  
  sort(array, 0, n-1);
  
  visualizza_dati(array, n);
  
  scanf("\n%*c");
  return 0;
}

void sort(struttura *array, int inizio, int fine) {

  int i, j;
  struttura pivot; 

  if (fine > inizio) {
     pivot = *(array + inizio);
     i = inizio + 1;
     j = fine + 1;
     while(i < j) {
        if(array[i].x < pivot.x) 
           i++;
        else {
           j--;
           swap(array + i, array + j);
        }
     }
     i--;
     swap(array + inizio, array + i);
     sort(array, inizio, i);
     sort(array, j, fine);
  }
}

void swap(struttura *p1, struttura *p2) {

  struttura temp;
  
  temp=*p2;
  *p2=*p1;
  *p1=temp;
}

void immissione_dati(struttura *array, int n) {
     
     short i;
     
     printf("Immettere i dati:\n");
     for (i=0; i<n; i++) {
        printf("\nStruttura %hd\nNome: ", i+1);
        gets(array[i].nome);
        printf("Float: ");
        scanf("\n%f%*c", &(array[i].x));
        puts("\n");
     }
}

void visualizza_dati(struttura *array, int n) {

  short i;

  for (i=0; i<n; i++) {
     printf("Nome: %s\nFloat: %f\n\n", array[i].nome, array[i].x);
  }
}

[Ol3iconfini]

Ora controllo. Grazie, naturalmente.

[MItaly]

Originariamente inviato da YuYevon
Ah ma voi parlavate del qsort predefinito del C? Io pensavo dovessi scrivere tu la funzione...

Prima regola del programmatore: mai riscrivere codice già scritto e collaudato.

Originariamente inviato da Ol3iconfini
Ora controllo. Grazie, naturalmente.

Prego, figurati.