0

OUTPUT 

    #include <iostream>
    using namespace std;

    int main()
    {
        //declaring the size of array and taking input from the user
        int n = 0;
        cout<<"Enter the Number of elements you want in the Array : ";
        cin>>n;
        //checking the user input
        if(n <= 0)
        {
            cout<<"Not Possible\n";
            return 1;
        }

        //declaring array of size 'n' and taking input from user
        int list[n];
        cout<<"Enter the Elements of the array of size "<<n<<" : ";
        for(int i = 0; i < n; i++)
            cin>>list[i];

        //Insertion Sort
        int swap = 0;   //number of swaps
        int comp = 0;   //number of comparison
        int temp;       //temporary variable 
        for(int i = 0; i < n-1; i++)
        {
            for(int j = i+1; j > 0; j--)
            {
                if(list[j] < list[j-1])
                {
                    //swapping equivalent to shifting
                    temp = list[j-1];
                    list[j-1] = list[j];
                    list[j] = temp;
                    comp++;
                    swap++;
                }
                else
                {
                    comp++;
                    break;
                }
            }
            //printing the iteration
            cout<<"Iteration  "<<(i+1)<<" : ";
            for(int k = 0; k < n; k++)
                cout<<list[k]<<" ";
            cout<<"\n";
        }

        cout<<"\nSwap : "<<swap<<"\n";
        cout<<"Comparison : "<<comp<<"\n";
        cout<<"Sorted Array : ";
        for (int i = 0; i < n; i++)
        {
            cout<<list[i]<<" ";
        }

        return 0;
    }

Is this implementation of insertion sort correct because I have seen many implementation online using while loop and other things?

If not can you point out what is wrong?

Thanks in advance

link - https://github.com/ish-u/DiscreteStructures/blob/master/InsertionSort.cpp

marc_s
  • 732,580
  • 175
  • 1,330
  • 1,459
an60221023
  • 9
  • 3

1 Answers1

2

No, this is a different type of sort, known as bubble sort. It still sorts, but insertion sort works in a different way, by keeping the array sorted at all times (moving elements if a new insertion would break the ordering).

So instead of just tagging new elements to the end of the array where you read them from cin, you should place each element directly in the right spot in the array. This will likely involve moving existing elements in order to keep the array sorted.

Note that your line

int list [n];

is wrong; you cannot allocate memory this way (and I'm surprised it even compiles). A better choice would be to use std::vector.

H. Guijt
  • 3,325
  • 11
  • 16
  • i am breaking the loop if the elements before are sorted... and continuing it till the 'key' element finds the correctt spot... – an60221023 Feb 08 '20 at 12:16
  • i don't know about vectors...if my implementation is wrong please tell me what is the correct one – an60221023 Feb 08 '20 at 12:18
  • You can learn about std::vector here: https://en.cppreference.com/w/cpp/container/vector – H. Guijt Feb 08 '20 at 12:18
  • 1
    "I'm surprised it even compiles" Variable length arrays is a C-feature and gcc has it as an extension also for C++ (but you are right that it isnt standard C++): https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard – 463035818_is_not_an_ai Feb 08 '20 at 12:42
  • guys i don't know advance c++ so the vector things are just adding confusion to my question. I just want to know whether the implementation of the Insertion Sort to sort the array that was taken as input from the user... I have seen most implementation using a while loop and shfiting rather than swaping(which i am using) ... I just want to know why is shifting better than swapping here – an60221023 Feb 08 '20 at 13:23
  • Your sorting algorithm is not insertion sort but bubble sort, so if it is your goal to implement insertion sort, you have done so incorrectly. Shifting (which I take to mean "moving each element in the array to the next position") is cheaper than swapping because you have only half the number of reads and writes. – H. Guijt Feb 08 '20 at 13:42
  • so i should use a whiie loop and shift rather than this...got it ...thanks – an60221023 Feb 08 '20 at 14:02