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

# Thread: Counting basic operations in this Selection Sort

1. ## 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.

2. ## 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. ## 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.