Sortieren eines array mit mehreren Kriterien Sortieren (QuickSort)

Ich versuche herauszufinden, wie (mit einem quicksort-Algorithmus) Sortieren ein struct array nach 2 Kriterien. Zum Beispiel sagen, ich hatte eine struct von:

struct employee{
   char gender[12];
   char name[12];
   int id;
};

Sagen, dass meine Eingabe ist:

struct employee arr[3]=
{
    {"male","Matt",1234},
    {"female","Jessica",2345},
    {"male","Josh",1235}
};

Ich bin zu wollen, Sortieren Sie die Elemente nach Geschlecht zuerst, dann die IDs in aufsteigender Reihenfolge. Ein Beispiel wäre, haben alle Männer zuerst gedruckt mit deren IDs in der Reihenfolge und dann alle Weibchen mit den ihrigen. Ich bin versucht dies zu tun, ohne mit der qsort-Funktion, aber ich habe nicht die geringste Idee, wie das zu überprüfen . Hier ist meine Sortier-Funktion:

void quicksort(struct employee *arr, int left, int right)
{
    int pivot, l, r, temp;
    if(left < right)
    {
        p = left;
        l = left;
        r = right;
        while(l < r)
        {

            while(arr[l].id <= arr[p].id && l <= right)
                l++;
            while(arr[r].id > arr[p].id && r >= left)
                r--;

            if(l < r)
            {
                temp = arr[l].id;
                arr[l].id = arr[r].id;
                arr[r].id = temp;
            }
        }


        temp = arr[r].id;
        arr[r].id = arr[p].id;
        arr[p].id = temp;

        quicksort(arr, left, r-1);
        quicksort(arr, r+1, right);
    }
}

Irgendwelche Vorschläge? Ich dachte ich könnte mit strcmp, aber ich kann nicht herausfinden, wo Sie gehören innerhalb der Funktion.

InformationsquelleAutor bardockyo | 2012-11-14

Können Sie sicher inline-die Vergleich-Funktion und eine swapper für diese Angelegenheit. Dieser code ist ziemlich einfach und beruht auf der gültigen Zeiger, aber Sie ' L bekommen die Idee. Ich nahm auch die Freiheit, Sie zu trimmen Sie Ihre quicksort, reparieren, was wurde aus auf dem Weg (hoffe ich).

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

//employee record
struct employee
{
    char gender[12];
    char name[12];
    int id;
};

//swap employee records
void swap_employee(struct employee *left, struct employee *right)
{
    struct employee tmp = *right;
    *right = *left;
    *left = tmp;
}

//compare employee records
int compare_employee(const struct employee* left,
                     const struct employee* right)
{
    int gender = strcmp(left->gender, right->gender);
    return (gender ? gender : (left->id - right->id));
}

//quicksort for employees
static void quicksort_(struct employee *arr, int left, int right)
{
    struct employee p = arr[(left+right)/2];    //as good as any
    int l = left, r = right;   //movable indicies

    while (l <= r)
    {
        while (compare_employee(arr+l, &p) < 0)
            ++l;
        while (compare_employee(arr+r, &p) > 0)
            --r;
        if (l <= r)
        {
            swap_employee(arr+l, arr+r);
            ++l; --r;
        }
    }

    if (left < r)
        quicksort_(arr, left, r);
    if (l < right)
        quicksort_(arr, l, right);
}

//exposed API
void quicksort(struct employee *arr, int count)
{
    if (arr && (count>0))
        quicksort_(arr, 0, count-1);
}

/* sample usage */
int main(int argc, char *argv[])
{
    struct employee arr[]=
    {
        {"male","Matt",1234},
        {"female","Jessica",2345},
        {"male","Josh",1235},
        {"female","Betsy",2344},
        {"male","Roger",1233}
    };

    quicksort(arr, sizeof(arr)/sizeof(arr[0]));

    for (int i=0;i<sizeof(arr)/sizeof(arr[0]);++i)
        printf("%s, %s, %d\n", arr[i].gender,arr[i].name, arr[i].id);

    return EXIT_SUCCESS;
}

Ergebnisse

female, Betsy, 2344
female, Jessica, 2345
male, Roger, 1233
male, Matt, 1234
male, Josh, 1235

InformationsquelleAutor WhozCraig

1

Es ist nicht schwer. Sie brauchen nur eine Funktion (oder einen block von code zu sehen, Sie wollen, dass es "hart codiert") zu vergleichen, Ihre Strukturen. In der Beispiel-code, den Sie gegeben haben, Sie vergleicht das aktuelle Objekt mit arr[l].id <= arr[p].id. Das ist Sie nur wenn man die id herausfinden, wo Ihr element passt. Sie brauchen nur zu vergleichen mit die anderen Felder an dieser Stelle. Es wäre viel aufgeräumter mit einer Funktion (die ich Euch gab, eine solche Funktion in Ihre frühere Frage).

Sind Sie auch nur eine Verschiebung der id-Felder, wenn Sie die swap - verlassen Sie die Namen und Geschlecht unverändert in Ihre Daten. Sollten Sie das ganze struct.
- Ah danke für den Fang, die ich nicht eve bemerken. Wenn ich versuche zu wechseln arr[l]=arr[r], ich bin immer ein syntax Fehler.
InformationsquelleAutor kallikak
0

Verwenden Sie einfach die integrierten qsort, und übergeben Sie eine Komparator-Funktion vergleicht gender ersten und berät ID-Nummer nur im Falle der "Bande" in den ersten Vergleich.
- Danke, mir ist schon klar, aber ich bin versucht zu sehen, wie es funktionieren würde, wenn es war hart codiert, nicht mit qsort
InformationsquelleAutor amalloy
0

Denke ich, sollten Sie Sortieren das array von gender ersten, eine für männliche, eine für weibliche. Dann verwenden Sie die quicksort-Funktion zum Sortieren innerhalb dieser zwei arrays.

Können Sie strcmp Sortieren die ursprüngliche array in zwei arrays: eine für männliche, eine für weibliche.
- Ist es möglich, die Sortierung in zwei Durchgängen wie diesem-aber wenn du das tun, es ist entscheidend, um ein stabiles Sortieren (behält die ursprüngliche Reihenfolge bei Gleichstand). Quicksort, zumindest als Regel implementiert, für arrays, die nicht stabil ist.
InformationsquelleAutor

int compare_employee (struct employee * a, struct employee * b) {
    int diff = strcmp(a->gender, b->gender);

    if (diff) //if gender different
        return -diff; //sort descending, please double check this and reverse in case I am wrong

    return a->id - b->id; //else sort by id
}

Ausgabe wird eine negative Zahl ein, wenn a < b, positiv, wenn a > b null, wenn Sie gleich sind.

Verwenden Sie es entweder in Ihren eigenen quicksort oder als qsort Komparator.

InformationsquelleAutor Sergey L.

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.