Question

Do an insertion sort based off this code

#include <iostream>

#define MAX_INT 2147483647

using namespace std;
  

int main(int argc,char **argv) {

int* Sequence;
int arraySize = 1;

// Get the size of the sequence
cin >> arraySize;
Sequence = new int[arraySize];
  
// Read the sequence
for(int i=0; i<arraySize; i++)
cin >> Sequence[i];

Answer 1

Insertion sort works by comparing the elements from second element in the array with all the elements below it and move that element such that up to that part the array remains sorted.

Insertion Sort Code:

#include <iostream>

#define MAX_INT 2147483647

using namespace std;
  

int main(int argc,char **argv) {

int* Sequence;
int arraySize = 1;
int i,j,pivot;

// Get the size of the sequence
cin >> arraySize;
Sequence = new int[arraySize];
  
// Read the sequence
for(int i=0; i<arraySize; i++)
cin >> Sequence[i];

for(i=1;i<arraySize;i++){
j=i-1;
pivot = Sequence[i];
  
//Comparing the elements from second element with all the elements below it
//and made the array sorted upto that point
while(j>=0 && Sequence[j] > pivot){
Sequence[j+1]=Sequence[j];
j=j-1;
}
  
Sequence[j+1]=pivot;
}
cout<<"The sorted array is:\n";
for(int i=0; i<arraySize; i++)
cout << Sequence[i]<<" ";

}

Output: