Scribd
Upload
9 views1 page

Insertion Sort with Comparison Count

The document presents a C++ program that implements the Insertion Sort algorithm to sort an array of integers. It tracks and reports the number of comparisons made during the sorting process. The program prompts the user for the number of elements and their values, sorts the array, and then displays the sorted array along with the total comparisons.

Uploaded by

raj617104
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
9 views1 page

Insertion Sort with Comparison Count

The document presents a C++ program that implements the Insertion Sort algorithm to sort an array of integers. It tracks and reports the number of comparisons made during the sorting process. The program prompts the user for the number of elements and their values, sorts the array, and then displays the sorted array along with the total comparisons.

Uploaded by

raj617104
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

PROGRAM 1

Question: Write a program to sort the elements of an array


using Insertion Sort. (The program should report the
number of comparisons.)

CODE:

#include <iostream>
using namespace std;

void insertionSort(int arr[], int n, int &comparisons) {


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

while (j >= 0 && (++comparisons && arr[j] > key)) {


arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}

int main() {
int n;
cout << "Enter number of elements: ";
cin >> n;

int arr[100];
cout << "Enter elements:\n";
for (int i = 0; i < n; i++)
cin >> arr[i];

int comparisons = 0;
insertionSort(arr, n, comparisons);

cout << "Sorted array:\n";


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

cout << "Total number of comparisons: " << comparisons << endl;

return 0;
}

You might also like