Search code examples
c++arrayssortinginsertion-sortfunction-definition

Does this count as an Insertion-Sort? And why does a random number show at the end?


I've been asked to create an insertion sort for an array. My program ended differently from the teacher's, but it sorts the array. However, I'm curious if it truly counts as a proper insertion sort. Also, at the end of the sorting, some random numbers appear. I would appreciate some help with this.

#include <iostream>
#define size  6
using namespace std;
void insertion(int v[size]){
    int i,temp;
    for(i=0;i<size;i++){
       while(v[i+1] < v[i]){
            temp = v[i+1];
            v[i+1] = v[i];
            v[i] = temp;
            printArr(v);
            i = 0;
            }
      }
}
int main(){
    int vet[size] = {34,12,15,21,5,88};
    printArr(vet);
    insertion(vet);
    
    return 0;

}

Here is the output, one line at a time:

34,12,15,21,5,88,
12,34,15,21,5,88,
12,15,34,21,5,88,
12,15,21,34,5,88,
12,15,21,5,34,88,
12,15,5,21,34,88,
12,5,15,21,34,88,
5,12,15,21,34,88,
5,12,15,21,34,44,

Notice the 44 at the end there. I don't know why it's there since the code works nicely up until the end.

Edit: Fixed a damn typo. My PC turns any lowercase i into uppercase, just forgot to adjust it, but it's not wrong in code.


Solution

  • For starters there is a typo in this statement

    v[i+1] = v[I];
             ^^^^ 
    

    It seems you mean

    v[i+1] = v[i];
             ^^^^
    

    The while loop

       while(v[i+1] < v[i]){
            temp = v[i+1];
            v[i+1] = v[I];
            v[i] = temp;
            printArr(v);
            i = 0;
            }
    

    can invoke undefined behavior due to accessing memory beyond the array when i is equal to size - 1.

    In any case the approach with the while loop is incorrect and inefficient. The outer for loop again starts from 0 when a swap of adjacent elements occurred.

    And moreover the function depends on the magic named number 6. That is it is unable to sort arrays of different sizes.