Thread: 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.

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.