Table of Contents

Sorting in computer science is an important part. Almost every problem can be solved effeciently if
sorted data are found. There are some excellent sorting algorithm which has already acheived the lower
bound n · lg n. In this problem we will also discuss about a new sorting approach. In this approach
only one operation (Flip) is available and that is you can exchange two adjacent terms. If you think a
while, you will see that it is always possible to sort a set of numbers in this way.
A set of integers will be given. Now using the above approach we want to sort the numbers in
ascending order. You have to find out the minimum number of flips required. Such as to sort ‘1 2 3’
we need no flip operation whether to sort ‘2 3 1’ we need at least 2 flip operations.

Input

The input will start with a positive integer N (N ≤ 1000). In next few lines there will be N integers.
Input will be terminated by EOF.

Output


For each data set print ‘Minimum exchange operations : M’ where M is the minimum flip operations required to perform sorting. Use a seperate line for each case.


Sample Input


3
1 2 3
3
2 3 1


Sample Output

Minimum exchange operations : 0
Minimum exchange operations : 2

Solution Code C++


#include <bits/stdc++.h>
using namespace std;
int c=0;
void swap(int *xp, int *yp)
{
    c++;
	int temp = *xp;
	*xp = *yp;
	*yp = temp;
}

void bubbleSort(int arr[], int n)
{
	int i, j;
	for (i = 0; i < n-1; i++)


	for (j = 0; j < n-i-1; j++)
		if (arr[j] > arr[j+1])
			swap(&arr[j], &arr[j+1]);
}


int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
    int arr[n];
    for(int i=0;i<n;i++)scanf("%d",&arr[i]);

	bubbleSort(arr, n);
    printf("Minimum exchange operations : %d\n",c);
    c=0;
    }

	return 0;
}

Share on facebook
Facebook
Share on twitter
Twitter
Share on linkedin
LinkedIn
Share on pinterest
Pinterest
Share on whatsapp
WhatsApp
Share on email
Email
Md. Nurnobi Hosen
Md. Nurnobi Hosen

Student of Computer Science and Engineering at Daffodil International University,Main Campus ,Dhanmondi.
Web and App Developer also expart of wordpress customization

All Blog Posts »
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x