Difference in implementation for Insertion Sort

Question

I'm trying to practice programming by implementing different algorithms in different languages. I have two questions about a c++ implementation for insertion sort. First, why do most implementations in c++ include a length parameter, while others, such as java, just access the arrays length in the for loop? The next question is why do most implementations swap the variable inside the while loop, instead of just swapping at the very end? I have included two implementations to make it easier to talk about.

Java implementation:

void insertionSort(int[] arr) {
      int i, j, newValue;
      for (i = 1; i < arr.length; i++) {
            newValue = arr[i];
            j = i;
            while (j > 0 && arr[j - 1] > newValue) {
                  arr[j] = arr[j - 1];
                  j--;
            }
            arr[j] = newValue;
      }
}

C++ Implementation:

void insertionSort(int arr[], int length) {
      int i, j, tmp;
      for (i = 1; i < length; i++) {
            j = i;
            while (j > 0 && arr[j - 1] > arr[j]) {
                  tmp = arr[j];
                  arr[j] = arr[j - 1];
                  arr[j - 1] = tmp;
                  j--;
            }
      }
}

It seems like the c++ implementation will perform worse because of the swapping in the while loop. Specifically, is there a reason why c++ doesn't access array sizes directly and also is it necessary to implement the while loop like that, or is it just sloppy programming? Thank you in advance.

In java, each data structure is normally represented as object that carries information (i.e. the length).. in c++, this is mostly also true, except in the case of arrays; typically arrays are just raw pointers and it is up to you to pass in the length. Yes, I would say that the second one is simply not coded efficiently; but that is not because it is in c++, you could do this in either language — SystemFun, Dec 29 '15 at 03:57
When you say they are raw pointers, do you mean they just point to a part of the memory where the values are stored? And that is why you don't have the size of the array available, just the location? — mtorres, Dec 29 '15 at 04:02
exactly correct. In java, they are abstracted away, which can be done in c++ as well, but it is not the default per se. — SystemFun, Dec 29 '15 at 04:03

YoungHobbit · Accepted Answer · 2015-12-29T04:20:37.447

First, why do most implementations in c++ include a length parameter, while others, such as java, just access the arrays length in the for loop?

C++ does not have any direct method/field to access the length of the array. In Java the primitive arrays are treated as objects and have a length field, which can be used to determine the length of the array.

The next question is why do most implementations swap the variable inside the while loop, instead of just swapping at the very end?

Swapping the values in a loop or not is all about the implementation. You can always write a implementation which will shift the element and then in the end put the new element in the correct place. This have nothing to do with any particular programming language.

Here is the C++ implementation which does not do swapping inside the loop.

void insertionSort(int arr[], int length) {
    int i, j, newValue;
    for (i = 1; i < length; i++) {
      newValue = arr[i];
      j = i;
      while (j > 0 && arr[j - 1] > newValue) {
        arr[j] = arr[j - 1];
        j--;
      }
      arr[j] = newValue;
    }
}

Thank you for your answer. I'm assuming there are many ways to access the length for an array in c++, is there a standard that I should look out for? — mtorres, Dec 29 '15 at 04:06
I hope this will help. [How do I find the length of an array?](http://stackoverflow.com/questions/4108313/how-do-i-find-the-length-of-an-array). — YoungHobbit, Dec 29 '15 at 04:08

Difference in implementation for Insertion Sort

1 Answers1