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ů:

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

Last updated: Wed 13 November 2019