Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 3 of 3

Thread: Counting basic operations in this Selection Sort

  1. #1
    Junior Member
    Join Date
    Feb 2012
    Posts
    1
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Question Counting basic operations in this Selection Sort

    Hi, first of all I'm new in this forum and I'm new at programming. My homework assignment is to use a Selection Sort algorithm and count how many basic operations it takes to sort 100, 1000, 10000, 100000 randomly generated elements. So I got that part of the code working as it creates files and sorts the elements. What I am having problems is with the counting of the fundamental operations. The Big O notation of Selection Sort is n^2. If I sort 100 then the number of fundamental operations should be 10000 or something close to it. Instead I get 16177. What exactly is considered a basic operation? +-*/, comparisons? Am I counting something that shouldn't be counting?

    import java.util.*;
    import java.io.*;
     
    public class SelectionSortarray
    {
      static  int counter = 0;
     
      public static void main(String a[]) throws IOException
      {
     
        int[] array = new int[100];
        int[] array2 = new int[1000]; 
        int[] array3 = new int[10000]; 
        int[] array4 = new int[100000]; 
     
        PrintWriter pw = new PrintWriter(new FileWriter("SS1.txt"));
        PrintWriter pw2 = new PrintWriter(new FileWriter("SS2.txt"));
        PrintWriter pw3 = new PrintWriter(new FileWriter("SS3.txt"));
        PrintWriter pw4 = new PrintWriter(new FileWriter("SS4.txt"));
     
        Random r = new Random();
     
        for (int idx = 1; idx <= array.length; ++idx) // Will generate random numbers from 1 - 100
        {
          int randomInt = r.nextInt(100);
     
          array[idx - 1] = randomInt;
        }
        selection_srt(array, array.length);
     
        System.out.println("Fundamental operations for 100 elements: "  + counter);
     
        for(int in = 0; in < array.length; in++)
        {
          pw.println(array[in]);
        }
        pw.close();
     
        for (int idx = 1; idx <= array2.length; ++idx) 
        {
          int randomInt = r.nextInt(100);
     
          array2[idx - 1] = randomInt;
        }
        selection_srt(array2, array2.length);
        System.out.println("Fundamental operations for 1000 elements: "  + counter);
     
        for(int in = 0; in < array2.length; in++)
        {
          pw2.println(array2[in]);
        }
        pw2.close();
     
        for (int idx = 1; idx <= array3.length; ++idx) 
        {
          int randomInt = r.nextInt(100);
     
          array3[idx - 1] = randomInt;
        }
        selection_srt(array3, array3.length);
        System.out.println("Fundamental operations for 10000 elements: "  + counter);
     
        for(int in = 0; in < array3.length; in++)
        {
          pw3.println(array3[in]);
        }
        pw3.close();
     
        for (int idx = 1; idx <= array4.length; ++idx)
        {
          int randomInt = r.nextInt(100);
     
          array4[idx - 1] = randomInt;
        }
        selection_srt(array4, array4.length);
     
        System.out.println("Fundamental operations for 100000 elements: "  + counter);
     
        for(int in = 0; in < array4.length; in++)
        {
          pw4.println(array4[in]);
        }
        pw4.close();
     
      }
     
      public static void selection_srt(int array[], int n){
        counter += 3; // For x, x<n, x++
        for(int x=0; x<n; x++){
          int index_of_min = x;
          counter += 1; // for index_of_min
          for(int y=x; y<n; y++){
            counter += 3; // y=x, y<n, y++
            if(array[index_of_min]<array[y]){
              index_of_min = y;
              counter += 2; // array<array[y]
            }
          }
          int temp = array[x];
          counter += 1; // temp = array[x]
          array[x] = array[index_of_min];
          counter += 1; // array[x] = array[index_of_min]
          array[index_of_min] = temp;
          counter += 1; // array[index_of_min] = temp
        }
      }
    }

    It prints out to the screen this,

    "Fundamental operations for 100 elements: 16177
    Fundamental operations for 1000 elements: 1529746
    Fundamental operations for 10000 elements: 151668395
    Fundamental operations for 100000 elements: -2026816714"

    Along with this can anyone tell me why I get a negative number with the last one? If anyone could help I would greatly appreciate it.
    Last edited by Keiran; February 1st, 2012 at 06:28 PM.


  2. #2
    Junior Member
    Join Date
    Jan 2012
    Posts
    10
    My Mood
    Lurking
    Thanks
    1
    Thanked 2 Times in 2 Posts

    Default Re: Counting basic operations in this Selection Sort

    Hi, a possible issue with that could be that you are using an integer data type for a very large number...

  3. #3
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,320
    Thanks
    181
    Thanked 833 Times in 772 Posts
    Blog Entries
    5

    Default Re: Counting basic operations in this Selection Sort

    First, think about the time complexity of the sorting algorithm...this would be based upon how much looping you have going on there. First loop is n, next is n-1, and so on...how many times does it ultimately loop ? (hint: n(n+1)/2) Now use the count variable to tally up how many times it loops. Does it equal what you did above? (Note: the other calculations are negligible in Big O notation). And don't forget to reset the count every time you call the method.

Similar Threads

  1. How do I sort strings without using the sort method?
    By mjballa in forum What's Wrong With My Code?
    Replies: 2
    Last Post: December 4th, 2011, 03:27 PM
  2. Selection sort code needs reverse
    By steel55677 in forum Algorithms & Recursion
    Replies: 7
    Last Post: September 27th, 2011, 06:40 AM
  3. Basic Java Sorting Algorithm (Selection/Insertion) help
    By Arte7 in forum Algorithms & Recursion
    Replies: 5
    Last Post: August 22nd, 2011, 01:38 PM
  4. Help with OS operations!
    By benglish in forum Java Theory & Questions
    Replies: 8
    Last Post: April 1st, 2011, 06:32 AM
  5. bubble sort and selection sort on strings
    By Sir Saula in forum What's Wrong With My Code?
    Replies: 5
    Last Post: July 3rd, 2010, 09:44 AM