Answer to Question #59769 in C++ for PRIYA

Question

Which of the following sorting algorithms in its typical implementation gives best
performance when applied on an array which is sorted or almost sorted (maximum 1 or two
elements are misplaced).
a.heap sort
b.quick sort
c.insertion sort
d.merge sort
NOTE: Write a program for the correct option and get the input from the user

Answer 1

C. Insertion Sort

#include <iostream>
#include <vector>

using namespace std;

int main() {
unsigned size;
cout << "Input size of array (count of elements): ";
cin >> size;
vector<int> arr(size);
for (unsigned i = 0; i < arr.size(); i++) {
cout << "Input " << i << "th element of the array (" << i << "th number): ";
cin >> arr[i];
}
cout << endl;
// Start of insertion sort
for (unsigned i = 1; i < arr.size(); i++) {
int j = i;
while (j > 0 && arr[j - 1] > arr[j]) {
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
j--;
}
}
// End of insertion sort
for (unsigned i = 0; i < arr.size(); i++) {
cout << arr[i] << " ";
}
cout << endl;
system("pause");
return 0;
}