Quicksort - sortowanie struktury

Question

Musze wykonać sortowanie struktury za pomocą Quicksorta. Jest to struktura z książkami (tytuł, autor, rok wydania, cena). Wiem, że istnieje w C funkcja qsort, ale niestety nie mogę nią zrobić tego zadania, bo potrzebuje zliczyć liczbę porównań oraz zamian.

Na jakiej zasadzie powinienem podstawiać zmienną pivot? Teraz mam to zrobione tak i niestety wywala błędy w  kompilatorze

int partition(struct daneks X[], int low, int high)
{
    char pivot[MAX_TYTUL] = X[low];
    char tytul[MAX_TYTUL];
    int i = low-1, j = high+1;

    while(i<j) {
        while(X[--j]>pivot[MAX_TYTUL])
            ;
        while(X[++i]<pivot[MAX_TYTUL])
            ;
        if(i<j)
        {
           strcpy(tytul, X[i].tytul);
           strcpy(X[i].tytul, X[j].tytul);
           strcpy(X[j].tytul, tytul);
        }
    }
    return j;
}

void quicksort(struct daneks X[], int low, int high)
{
    if(low<high) {
        int partition_index = partition(X,low,high);
        quicksort(X, low, partition_index);
        quicksort(X, partition_index+1, high);
    }
}

 

Comments

Wrzuć cały kod, bo nikt się nie będzie domyślał jak wygląda twoja struktura. Poza tym, błąd może być w zupełnie innym miejscu

---

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

#define MAX_TYTUL 40
#define MAX_AUTOR 40
#define MAX_ksiazki 100

struct daneks {
    char tytul[MAX_TYTUL];
    char autor[MAX_AUTOR];
    int rok;
};

int odczyt_z_pliku(FILE *, struct daneks [], int rozmiar_pliku);
int zapis_do_pliku(FILE *fosoba, int licznik_osob, struct daneks [], int rozmiar_pliku);

int porownania, zamiany;

int main()
{
    int licznik_end, licznik_struktur, index;
    int rozmiar;
    struct daneks ksiazki[MAX_ksiazki];
    rozmiar = sizeof(struct daneks);

    FILE *book;
    if((book = fopen("dane.txt","a+")) == NULL)
    {
        fputs("Nie mozna otworzyc pliku.\n",stderr);
        exit(1);
    }
    rewind(book);

    licznik_struktur = odczyt_z_pliku(book,ksiazki,rozmiar);
    licznik_end = zapis_do_pliku(book,licznik_struktur,ksiazki,rozmiar);

    puts("Oto lista Twoich ksiazek: ");
    for(index = 0; index < licznik_end; index++)
        printf("%s, %s, %d \n",ksiazki[index].tytul,ksiazki[index].autor,ksiazki[index].rok);

    fwrite(&ksiazki[licznik_struktur],rozmiar,licznik_end-licznik_struktur,book);


    quicksort(ksiazki,0,licznik_struktur);

    puts("\n\nKsiazki po sortowaniu quicksort: ");
    for(index = 0; index < licznik_end; index++)
        printf("%s, %s, %d \n",ksiazki[index].tytul,ksiazki[index].autor,ksiazki[index].rok);


    return 0;
}

int odczyt_z_pliku(FILE *fosoba, struct daneks X[], int rozmiar)
{
    int licznik = 0;
    while(licznik < MAX_ksiazki && fread(&X[licznik],rozmiar,1,fosoba) == 1)
        licznik++;

    if(licznik == MAX_ksiazki)
    {
        fputs("Plik dane.txt jest pelny.",stderr);
        exit(2);
    }
    return licznik;
}

int zapis_do_pliku(FILE *fosoba, int licznik_struktur, struct daneks X[], int rozmiar)
{
    puts("\nPodaj nowe ksiazki do zapisania. \n");
    puts("Podaj tytul.");
    puts("Jesli nie chcesz dodawac nowych ksiazek i zobaczyc aktualna liste nacisnij (ENTER)!");
    while(licznik_struktur < MAX_ksiazki && gets(X[licznik_struktur].tytul) != NULL && X[licznik_struktur].tytul[0] != '\0')
        {
            puts("Teraz podaj autora.");
            gets(X[licznik_struktur].autor);
            puts("Teraz podaj rok wydania.");
            scanf("%d",&X[licznik_struktur++].rok);
            while(getchar() != '\n')
                continue;
            if(licznik_struktur < MAX_ksiazki)
                puts("Podaj nastepny tytul.");
        }
    return licznik_struktur;
}

///QUICKSORT
int partition(struct daneks X[], int low, int high)
{
    char pivot[MAX_TYTUL];
    char tytul[MAX_TYTUL];

    strcpy(pivot[MAX_TYTUL], X[low].tytul);

    int i = low-1, j = high+1;

    while(i<j) {
        while(X[--j].tytul>pivot[MAX_TYTUL])
            ;
        while(X[++i].tytul<pivot[MAX_TYTUL])
            ;
        if(i<j)
        {
           strcpy(tytul, X[i].tytul);
           strcpy(X[i].tytul, X[j].tytul);
           strcpy(X[j].tytul, tytul);
        }
    }
    return j;
}

void quicksort(struct daneks X[], int low, int high)
{
    if(low<high) {
        int partition_index = partition(X,low,high);
        quicksort(X, low, partition_index);
        quicksort(X, partition_index+1, high);
    }
}

 

Answer 1

Linia 100 i 102: do porównywania łańcuchów znakowych użyj funkcji strcmp.

Comments

Dalej nie działa :/

///QUICKSORT
int partition(struct daneks X[], int low, int high)
{
    char pivot[MAX_TYTUL];
    char tytul[MAX_TYTUL];

    strcpy(pivot[MAX_TYTUL], X[low].tytul);

    int i = low-1, j = high+1;

    while(i<j) {
        while(strcmp(X[--j].tytul, pivot[MAX_TYTUL]) > 0)
            ;
        while(strcmp(X[++i].tytul, pivot[MAX_TYTUL]) < 0)
            ;
        if(i<j)
        {
           strcpy(tytul, X[i].tytul);
           strcpy(X[i].tytul, X[j].tytul);
           strcpy(X[j].tytul, tytul);
        }
    }
    return j;
}

void quicksort(struct daneks X[], int low, int high)
{
    if(low<high) {
        int partition_index = partition(X,low,high);
        quicksort(X, low, partition_index);
        quicksort(X, partition_index+1, high);
    }
}

 

---

strcmp(X[--j].tytul, pivot)

strcmp(X[++i].tytul, pivot) 

 

Answer 2

Przykładowy kod qsorta, nie sprawdzałem czy zawsze zadziała poprawnie, taki napisany na kolanie:

#include <iostream>
#include <cstdlib>
#include <ctime>

void mqsort( int data[] , const int size ) {
    if( size < 2 ) {  // Jeden element albo zero elementów...
        return;       // stanowią zawsze posortowany ciąg.
    }
    {
        const int base = rand() % size;
        const int swp = data[0];
        data[0] = data[base];
        data[base] = swp;
    }
    int split = 1;
    for( int i=1 ; i<size ; i++ ) {
        if( data[0] > data[i] ) {
            const int swp = data[i];
            data[i] = data[split];
            data[split++] = swp;
        }
    }
    mqsort( data , split );
    mqsort( data + split , size - split );
}

int main(int argc, char *argv[]) {
    int data[] = {10,11,-2,7,20,9,9,9,23,18,10};
    srand(time(NULL));
    mqsort( data , (int)(sizeof(data)/sizeof(data[0])) );
    for( int i=0 ; i<(int)(sizeof(data)/sizeof(data[0])) ; i++ ) {
        std::cout << data[i] << std::endl;
    }
    return 0;
}