Question

1. How many comparisons and how many moves are needed to sort the array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} using shell sort?

How many comparisons and how many moves are needed to sort the array = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1} using shell sort?

2. Write a c++ program that finds the number of comparisons and number of moves in shell sort.

Answer 1

1. How many comparisons and how many moves are needed to sort the array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} using shell sort?

Ans:  No of comparisons to be made is : 25

No of moves to be made is : 0 ( Because it is already sorted )

2. How many comparisons and how many moves are needed to sort the array = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1} using shell sort?

Ans: No of comparisons to be made is : 51

No of moves to be made is : 26

( Swapping of elements with each other place is known to be 2 moves )

Program :

#include <iostream>
using namespace std;
  

int shell(int a[], int n)
{
int comp = 0;
int mov = 0;

for (int l = n/2; l > 0; l /= 2)
{
comp++;
  
for (int i = l; i < n; i += 1)
{
comp++;

int temp = a[i];

int j;   
for (j = i; j >= l && a[j - l] > temp; j -= l)
{
a[j] = a[j - l];
comp++;
comp++;
mov = mov + 2;
  
}

a[j] = temp;
}
}
cout << "Number of Comparison : \n" << comp << endl; // printing no of comparisons
  
cout << "Number of Moves : \n" << mov << endl; // printing no of moves
return 0;
}
  

int main()
{
int a[100], i, n;
cout << "Enter the no of elements to find the comparisons and moves: \n";
  
cin >> n; // read no of elements
  
cout << "Enter the elements to find the comparisons and moves: \n";
  
for(i = 0; i < n; i++)
{
cin >> a[i]; // read each element into an array
}
  
shell(a, n); // passing array and no of elements to shell function
  
cout << "After sorting: \n";
  
for(i = 0; i < n; i++)
{
cout << a[i] << " "; // print elements after sorting
}
  
return 0;
}

OUTPUT :