14. cvičení

Seřazení prvků pole dle velikosti

Nejjednodušší způsob, jak seřadit prvky pole dle velikosti, je použít jeden z následujících algoritmů:

• řazení výběrem
• řazení vkládáním
• bublinkové řazení

Analýze těchto a dalších řadících algoritmů se budete věnovat v předmětu Základy algoritmizace (ZALG).

Probrané příklady

1. Seřazení prvků pole dle velikosti pomocí jednoduchého algoritmu. Hodnoty načtěte z terminálu nebo ze souboru.

   Následující program provede řazení výběrem pomocí funkce argmax:

   #include <stdio.h>
   
   int argmax(int n, float* pole)
   {
       int vysledek = 0;
       for (int i = 0; i < n; i++) {
           if (pole[i] > pole[vysledek])
               vysledek = i;
       }
       return vysledek;
   }
   
   void serad_pole(int n, float* pole)
   {
       for (int i = 0; i < n - 1; i++) {
           int m = argmax(n - i, pole + i);
           // prehodit pole[i] a pole[m + i]
           float pomocna = pole[i];
           pole[i] = pole[m + i];
           pole[m + i] = pomocna;
       }
   }
   
   int main()
   {
       printf("Zadej pocet cisel: ");
       int n;
       scanf("%d", &n);
   
       // pole o velikosti n
       float pole[n];
   
       // nacist n cisel do pole
       for (int i = 0; i < n; i++) {
           scanf("%f", &pole[i]);
       }
   
       serad_pole(n, pole);
   
       // vypis n cisel
       for (int i = 0; i < n; i++) {
           printf("%f ", pole[i]);
       }
       printf("\n");
   
       return 0;
   }
   

2. Seřazení tabulky (histogramu) počtu výskytů jednotlivých znaků v souboru (viz příklad z předchozího cvičení).

   Oproti předchozímu příkladu v histogramu nestačí seřadit pole s počty výskytů každého znaku, protože bychom ztratili informaci o tom, kterému znaku daný počet výskytů přísluší. Problém lze vyřešit dvěma způsoby:

   1. Nejjednodušší způsob je vytvořit druhé pole znaků a při řazení měnit pořadí prvků v obou polích, aby vždy platilo, že počet výskytů \(i\)-tého prvku nového pole je \(i\)-tý prvek původního pole.

      #include <stdio.h>
      
      int argmax(int n, int* pole)
      {
          int vysledek = 0;
          for (int i = 0; i < n; i++) {
              if (pole[i] > pole[vysledek])
                  vysledek = i;
          }
          return vysledek;
      }
      
      void serad_pole(int n, int* pole, char* znaky)
      {
          for (int i = 0; i < n - 1; i++) {
              int m = argmax(n - i, pole + i);
              // prehodit pole[i] a pole[m + i]
              int pomocna = pole[i];
              pole[i] = pole[m + i];
              pole[m + i] = pomocna;
              // prehodit znaky[i] a znaky[m + i]
              char znak = znaky[i];
              znaky[i] = znaky[m + i];
              znaky[m + i] = znak;
          }
      }
      
      int main()
      {
          FILE* soubor = fopen("M:\\ZPRO 2019\\vstup.txt", "r");
          if (soubor == NULL) {
              printf("chyba otevreni souboru\n");
              return 1;
          }
      
          int pocty_vyskytu[256];
          for (int i = 0; i < 256; i++)
              pocty_vyskytu[i] = 0;
      
          // dokud nedojdu na konec souboru
          while (!feof(soubor)) {
              // nacist znak
              int znak = fgetc(soubor);
              // pricist 1 v poli
              if (znak != EOF)
                  pocty_vyskytu[znak]++;
          }
      
          fclose(soubor);
      
          char znaky[256];
          for (int i = 0; i < 256; i++)
              znaky[i] = i;
          serad_pole(256, pocty_vyskytu, znaky);
      
          // vypis tabulky
          for (int i = 0; i < 256; i++) {
              if (pocty_vyskytu[i] == 0)
                  break;
              printf("%d. nejcastejsi znak je '%c', pocet vyskytu: %d\n", i + 1, znaky[i], pocty_vyskytu[i]);
          }
      
          return 0;
      }
      

   2. Alternativní způsob opět vyžaduje vytvořit další pole, ale nyní ne znaků, ale indexů. Při řazení budeme měnit pouze pořadí indexů a pořadí hodnot v původním poli (počty výskytů) zůstane nezměněné. Interpretace indexů bude taková, že \(i\)-tý prvek pole indexů udává číslo znaku s \(i\)-tým nejvyším počtem výskytů. Příslušný počet výskytů najdeme v původním poli pomocí čísla daného znaku.

      #include <stdio.h>
      
      int argmax_2(int n, int* pole, int* indexy)
      {
          int vysledek = 0;
          for (int i = 0; i < n; i++) {
              if (pole[indexy[i]] > pole[indexy[vysledek]])
                  vysledek = i;
          }
          return vysledek;
      }
      
      void serad_pole_2(int n, int* pole, int* indexy)
      {
          for (int i = 0; i < n - 1; i++) {
              int m = argmax_2(n - i, pole, indexy + i);
              // prehodit indexy[i] a indexy[m + i]
              int znak = indexy[i];
              indexy[i] = indexy[m + i];
              indexy[m + i] = znak;
          }
      }
      
      int main()
      {
          FILE* soubor = fopen("M:\\ZPRO 2019\\vstup.txt", "r");
          if (soubor == NULL) {
              printf("chyba otevreni souboru\n");
              return 1;
          }
      
          int pocty_vyskytu[256];
          for (int i = 0; i < 256; i++)
              pocty_vyskytu[i] = 0;
      
          // dokud nedojdu na konec souboru
          while (!feof(soubor)) {
              // nacist znak
              int znak = fgetc(soubor);
              // pricist 1 v poli
              if (znak != EOF)
                  pocty_vyskytu[znak]++;
          }
      
          fclose(soubor);
      
          int indexy[256];
          for (int i = 0; i < 256; i++)
              indexy[i] = i;
          serad_pole_2(256, pocty_vyskytu, indexy);
      
          // vypis tabulky
          for (int i = 0; i < 256; i++) {
              if (pocty_vyskytu[indexy[i]] == 0)
                  break;
              printf("%d. nejcastejsi znak je '%c', pocet vyskytu: %d\n", i + 1, indexy[i], pocty_vyskytu[indexy[i]]);
          }
      
          return 0;
      }