Why the second algorithm consume almost the same time as the first one?

This is the answer explained by a professor in my department:

"The reason for your strange results is that you are miscounting copies in both versions of the algorithm. In Algorithm 2, for example, your swap should be counted as 2 copies, not 3.

Real time measurements on a computer can be unreliable: they can be influenced by the existence of other processes running concurrently with the process that you are trying to measure. Software engineers get over this by running the process repeatedly with the same data, and taking the average time."

I still have some questions now, he said I miscounting copies in both algorithm, and in algorithm2 the copies of swap should be 2 rather than 3, I don't know why the following code counts 2 times but not 3?

{

int a = b;

b = c;

c = a

}

What's more, what is the step in which I miscounted the copies in Algorithm1?

Thanks a lot , guys, waiting for your ideas :P

K_Ghosta at 2007-7-16 23:55:25 >

Your Solution !!!

public class SelectionSort {

private static int selectionSortCompCounter = 0;

private static int selectionSortCopyCounter = 0;

static void selectionSort(Comparable[] a, int left, int right) {

int iIncrement = 0;

int iAssignment = 0;

int iComparison = 0;

int iRetrieve = 0;

for (int l = left; l < right; l++) {

iIncrement++;

iComparison++;

int p = l;

iAssignment++;

Comparable least = a[p];

iAssignment++;

iRetrieve++;

for (int k = l + 1; k <= right; k++) {

iIncrement++;

iComparison++;

int comp = a[k].compareTo(least);

iAssignment++;

iComparison++;

iRetrieve++;

// Increase comparions counter by 1.

selectionSortCompCounter++;

iIncrement++;

if (comp < 0) {

iComparison++;

p = k;

iAssignment++;

least = a[p];

iAssignment++;

iRetrieve++;

// Increase copies counter by 2;

selectionSortCopyCounter += 2;

iAssignment++;

iIncrement++;

}

}

if (p != l) {

iComparison++;

a[p] = a[l];

iAssignment++;

iRetrieve++;

iRetrieve++;

a[l] = least;

iAssignment++;

iRetrieve++;

// Increase copies counter by 2;

selectionSortCopyCounter += 2;

iAssignment++;

iIncrement++;

}

}

System.out.println("Comparison : " + iComparison);

System.out.println("Assigment : " + iAssignment);

System.out.println("Increment : " + iIncrement);

System.out.println("Retrieval : " + iRetrieve);

}

//The Second Selection Sort Algorithm

static void selectionSort2(Comparable[] a, int left, int right) {

int iIncrement = 0;

int iAssignment = 0;

int iComparison = 0;

int iRetrieve = 0;

for (int l = left; l < right; l++) {

iIncrement++;

iComparison++;

int p = l;

iAssignment++;

for (int k = l + 1; k <= right; k++) {

iIncrement++;

iComparison++;

int comp = a[k].compareTo(a[p]);

iAssignment++;

iComparison++;

iRetrieve++;

iRetrieve++;

// Increase comparions counter by 1.

selectionSortCompCounter++;

iIncrement++;

if (comp < 0) {

iComparison++;

p = k;

iAssignment++;

selectionSortCopyCounter += 1;

iIncrement++;

iAssignment++;

}

}

if (p != l) {

iComparison++;

Comparable temp = a[p];

iAssignment++;

iRetrieve++;

a[p] = a[l];

iAssignment++;

iRetrieve++;

iRetrieve++;

a[l] = temp;

iAssignment++;

iRetrieve++;

selectionSortCopyCounter += 3;

iIncrement++;

iAssignment++;

}

}

System.out.println("Comparison : " + iComparison);

System.out.println("Assigment : " + iAssignment);

System.out.println("Increment : " + iIncrement);

System.out.println("Retrieval : " + iRetrieve);

}

static String random(int m) {

char[] d = new char[m];

for (int i = 0; i < m; i++) {

d = (char) (10 * Math.random() + '0');

}

return new String(d);

}

static String[] generateRandom(int n) {

String[] random = new String[n];

for (int i = 0; i < n; i++) {

random = "" + random(i);

}

return random;

}

public static void main(String[] args) {

final int RANGE = 10000;

String[] string = generateRandom(RANGE);

String[] string2 = new String[RANGE];

System.arraycopy(string, 0, string2, 0, string.length);

selectionSortCompCounter = 0;

selectionSortCopyCounter = 0;

long time1 = System.currentTimeMillis();

selectionSort(string, 0, RANGE - 1);

long time2 = System.currentTimeMillis();

System.out.println(selectionSortCompCounter + " " + selectionSortCopyCounter);

System.out.println("Time consumed: " + (time2 - time1));

selectionSortCompCounter = 0;

selectionSortCopyCounter = 0;

long time3 = System.currentTimeMillis();

selectionSort2(string2, 0, RANGE - 1);

long time4 = System.currentTimeMillis();

System.out.println(selectionSortCompCounter + " " + selectionSortCopyCounter);

System.out.println("Time consumed: " + (time4 - time3));

}

}

Algorithm 1::

Comparison : 100088296

Assigment : 50279889

Increment : 100088296

Retrieval : 50113276

49995000 176594

Time consumed: 7406

Algorithm 2::

Comparison : 100088296

Assigment : 50201573

Increment : 100088296

Retrieval : 100029960

49995000 108277

Time consumed: 7156

Please check the retrieval and comparison ....

Basic Assembly Instruction ...

Regards...

myraid77a at 2007-7-16 23:55:25 >