-1

I'm studying this book since yesterday and after I've understood and applied the first algorithm, I tried to go on my own and look in a different way. Here's, in Java, the shown algorithm :

public static int[] sort(int[] array)
{
    for(int i = 1; i < array.length; i++){
        int value = array[i];
        int j = i - 1;

        while(j >= 0 && array[j] > value){
            array[j + 1] = array[j];
            j--;
        }
        array[j+1] = value;
    }

    return array;
}

And here is mine :

public static int[] sortb(int[] array)
{
    for(int i = 0; i < array.length; i++){
        int value = array[i];
        int j = i;

        while(j < array.length && value > array[j]){
            array[j] = array[j + 1];
            j++;
        }

        array[j] = value;
    }

    return array;
}

For 1 million of function call for each, I got 32 ms for the first and 25 ms for the second. I'm still beginning with algorithms, so I have no idea of the meaning.

RubioRic
  • 2,442
  • 4
  • 28
  • 35
Despirithium
  • 309
  • 5
  • 13
  • It doesn't really have any meaning. I'd spend more time concentrating on the algorithms and less on the measuring of their speed. If you don't know how to do measurement correctly, you can get all sorts of results and waste your time trying to find meaning where there is no meaning. – Kayaman Apr 12 '16 at 09:59
  • @FarazDurrani I'm pretty sure when professors teach algorithms, they're more interested in `Big O` than milliseconds gotten by bad measurements. – Kayaman Apr 12 '16 at 10:10
  • I'm not working with professor, but on my own – Despirithium Apr 12 '16 at 10:13
  • Well i tried with arrays of 2 000 000 elements, the second algorithm make it right in 6ms The first one takes takes more than a minute. – Despirithium Apr 12 '16 at 10:24
  • Possible duplicate of [How do I write a correct micro-benchmark in Java?](http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java) –  Apr 12 '16 at 10:27
  • I get 3998 ms in `sort` and 2 ms in `sortb` with 200,000 random int array on my local machine. Here the ideone's [result](http://ideone.com/qn0piI). – Nier Apr 12 '16 at 11:05

2 Answers2

6

I found why your sort is so much faster than original one: Because you are not doing sort at all.

In your code

    int value = array[i];
    int j = i;

    while(j < array.length && value > array[j]) { ... }

Because j = i, so value == array[j] before you get into the while loop, and thus your while loop body will never execute. Your sort result will be wrong. That's the main reason why your code is extremely faster.

Nier
  • 638
  • 7
  • 15
5

In my experience (read student's experience) this kind of different values have little meaning.

Maybe you had a background process that took / released a bit more of resources from one to another.

Maybe the specific case you tried to arrange was better for one of the algorythms than the other.

Maybe, if you used different random arrays, one of them was closer to be sorted than the other..

To have good measures, you usually have to do a lot of tests, not only one. For example, generate 1k arrays of 10k elements each and sort each of this array with both algorythms..

Anyway, sometimes specific features of a language or a compiler can generate different results for algorythms with theoretically the exact same complexity (one example: once I noticed in C++ if you traverse a 2-dimensional array first by columns and then by rows, you will have a very different speed than if you do it the other way around; but I don't remember which one was faster tbh).

dquijada
  • 1,697
  • 3
  • 14
  • 19
  • 1
    If you mean `a[10][10]` such a C++ 2-dimensional array, it's will be faster if you traverse with outer loop is `a[0-9]` and inner loop is `a[i][0-9]` because `a[i][0-9]` should be sequential placed in memory. – Nier Apr 12 '16 at 10:51