CODEWITHSUNDEEP
javac++insertion-sort
mtorres
mtorres

Reputation: 197

Difference in implementation for Insertion Sort

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.

Upvotes: 0

Views: 84

Answers (1)

YoungHobbit
YoungHobbit

Reputation: 13402

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;
    }
}

Upvotes: 3

Related Questions