# Counting basic operations in this Selection Sort

• February 1st, 2012, 05:26 PM
Keiran
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?

Code Java:

```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.
• February 1st, 2012, 05:56 PM
rchrispink3913
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...
• February 1st, 2012, 06:16 PM
copeg
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.