java


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 2 of 2

Thread: java

  1. #1
    Join Date
    Oct 2004
    Posts
    2

    java

    If someone can help me with this, i'll really appreciate it.

    I'm doing this project where I have to show the complexity analysis of each sorting algorithm.

    I've created the insertionSort algorithm..

    public static void insertionSort( int[] num )
    {
    int i, j ;

    for( i = 0; i < num.length; i++)
    {
    int index = num[i];

    j = i;

    while ((j > 0) && (num[j-1] > index))
    {
    num[j] = num[j-1];
    j = j - 1;
    }
    num[j] = index;


    }

    how would i go about printing out the work & work/n^2 for this sorting algorithm using an array storing random integers..

  2. #2
    Join Date
    Oct 2004
    Location
    UK
    Posts
    12
    You need to define what a unit of work is, i.e. how you are going to measure the work. Usually its either the time taken for computation, or each operation performed in the algorithm is assigned a unit of work. I suspect you mean the latter. In which case, why not just have an int, which is initially zero, which you increment each time 'a unit of work' is done? For example, increment this work counter each time a variable has its value assigned, a variable is incremented, a calculation is performed, etc. Then its just a matter of figuring out n^2 (in this case, num.length^2)...

    E.g.:
    Code:
    public static void insertionSort( int[] num )
    {
        int i, j;
        int workCount = 0;
        int n2;
    
        for(i = 0; i < num.length; i++)
        {
            int index = num[i];
            j = i;
            
            /*
                comparison, increment, 2x assignment = 4 ops
            */
            
            workCount += 4
            
            while ((j > 0) && (num[j-1] > index))
            {
                num[j] = num[j-1];
                j = j - 1;
             
                 /*
                     2x comparison, 3x decrement, 2x assignment = 7 ops
                 */   
                 
                 work += 7
            }
            
            num[j] = index;
            workCount++;
        }
        
        n2 = num.length * num.length;
        System.out.println("work = " + workCount + ", work/n^2 = " + workCount/n2);
    }
    Although you could interpret what constitutes a 'work unit' differently to that...

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center