Searching and Sorting

vyhľadávanie a triedenie zoznamov, knižnica stdlib.h, funkcie qsort(), bsearch()

Záznam z prednášky

Searching and Sorting

  • (slide) Trošku sa však vráťme. Keď ste hovorili o poliach, hovorili ste aj o dvoch základných operáciách, ktoré nad uloženými údajmi v poli potrebujeme vykonávať. Ktoré to sú? Vyhľadávanie a triedenie.
  • Lineárne vyhľadávanie už poznáme - doteraz sme však hľadali len v poliach jednoduchých údajových typov. Ako bude vyzerať táto operácia nad zoznamom objektov typu štruktúra?

  • (slide) Jednoduchú reprezentáciu lineárneho vyhľadávania ste si vytvorili už v predmete Základy algoritmizácie a programovania. Čo budeme potrebovať upraviť pre použitie vyhľadávania nad poľom štruktúr?

  • Vytvoríme funkciu, pomocou ktorej budeme vedieť v danom poli vyhľadať konkrétnu osobu na základe jej priezviska:

    int search_by_surname(const struct person data[], 
                          const size_t size, 
                          const char surname[]){
        for(size_t idx=0; idx < size; idx++){
            if(strcmp(data[idx].surname, surname) == 0){
                return idx;
            }
        }
        return -1;
    }
  • Rovnako tak môžeme vytvoriť funkciu, pomocou ktorej budeme vedieť v danom poli vyhľadať konkrétnu osobu na základe mena a priezviska:

    int search_by_surname_and_age(const struct person data[], 
                                  const size_t size,
                                  const char surname[], 
                                  const char name[]){
      for(size_t idx=0; idx < size; idx++){
          if(strcmp(data[idx].surname, surname) == 0 
             && strcmp(data[idx].name, name) == 0){
              return idx;
          }
      }
      return -1;
    }
  • Celý kód bude teda vyzerať nasledovne:

    #include <stdio.h>
    #include <string.h>
    
    // structure representing a person
    struct person {
        char name[20];
        char surname[30];
        char sex;
        // int age;
    };
    
    // Search person by surname in the list of data of given size
    int search_by_surname(const struct person data[], 
                          const size_t size, 
                          const char surname[]){
        for(size_t idx=0; idx < size; idx++){
            if(strcmp(data[idx].surname, surname) == 0){
                return idx;
            }
        }
        return -1;
    }
    
    // Search person by name and surname in the list of data 
    // of given size
    int search_by_surname_and_age(const struct person data[], 
                                  const size_t size,
                                  const char surname[], 
                                  const char name[]){
        for(size_t idx=0; idx < size; idx++){
            if(strcmp(data[idx].surname, surname) == 0 
               && strcmp(data[idx].name, name) == 0){
                return idx;
            }
        }
        return -1;
    }
    
    // Print person object on screen
    void print_person(struct person person){
        printf("%s %s is %c.\n",
            person.name, person.surname, person.sex
        );
    }
    
    int main(){
        // read the nr of persons
        printf("Enter the number of persons: ");
        int size;
        scanf("%d", &size);
    
        // declare list of persons
        struct person list[size];
    
        // populate list
        for(size_t i = 0; i < size; i++){
            printf("Enter %zu person: ", i);
            scanf("%s %s %c", 
                  list[i].name, list[i].surname, &list[i].sex);
        }
    
        // traverse the list
        for(size_t i = 0; i < size; i++){
            printf("%zu: ", i);
            print_person(list[i]);
        }
    
        // search
        char *f_surname = "Plum";
        int f_idx = search_by_surname(list, size, f_surname);
        printf("Position of %s is %d\n", f_surname, f_idx);
    }

Standard Library

  • (slide) V praxi však nebudete vždy nutne potrebovať písať vlastné funkcie pre vyhľadanie prvkov alebo pre zotriedenie zoznamu prvkov. Proste využijete funkcie, ktoré sú už pre tento účel pripravené.

  • V tomto prípade môžeme napríklad využiť funkciu bsearch() z knižnice stdlib.h, ktorá implementuje tzv. binárne vyhľadávanie. A už z predmetu Základy algoritmizácie a programovania viete, že v porovnaní s lineárnym vyhľadávaním, má binárne vyhľadávanie lepšiu zložitosť.

  • (slide) Pokúsme sa porovnať vlastnosti oboch algoritmov na vyhľadávanie:

    Lineárne vyhľadávanie Binárne vyhľadávanie
    zložitosť \[\mathcal{O}(n)\] \[\mathcal{O}(\log_2{}(n))\]
    najlepší prípad \[\mathcal{O}(1)\] \[\mathcal{O}(1)\]
    najhorší prípad \[\mathcal{O}(n)\] \[\mathcal{O}(\log_{2}(n))\]
    prerekvizity žiadne zotriedený zoznam
    prístup iteratívny rozdeľ a panuj
  • (slide) Pozrime sa teraz na porovnanie cez čísla. V nasledujúcej tabuľke je vidieť porovnanie oboch algoritmov. Tu je vidieť, na koľký pokus sme schopní nájsť hľadaný prvok pri použití oboch algoritmov vzhľadom na množstvo prvkov v zozname/poli. Jasne vidieť, že binárnym vyhľadávaním sme schopní hľadaný prvok nájsť za výrazne menší počet krokov ako v prípade lineárneho vyhľadávania.

    \[n\] 10 100 1 000 10 000 100 000
    \[\mathcal{O}(n)\] 10 100 1 000 10 000 100 000
    \[\mathcal{O}(\log_2{}(n))\] 3.3 6.6 10 13.3 16.6
  • (slide) Porovnať môžeme obe zložitosti aj graficky. Na x-ovej osi sa nachádza počet prvkov a na y-ovej osi sa nachádza počet krokov/prístupov, ktoré potrebujeme vykonať na nájdenie hľadaného prvku. Ako je vidieť, zložitosť lineárneho vyhľadávanialineárny priebeh, zatiaľ čo zložitosť binárneho vyhľadávanialogaritmický priebeh.

    Linear vs Binary Search

Sorting lists with qsort()

  • Ak však chceme binárne vyhľadávanie použiť, prvky musia byť už zotriedené. V opačnom prípade fungovať nebude. V štandardnej knižnici sa nachádza implementácia algoritmu triedenia quick sort, ktorú môžeme využiť zavolaním funkcie qsort().

  • (slide) Deklarácia funkcie qsort() vyzerá nasledovne:

    void qsort(void *base, size_t nmemb, size_t size, 
               int (*compar)(const void *, const void *));
  • Význam jednotlivých parametrov je nasledovný:

    • base - začiatok zoznamu/poľa
    • nmemb - počet prvkov zoznamu/poľa
    • size - veľkosť v pamäti, ktorú zaberá jeden prvok zoznamu/poľa
    • compar - adresa na funkciu, ktorá porovná dva prvky zoznamu navzájom
  • (slide) Začneme teda tým, že vytvoríme funkciu cmp_by_surname(), ktorá umožní porovnať dve premenné typu struct person na základe ich priezviska. Funkcia vráti hodnotu:

    • menšiu ako 0, ak ľavé priezvisko (prvý parameter funkcie) je v poradí pred pravým priezviskom (druhým parametrom funkcie)
    • väčšiu ako 0, ak sú priezviská v opačnom poradí
    • rovnú 0, ak budú priezviská rovnaké
  • Výsledná podoba funkcie cmp_by_surname() bude vyzerať nasledovne:

    int cmp_by_surname(const void* p1, const void* p2){
        struct person* person1 = (struct person*)p1;
        struct person* person2 = (struct person*)p2;
    
        int result = strcmp(person1->surname, person2->surname);
        // printf("comparing %s vs %s = %d\n", 
        //        person1->surname, person2->surname, result);
        return result;
    }
  • Následne už len aktualizujeme výsledný kód z minulého týždňa tak, že necháme výsledný zoznam usporiadať pomocou funkcie qsort() a takto ho usporiadaný vypíšeme na obrazovku:

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    // structure representing a person
    struct person {
        char name[20];
        char surname[30];
        char sex;
        // int age;
    };
    
    // Search person by surname in the list 
    // of data of given size
    int search_by_surname(const struct person data[], 
                          const size_t size, 
                          const char surname[]){
        for(size_t idx=0; idx < size; idx++){
            if(strcmp(data[idx].surname, surname) == 0){
                return idx;
            }
        }
        return -1;
    }
    
    // Print person object on screen
    void print_person(const struct person person){
        printf("%s %s is %c.\n",
            person.name, person.surname, person.sex
        );
    }
    
    int cmp_by_surname(const void* p1, const void* p2){
        struct person* person1 = (struct person*)p1;
        struct person* person2 = (struct person*)p2;
    
        return strcmp(person1->surname, person2->surname);
    }
    
    int main(){
        // read the nr of persons
        printf("Enter the number of persons: ");
        int size;
        scanf("%d", &size);
    
        // declare list of persons
        struct person list[size];
    
        // populate list
        for(size_t i = 0; i < size; i++){
            printf("Enter %zu person: ", i);
            scanf("%s %s %c", 
                  list[i].name, list[i].surname, &list[i].sex);
        }
    
        printf("\n");
    
        // traverse the list
        for(size_t i = 0; i < size; i++){
            printf("%zu: ", i);
            print_person(list[i]);
        }
    
        // sort
        qsort(list, size, sizeof(struct person), cmp_by_surname);
    
        // traverse the list
        for(size_t i = 0; i < size; i++){
            printf("%zu: ", i);
            print_person(list[i]);
        }
    }

Searching with bsearch()

  • (slide) Deklarácia funkcie bsearch(), ktorá implementuje binárne vyhľadávanie nad zoznamom/poľom, vyzerá nasledovne:

    void *bsearch(const void *key, const void *base, 
                  size_t nmemb, size_t size, 
                  int (*compar)(const void *, const void *));
  • Význam jednotlivých parametrov je nasledovný:

    • key - adresa prvku, ktorý má nastavené príslušné položky, na základe ktorých chceme vyhľadávať
    • base - začiatok zoznamu/poľa
    • nmemb - počet prvkov zoznamu/poľa
    • size - veľkosť v pamäti, ktorú zaberá jeden prvok zoznamu/poľa
    • compar - adresa na funkciu, ktorá porovná dva prvky zoznamu navzájom
  • Ako funkciu pre porovnanie dvoch prvkov môžeme použiť rovnakú funkciu ako pre zotriedenie zoznamu. Takže už len rozšírime predchádzajúcu verziu kódu o nasledujúci fragment:

    // search
    struct person key = { .surname = "Gray" };
    struct person* result = bsearch(&key, list, size, 
                                    sizeof(struct person), 
                                    cmp_by_surname);
    
    if(result != NULL){
        printf("founded %s %s, who is %c\n", 
               result->name, result->surname, result->sex);
    }else{
        printf("entry not found\n");
    }

Conclusion

  • Na tejto a minulej prednáške si predstavili štruktúry, štruktúrované údajové typy a prácu s nimi. Ukázali sme si, ako je možné takto reprezentované údaje ukladať do súboru (serializovať) a zo súboru ich načítavať (deserializovať). Dnes sme si ukázali, ako je možné v zoznamoch obsahujúcich štruktúrované údaje vyhľadávať a ako je možné ich triediť.

  • Aj napriek tomu, že organizácia údajov do štruktúr prináša výhody, vytváranie zoznamov spôsobom, ktorý sme si ukázali, nie je vždy úplne praktický. Stále je tu jedno obrovské obmedzenie - musíme poznať počet prvkov zoznamu pred jeho vytvorením a počas jeho existencie ho nesmieme meniť (minimálne zväčšovať).

  • To, ako sa popasovať s týmto problémom si ukážeme na niektorej z ďalších prednášok.