Matematické Fórum

Stačilo by mi ukázat jak udělat tu 3, tu bych mohl pak nějak spatlat.A potřeboval bych ještě jeden ale u ostatních si nejsem vůbec jistej jak na to...

↑ Shaker:
Konderla?

1) http://blog.codebeach.com/2008/09/sorti … -in-c.html

2) Prostuduj tohle http://en.wikipedia.org/wiki/Binary_search_tree nebo podobný příklad

3) Nejjednodušší postup je seřadit pole podle nějakého algoritmu a vypsat prvních n čísel.

4) Jednosměrný seznam: http://www.linuxsoft.cz/article.php?id_article=868  Obousměrný si buď vygoogli nebo napiš podle tohoto, princip je stejný.

Pleas helpne mi s tim nekdo?

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


void BubbleSort(int a[], int array_size)
{
     int i, j, temp;
     for (i = 0; i < (array_size - 1); ++i)
     {
          for (j = 0; j < array_size - 1 - i; ++j )
          {
               if (a[j] > a[j+1])
               {
                    temp = a[j+1];
                    a[j+1] = a[j];
                    a[j] = temp;
               }
          }
     }
}

void SelectionSort(int a[], int array_size)
{
     int i;
     for (i = 0; i < array_size - 1; ++i)
     {
          int j, min, temp;
          min = i;
          for (j = i+1; j < array_size; ++j)
          {
               if (a[j] < a[min])
                    min = j;
          }

          temp = a[i];
          a[i] = a[min];
          a[min] = temp;
     }
}

void InsertionSort(int a[], int array_size)
{
     int i, j, index;
     for (i = 1; i < array_size; ++i)
     {
          index = a[i];
          for (j = i; j > 0 && a[j-1] > index; j--)
               a[j] = a[j-1];

          a[j] = index;
     }
}

void HeapSort(int a[], int root, int bottom)
{
     int maxchild, temp, child;
     while (root*2 < bottom)
     {
          child = root * 2 + 1;
          if (child == bottom)
          {
               maxchild = child;
          }
          else
          {
               if (a[child] > a[child + 1])
                    maxchild = child;
               else
                    maxchild = child + 1;
          }

          if (a[root] < a[maxchild])
          {
               temp = a[root];
               a[root] = a[maxchild];
               a[maxchild] = temp;
          }
          else return;

          root = maxchild;
     }
}






1) 6 druhů třídění (dalsi dve nevim...) - mam urcit(s cim si take nevim rady jak by to melo byt naspsano) :

- projdou vsechna trideni, zmeri cas a zjisti ktere bylo nejrychlejsi
-zadavani pole-muze uzivatel zadat nebo automaticky (to mozna jeste nejak dam dohromady)
-odebirani....
-rozhazeni pole

1) 6 druhů třídění (dalsi dve nevim...) - mam urcit(s cim si take nevim rady jak by to melo byt naspsano) :

- projdou vsechna trideni, zmeri cas a zjisti ktere bylo nejrychlejsi
-zadavani pole-muze uzivatel zadat nebo automaticky (to mozna jeste nejak dam dohromady)
-odebirani....
-rozhazeni pole

QuickSort:

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

void quickSort(int[], int, int);
int partition(int[], int, int);


int main()
{
    int a[10];
    double start, end;
   
    for(int i = 0; i < 10; i++)
    {
            a[i] = rand() % 9 + 1;           
    }
    putchar('\n');
    putchar('\n');

    start = clock();
    quickSort( a, 0, 10);
    end = clock();

    for(int i = 0; i < 10; i++)
    {           
            printf("%d ", a[i]);
    }   
   
    printf("\n\nDoba behu programu: %lf sec", (end - start) / CLOCKS_PER_SEC);
       
    getchar();
    getchar();

}



void quickSort(int a[], int l, int r)
{
   int j;

   if(l < r)
   {      
       j = partition(a, l, r);
       quickSort(a, l, j - 1);
       quickSort(a, j + 1, r);
   }   
}



int partition(int a[], int l, int r)
{
   int pivot = a[l], t;   
   int i = l;
   int j = r + 1;
       
   while(1)
   {
       do ++i; while(a[i] <= pivot && i <= r);
       do --j; while(a[j] > pivot);
      
       if(i >= j) break;
       t = a[i]; a[i] = a[j]; a[j] = t;
   }
   
   t = a[l]; a[l] = a[j]; a[j] = t;   
   return j;
}


Na měření času máš v C knihovnu time.h, tak se do ní podívej. Jinak takto malé časové intervaly jdou změřit např. makrem CLOCKS_PER_SEC - takže máš nějaký počáteční čas start a koncový end, uděláš rozdíl těchto časů (samozřejmě end - start) a vydělíš to tím makrem. Výše u QuickSortu to měření používám. Ale setřídění 10-ti prvkového pole tímto nezměříš, to je moc rychlé...pak jedině sáhnout po nějaké externí knihovně - na unixových systémech nejspíše gettimeofday.

Zadávání pole - tím myslíš co? Že uživatel zadá délku pole? Nebo že zadá jednotlivé hodnoty? Nebo obojí?

Odebírání pole - opět trochu upřesni, nevím přesně co tím myslíš a nerad bych se rozepisoval o něčem jiném.

Rozházení pole: já bych to realizoval takto (všímej si hlavně fce rozhod):

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

#define MAX 10

#define cisti() while(getchar() != '\n')

void napln_setrid(int *);
void rozhod(int *);

int main()
{
    int pole[10]; 
   
    napln_setrid(pole); 
    rozhod(pole);   
   
    cisti();
    getchar();
    return 0;
}

void napln_setrid(int *pole)
{
    int help, j;
     
    for(int i = 0; i < MAX; i++)
    {
            pole[i] = rand() % 9;           
    }
   
    for(int i = 0; i < MAX - 1; i++)
    {             
           if(pole[i] < pole[i + 1])
           {
                    help = pole[i];
                    pole[i] = pole[i + 1];
                    pole[i + 1] = help;
                   
                    j = i;
                   
                    while(pole[j] > pole[j - 1])
                    {
                                  help = pole[j];
                                  pole[j] = pole[j - 1];
                                  pole[j - 1] = help;
                                 
                                  j--;
                    }                                                                     
           }
    } 
}

void rozhod(int *pole)
{
     int first, second, temp, j = 0;
     
     while(j != 10)
     {
              first = rand() % 9;
              second = rand() %9;
              j++;
             
              temp = pole[first];
              pole[first] = pole[second];
              pole[second] = temp;                         
     }   
}

EDIT: pokud ještě nemáš obousměrně zřetězený seznam (není můj), tak tady: http://paul27.ic.cz/programming/c/spojovy_seznam_2.txt akorát já bych to udělal do fcí a ne takhle prasácky všechno do main, ale vyčíst se to z toho dá, je tam i jakýsi komentář