DNA strings sorting function problem

Question

Well, I'm trying to solve the following problem, and almost done: http://acm.pku.edu.cn/JudgeOnline/problem?id=1007

Here's my code:

#include "stdafx.h"
#include<iostream>
#include<string>
using namespace std;
/*

int compare(size_type pos1, size_type n1,
const charT* s, size_type n2 = npos) const;*/
int * sort(string *w, int n, int l, int * count){

         for(int i = 0; i< n; i++){
               for(int k= 0; k < l; k++){
                     for(int z = 0; z < k; z++)
                            if(w[k][z] > w[k][z]) count[i]++;
                     }
               }
     return count;
         }

int main(){

cout << "Enter the number of strings, followed by the length of each one: " << endl;
int n,l;
cin >> n >> l;
int *count = new int[n];
string *s = new string[n];
for(int i =0; i < n; i++){
cout << "Enter the string #" << i+1 << endl;
cin >> s[i];
}
int * x = sort(s, n, l, count);
for(int i = 0;  i < n; i++){
      cout << x[i]<< endl;
      }

 getchar(); getchar();

}

I've no problem but the if condition line in sort(), and the I can't get the value of count correctly from sort()

Update: I just want you to find a suitable form for the if condition using the string subscript like the one above.

Answer 1

if(w[k][z] > w[k][z])

You are comparing a number with itself. This means count[i] will never be incremented.

I believe you want w[i][z]>w[i][k] instead. You should also initialize count to 0.

Answer 2

You need to define "sortedness", i.e., from the definition in the mentioned page: the number of pairs out of order.

Functionally written that would be

unsortedness( {} ) = 0

unsortedness( a1, a2, ... an ) = 
    count( smaller_then( a1 ), {a2,a3,...,an} ) 
    + unsortedness( {a2,a3,...,an} )

If you can pour that in C++ syntax, you're done. Hint: there is a standard function std::count_if( begin, end, comparator ), in which you can use std::bind2nd( std::less<char>(), a1 ) as comparator.

Answer 3

First, you tagged your question, why don’t you use C++ features such as strings? Second, use std::stable_sort to perform the actual sorting for you. You need to supply a fitting sorting criterion to stable_sort. This is where your code comes in: as a criterion, you supply it with a function (functor) which compares the sortedness of a string, using your (corrected) function.