#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2013
    Posts
    10
    Rep Power
    0

    How to find the numbers of iteration,comparisons and permutation?


    Here is a part of my program about sorting with bubble,selection,insertion,shell and quick sort:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <conio.h>
    #include <time.h>
    
    
    void sort_bubble(int tablou[], int dim)
    {
    int temp,i,j;
    for (i=0; i<dim; i++)
    for (j=0; j<dim; j++)
    if (tablou[i] < tablou[j])
    {
    temp=tablou[i];
    tablou[i]=tablou[j];
    tablou[j]=temp;
    }
    }
    
    
    void sort_insert(int tablou[],int dim)
    {
        int temp;
        int i,j;
        for (i=0; i<dim;i++)
        for (j=i+1; j<dim; j++)
        if (tablou[i] >tablou[j])
        
        {
            temp=tablou[i];
            tablou[i]=tablou[j];
            tablou[j]=temp;
        }
    }
    
    void sort_select (int tablou[],int dim)
    {
        int i,j,min,locmin;
        for (i=0; i<dim; i++)
        {
            min=tablou[i];
            locmin=i;
            for (j=i+1; j<dim; j++)
            if(tablou[j]<min)
           
            {
                min=tablou[j];
                locmin=j;
            }
            tablou[locmin]=tablou[j];
            tablou[i]=min;
        }
    }
    
    void sort_shell (int tablou[],int dim)
    {
        int temp,gap,i,modificari;
        gap=dim/2;
        do{
        do{
        modificari=0;
        for (i=0; i<dim-gap;i++)
        if (tablou[i]>tablou[i+gap])
       
        {
            temp=tablou[i];
            tablou[i]=tablou[i+gap];
            tablou[i+gap]=temp;
            
            modificari=1;
           
        }
        }
        while (modificari);
        }
        while (gap=gap/2);
    }
    
    void swap(int *x,int *y)
    {
       int temp;
       temp = *x;
       *x = *y;
       *y = temp;
    }
    
    int choose_pivot(int i,int j )
    {
       return((i+j) /2);
    }
    
    
    
    void sort_rapid(int tablou[],int m,int n)
    {
       int key,i,j,k;
       if( m < n)
       {
          k = choose_pivot(m,n);
          swap(&tablou[m],&tablou[k]);
          key = tablou[m];
          i = m+1;
          j = n;
          while(i <= j)
          {
             while((i <= n) && (tablou[i] <= key))                 
                    i++;          
             while((j >= m) && (tablou[j] > key))
                    j--;
             if( i < j)
            
                    swap(&tablou[i],&tablou[j]);
          }
          
          swap(&tablou[m],&tablou[j]);
          
          sort_rapid(tablou,m,j-1);
          sort_rapid(tablou,j+1,n);
       }
    }
    How can i find the number of iteration, comparisons and permutations here ? :confused:
  2. #2
  3. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2013
    Posts
    25
    Rep Power
    0
    Originally Posted by path_finder5
    How can i find the number of iteration, comparisons and permutations here ? :confused:
    comparisons: easy, add a variable "comparison_count" and increment everytime u do the "<".

    iteration: first u need to define whats an iteration for u. easiest way: add a variable "iteration_count" and increment within the inner-most block of the loops.

    permutations: again, what u mean by permutation? everytime 2 values switch? then as before: add a variable "permuation_count" and increment everytime u do a "="...

    question answered, problem not solved. right?


    for easier reading you could make functions "permutate" and "compare" which do the permuation of 2 values / the comparions and increment in there.


    edit: wait, u already got that "swap", why dont u use that everywhere?
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2013
    Posts
    10
    Rep Power
    0
    thx. i'll try it
    edit: wait, u already got that "swap", why dont u use that everywhere?
    the program is just a "prototype", i'll fix everything when i'm done

    Comments on this post

    • mythos_ disagrees : so no need to fix problems for now? then why are u asking?
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2013
    Posts
    10
    Rep Power
    0
    mythos_ disagrees: so no need to fix problems for now? then why are u asking?
    once i calculate those numbers i'll proceed to make the program more easy to read . the program work and without that swamp function in each sorting method .
  8. #5
  9. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2013
    Posts
    25
    Rep Power
    0
    Originally Posted by path_finder5
    once i calculate those numbers i'll proceed to make the program more easy to read . the program work and without that swamp function in each sorting method .
    then u can do as i suggested. add counter-variable, and simply count every comparions, swap, iteration. i still dont get the problem... :confused:

IMN logo majestic logo threadwatch logo seochat tools logo