• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Quicksort - sortowanie struktury

VPS Starter Arubacloud
0 głosów
694 wizyt
pytanie zadane 24 czerwca 2018 w C i C++ przez siemasiema123.96 Początkujący (350 p.)

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);
    }
}

 

komentarz 24 czerwca 2018 przez Secrus Nałogowiec (32,880 p.)
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
komentarz 24 czerwca 2018 przez siemasiema123.96 Początkujący (350 p.)
#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);
    }
}



 

2 odpowiedzi

0 głosów
odpowiedź 25 czerwca 2018 przez j23 Mędrzec (194,920 p.)

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

komentarz 25 czerwca 2018 przez siemasiema123.96 Początkujący (350 p.)

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);
    }
}

 

komentarz 25 czerwca 2018 przez j23 Mędrzec (194,920 p.)
strcmp(X[--j].tytul, pivot)

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

 

0 głosów
odpowiedź 9 listopada 2019 przez mmarszik Mądrala (7,390 p.)

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;
}

 

Podobne pytania

0 głosów
0 odpowiedzi 146 wizyt
pytanie zadane 15 listopada 2022 w C i C++ przez ijoasia Nowicjusz (120 p.)
0 głosów
1 odpowiedź 306 wizyt
pytanie zadane 28 marca 2020 w C i C++ przez wall7489 Obywatel (1,250 p.)
0 głosów
2 odpowiedzi 588 wizyt

92,452 zapytań

141,262 odpowiedzi

319,077 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...