Question

Use any programming language.

1)Permutations (Johnson Trotter): {1, 2, 3, 4, 5}; Insertion Sort: {45, 24, 16, 92, 71, 69, 28} – develop count of # data “insertions”

2) Use sorted data from insertion sort (part A) and develop # of key compares against the following: 16, 77, 24, 92, 44

Answer 1

1)1st part

#include <iostream>
#include<conio.h>

using namespace std;

const bool LTR = true;
const bool RTL = false;

void displayPermutation(int);

// main function
int main()
{
int n = 5;

displayPermutation(n);

getch();

return 0;
}

// function find the factorial of n
int fact(int n)
{
if(n==1) return 1;
return (n*fact(n-1));
}

// function finding the position of largest integer
int search(int a[], int n, int key)
{
for (int i=0; i<n; i++)
if (a[i] == key)
return i + 1;
}

// function find the largest mobile integer
int getMobile(int a[], bool d[], int n)
{
int prev = 0, m = 0;
for (int i=0; i <n; i++)
{
// 0 represents RIGHT TO LEFT.
if (d[a[i]-1] == RTL && i!=0)
{
if (a[i]>a[i-1] && a[i]>prev)
{
m = a[i];
prev = m;
}
}

// 1 represents LEFT TO RIGHT.
if (d[a[i]-1] == LTR && i!=n-1)
{
if (a[i]>a[i+1] && a[i]>prev)
{
m = a[i];
prev = m;
}
}
}

if (m == 0 && prev == 0)
return 0;
else
return m;
}

// function to interchange two variables
void interchange(int &a, int &b)
{
int t;
t = a;
a = b;
b = t;
}

// function prints a single permutation
int displaySinglePerm(int a[], bool d[], int n)
{
int m = getMobile(a, d, n);
int pos = search(a, n, m);

// interchange the elements
if (d[a[pos - 1] - 1] == RTL)
interchange(a[pos-1], a[pos-2]);

else if (d[a[pos - 1] - 1] == LTR)
interchange(a[pos], a[pos-1]);

for (int i=0; i<n; i++)
{
if (a[i]> m)
{
if (d[a[i]-1] == LTR)
d[a[i]- 1] = RTL;
else if (d[a[i] - 1] == RTL)
d[a[i] - 1] = LTR;
}
}

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

}

//function to display permutation
void displayPermutation(int n)
{
int a[n];
bool d[n];

for (int i=0; i<n; i++)
{
a[i] = i + 1;
cout << a[i];
}
for (int i=0; i<n; i++)
d[i] = RTL;

for (int i=1; i<fact(n); i++)
displaySinglePerm(a, d, n);
}

Output screen:

12345 12354 12534 1523451234 51243 15243 12543 12453 12435 14235 14253 14523 15423 51423 5412345123415234125341235, 41325 41352 41532451325413251432 15432 14532 14352 14325 13425 13452 13542 15342 51342 51324 15324 13524 13254 13245 31245 31254 31524 35124 53124 53142 35142315423145231425 4125 14152 4512 35412 53412 4312 45312 43512 43152 43125 43215 43251 43521 45321 54321 53421 35421 34521 34251 34215 3241532451 52541 52415324153214 35214 325 14 3215432145 23145 23154 23514 25314 52314 52341 25341235412345123415 24315 24351 24531 25431 52431 54231 45231 42531 42351 42315 42142534251445213542135241325413 24513 24 153 24135 21435 21453 215432514352143 52134 25114 2153421354 21345

1) 2nd part:

#include<iostream>
#include<conio.h>

using namespace std;

int insertion(int a[], int n);

//main function
int main()
{
int a[] = {45, 24, 16, 92, 71, 69, 28};
int n = 7;

int c = insertion(a, n);

cout<<"Sorted List: "<<endl;

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

cout<<endl<<"Number of insertion: "<<c<<endl;

getch();
}

//function of insertion sort
int insertion(int a[], int n)
{
int i, j, t;
int count = 0;

for(i=1; i<n; i++)
   {
t=a[i];

if(t<a[i-1]) count++;

for(j=i-1;j>=0 && t<a[j];j--)
{
a[j+1]=a[j];
}
a[j+1]=t;
}

return count;
}

Output Screen:

Sorted list: 16 24 28 45 69 71 92 Number of insertion: 5

2)

#include<iostream>
#include<conio.h>

using namespace std;

void insertion(int a[], int n);
int inserting(int a[], int&, int);

//main function
int main()
{
int a[20] = {45, 24, 16, 92, 71, 69, 28};
int n = 7;

int c = 0;

insertion(a, n);

c = inserting(a, n, 16);
cout<<endl<<"Number of comparisons to insert 16: "<<c;
c = inserting(a, n, 77);
cout<<endl<<"Number of comparisons to insert 77: "<<c;
c = inserting(a, n, 24);
cout<<endl<<"Number of comparisons to insert 24: "<<c;
c = inserting(a, n, 92);
cout<<endl<<"Number of comparisons to insert 92: "<<c;
c = inserting(a, n, 44);
cout<<endl<<"Number of comparisons to insert 44: "<<c;

getch();
}

int inserting(int a[], int &n, int key)
{
int i;

int count = 1;

for(i=n-1; i>=0 && key<a[i];i--,count++)
{
a[i+1]=a[i];
}

a[i+1]=key;

n = n + 1;

return count;
}

//function of insertion sort
void insertion(int a[], int n)
{
int i, j, t;

for(i=1; i<n; i++)
   {
t=a[i];

for(j=i-1;j>=0 && t<a[j];j--)
{
a[j+1]=a[j];
}
a[j+1]=t;
}
}

Output screen:

Number of comparisons to insert 16: 7 Number of comparisons to insert 77: 2 Number of comparisons to insert 24: 7 Number of comparisons to insert 92: 1 Number of comparisons to insert 44: 7