1

recently, I learned how to use insertion sort. So, i started tinkering with its code.

#include<bits/stdc++.h>
using namespace std;
 
int main(void)
{
    int arr[] = {4,3,2,10,12,1,5,6};
    int n = sizeof(arr)/sizeof(arr[0]);

    for(int i=1; i<n; i++)
    {
        int key = arr[i]; // line a
        int j = i-1;

        while(j>=0 && arr[j]>key) //line b
        {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key; //line c
    }

    for(int i=0; i<n; i++)
    {
        cout<<arr[i]<<" ";
    }
}

since key = arr[i], I removed "line a" and placed arr[i] instead of key at "line b" and "line c". I expected the same outcome, but the output is [4 4 4 10 12 12 12 12] which is wrong. Why did this happen?

Alan Birtles
  • 32,622
  • 4
  • 31
  • 60
amaan211
  • 25
  • 5
  • use a debugger and find out why – bb1950328 Aug 26 '21 at 13:02
  • 1
    Unrelated but useful: [Why should I **not** `#include `?](https://stackoverflow.com/Questions/31816095/Why-Should-I-Not-Include-Bits-Stdc-H.) and [Why is `using namespace std;` considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) – Ted Lyngmo Aug 26 '21 at 13:10
  • I imagine the element at `arr[i]` is moved between line a and line c – Alan Birtles Aug 26 '21 at 13:10
  • Aside: [Implementing insertion_sort](https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c) among other sorts – Caleth Aug 26 '21 at 13:25

1 Answers1

3

When you do int key = arr[i];, the value of the key is saved in the variable key.

When you do while(j>=0 && arr[j]>arr[i]) instead, you use the current value of arr[i]. At first it is the same, but as the while loop runs, you start modifying arr:

arr[j+1] = arr[j];

This will modify arr[i] eventually, when j+1 equals i. So, for the further iterations of the loop, you'll check against a different value.

Jeffrey
  • 11,063
  • 1
  • 21
  • 42
  • 2
    It modifies it in the first go round of the loop, because `j` starts at `i-1` and goes down – Caleth Aug 26 '21 at 13:20