We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
boolsorted(vector<int>arr,intindex){for(inti=0;i<index;i++){if(arr[i]>arr[i+1])returnfalse;}returntrue;}voidinsertionSort2(intn,vector<int>arr){inti,key,j;for(i=1;i<n;i++){//initiating key at arr[i]key=arr[i];//setting key one place behind ij=i-1;//now we will check if j >=0 and arr[j] is also greater than keywhile(j>=0&&arr[j]>key){//putting element of j one place advance arr[j+1]=arr[j];j=j-1;//we are also decrementing j's position so that we can put key at the end }//putting key behind all the elements greater than keyarr[j+1]=key;if(!sorted(arr,i-1)){cout<<"Failed at i="<<i-1<<endl;for(intj=0;j<n;j++){cout<<arr[j]<<" ";}cout<<endl;}}//print the arrayfor(inti=0;i<arr.size();++i){cout<<arr[i]<<" ";}cout<<"\n";}intmain(){/* Enter your code here. Read input from STDIN. Print output to STDOUT */intn;cin>>n;vector<int>v;for(inti=0;i<n;i++){inttemp;cin>>temp;v.push_back(temp);}insertionSort2(n,v);return0;}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Correctness and the Loop Invariant
You are viewing a single comment's thread. Return to all comments →
C++ Solution with loop Invariant