使用插入排序的倒置检查器

Question

我需要输出一组字母，这些字母相对于彼此的倒置次数而言是乱序的。

例如，序列“AACEDGG”只有 1 个反转（E 和 D），而序列“ZWQM”有 6 个反转。我实际上不必整理它，但我必须根据它们的反转次数输出它们。

例如：

输入：AACATGAAGG TTTTGGCCAA TTTGGCCAAA GATCAGATTT CCCGGGGGGA ATCGATGCAT

输出：CCCGGGGGGA AACATGAAGG GATCAGATTT ATCGATGCAT TTTTGGCCAA TTTGGCCAAA

我正在尝试按照老师的要求使用插入排序作为模板。

void inversionChecker(string dna[], int n)
{
    int j,k,m;
    int tempCount;
    for(int i=0; i < n; i++){
        int count=0;
        for(j=0;j < n; j++){
            for(k=j+1; k <= n; k++){
                if(dna[i][j] > dna[i][k]){
                    count++;
                    tempCount = count;
                }
            }
        }
        if(i != 0 && tempCount > count)
            dna[i].swap(dna[i-1]);
    }
}

我遇到问题是因为我不太熟悉使用二维数组来比较每个字符串中的字母。当我尝试输出数组时，它最终变成空白、段错误或由于我尝试交换数组中字符串的位置而导致的错误。

如有任何帮助，我们将不胜感激

Answer 1

此处访问dna数组越界：

for(j=0;j < n; j++){
    for(k=j+1; k <= n; k++){        // when k == n you have undefined behavior
        if(dna[i][j] > dna[i][k])

应该是：

for(j=0;j < n-1; j++){
    for(k=j+1; k < n; k++){
        if(dna[i][j] > dna[i][k])

另一种使用 misc 的方法。标准类和算法，例如 std::vector 和 std::sort.

#include <algorithm> // copy, sort
#include <cstddef>   // size_t
#include <iterator>  // istream_iterator, back_inserter
#include <sstream>   // istringstream
#include <string>    // string
#include <tuple>     // tie
#include <utility>   // swap
#include <vector>    // vector

#include <iostream>

// count inversions in a sequence
unsigned count_inversions(std::string sequence) {
    unsigned res = 0;

    // assuming "inversions" are defined as the number of swaps needed in bubblesort
    for(size_t i = 0; i < sequence.size() - 1; ++i) {
        for(size_t j = i + 1; j < sequence.size(); ++j) {
            if(sequence[j] < sequence[i]) {
                std::swap(sequence[i], sequence[j]);
                ++res;
            }
        }
    }
    return res;
}

// a class to store a sequence and its inversion count
struct sequence_t {
    sequence_t() = default;

    explicit sequence_t(const std::string& Seq) :
        seq(Seq), inversions(count_inversions(seq)) {}

    // "less than" operator to compare two "sequence_t"s (used in std::sort)
    bool operator<(const sequence_t& rhs) const {
        // assuming lexicographical order if inversions are equal
        return std::tie(inversions, seq) < std::tie(rhs.inversions, rhs.seq);
    }

    std::string seq;
    unsigned inversions;
};

// read one sequence_t from an istream
std::istream& operator>>(std::istream& is, sequence_t& s) {
    std::string tmp;
    if(is >> tmp) s = sequence_t(tmp);
    return is;
}

// read "sequence_t"s from an istream and put in a vector<sequence_t>
auto read_sequences(std::istream& is) {
    std::vector<sequence_t> rv;

    std::copy(std::istream_iterator<sequence_t>(is),
              std::istream_iterator<sequence_t>{}, std::back_inserter(rv));
    return rv;
}

int main() {
    std::istringstream input(
        "AACATGAAGG TTTTGGCCAA TTTGGCCAAA GATCAGATTT CCCGGGGGGA ATCGATGCAT");

    auto sequences = read_sequences(input);

    std::sort(sequences.begin(), sequences.end());

    // print result
    for(const auto& [seq, inversions] : sequences) {
        std::cout << seq << '(' << inversions << ')' << ' ';
    }
    std::cout << '\n';
}

输出（包括反转）：

CCCGGGGGGA(2) AACATGAAGG(10) GATCAGATTT(10) ATCGATGCAT(11) TTTTGGCCAA(12) TTTGGCCAAA(15)

使用插入排序的倒置检查器

Inversion Checker using Insertion Sort

c++

arrays

sorting

inversion

insertion-sort