UVA – 612 – DNA Sorting

  • Problem Statement : http://uva.onlinejudge.org/external/6/612.html
  • Gochas :
    • Use STL’s stable_sort it preserves the relative ordering of equivalent elements. That is, if x and y are elements in [first, last) such that x precedes y, and if the two elements are equivalent (neither x < y nor y < x) then a postcondition of stable_sort is that x still precedes y.
    • This is an Inversion Index problem, count the no of swaps needed using a linear sort algorithm.
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <vector>
using namespace std;

typedef struct DNA {
	string s;
	int swaps;
	DNA() {	}
	DNA(string a) {
		s = a;
		swaps = 0;
		for (size_t i = 0; i < a.size() - 1; i++)
			for (size_t j = i + 1; j < a.size(); j++)
				if (a[i] > a[j])swaps++;
	}
};
bool operator < (const DNA & a, const DNA & b){ return  a.swaps<b.swaps; }
int main() {
	int T, started=0, N, L;
	scanf("%d\n", &T);
	while (T--) {
		if(started++)printf("\n");
		scanf("%d %d\n", &L, &N);
		char line[L];
		vector<DNA> v;
		while (N-- && gets(line)) v.push_back(DNA(string(line)));
		stable_sort(v.begin(), v.end());
		for(size_t i=0; i<v.size(); i++)
			printf("%s\n", v[i].s.c_str());

	}
	return 0;
}
Advertisements

2 thoughts on “UVA – 612 – DNA Sorting

  1. ashis says:

    Thanks to share your mistakes. But I think it is not a good habit to published all solving codes. You may discuss about the process or algorithm that you follow to solve the problem, then the visitor will solve it using his own style. There is also some people who are more interest in copy past than programming.
    Best of luck . . .

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: