Question

1) Design a greedy algorithm that solves the problem; describe your algorithm with clear pseudocode; and prove the time efficiency class of your algorithm:

If x, y are two adjacent elements in a sequence, with x before y, we say that the pair x, y is in order when x <= y and the pair is out of order when x > y.

For example, in the string “BEGGAR” the pair G, A are out of order, but all the other pairs are in order.

out-of-order counting

input: a list L of n comparable elements output: the number of out-of-order pairs in L

Hint: An optimal algorithm for this problem takes O(n) time.

Answer 1

Greedy Algorithm(C++ code) for the above problem is as follows-

#include<bits/stdc++.h>

using namespace std;

int main() {

string s;
cin>>s;
int n=s.length();

//to count the No. of out-of-order pairs
int ans=0;

//traversing the list
for(int i=0;i<n-1;i++){
//checking if the element before
//is greater then element after it.
if(s[i]>s[i+1])
ans++;
}

//displaying the answer
cout<<"No. of out-of-order pairs-> "<<ans;

return 0;
}
Code-

Input and Output-


Time complexity of the above algorithm is O(n) because only one loop has been used to traverse the list only once.

If the answer helped then please upvote, it means a lot.
And for any queries feel free to comment.