Как реализовать естественный алгоритм сортировки в C ++?





В данном посте я покажу как можно отсортировать смешанные данные, т.е. строки, которые содержат числа, слова, даты и.т.д.

Допустим у нас имеется файл содержащий данные в виде:

34 Jack 2016-01-22
43 Oliver 2016-01-23
3 Charlie 2016-01-20
7 Harry 2016-01-19
78 Alfie 2016-01-22
13 Thomas 2016-01-22
32 Joshua 2016-01-11
21 William 2016-01-08
17 James 2016-01-25
2 Amelia 2016-01-26
54 Daniel 2016-01-22
33 Lily 2016-01-17
11 Emily 2016-01-22

то есть каждая строка содержит цифры и слова. Нам надо отсортировать данный список по порядку так чтобы все строки содержащие цифры шли по возрастанию.
Стандартные методы сортировка естественно не подходят, но способ всё-таки есть — это натуральная сортировка.

См. листинг:

#pragma hdrstop

#pragma argsused

#ifdef _WIN32

#include <tchar.h>

#else

typedef char _TCHAR;

#define _tmain main

#endif

#include <fstream>

#include <iostream>

#include <vector>

#include <algorithm>

#include <sstream>

using namespace std;

struct Symbol {

    bool is_number;

    string string;

};

vector<Symbol>Tokenize(string const &input) {

    string const number = "0123456789";

    vector<Symbol>result;

    if (!input.empty()) {

        bool inside_number_token =

            isdigit(static_cast<unsigned char>(input[0])) != 0;

        string::size_type start_current_token = 0;

        string::size_type start_next_token = 0;

        do {

            if (inside_number_token) {

                start_next_token =

                    input.find_first_not_of(number, start_current_token);

            }

            else {

                start_next_token =

                    input.find_first_of(number, start_current_token);

            }

            string const string =

                input.substr(start_current_token,

                start_next_token - start_current_token);

            Symbol symbol;

            symbol.is_number = inside_number_token;

            symbol.string = string;

            result.push_back(symbol);

            start_current_token = start_next_token;

            inside_number_token = !inside_number_token;

        }

        while (start_current_token != string::npos);

    }

    return result;

}

int ConvertToInteger(string const &number_as_string) {

    istringstream converter(number_as_string);

    int ganze = 0;

    converter >> ganze;

    return ganze;

}

struct NaturalSortOrder {

    bool operator()(string const &lhs, string const &rhs) const {

        vector<Symbol> const tokens_lhs = Tokenize(lhs);

        vector<Symbol> const tokens_rhs = Tokenize(rhs);

        for (vector<Symbol>::size_type index = 0;

        index < tokens_lhs.size() && index < tokens_rhs.size(); ++index) {

            Symbol const &token_lhs = tokens_lhs[index];

            Symbol const &token_rhs = tokens_rhs[index];

            if (token_lhs.is_number && token_rhs.is_number) {

                int const number_lhs = ConvertToInteger(token_lhs.string);

                int const number_rhs = ConvertToInteger(token_rhs.string);

                if (number_lhs != number_rhs) {

                    return number_lhs < number_rhs;

                }

            }

            else {

                if (token_lhs.string != token_rhs.string) {

                    return token_lhs.string < token_rhs.string;

                }

            }

        }

        return false;

    }

};

int _tmain(int argc, _TCHAR* argv[]) {

    vector<string>filenames;

    ifstream input_file("C:\myfile.txt");// файл в котором надо отсортировать данные

    char line[100];

    while (!input_file.eof()) {

        input_file.getline(line, sizeof(line));

        filenames.push_back(line);

    }

    sort(filenames.begin(), filenames.end(), NaturalSortOrder());

    for (vector<string>::const_iterator iter = filenames.begin();

    iter != filenames.end(); ++iter) {

        cout << *iter << "\n";

    }

    system("pause");

    return 0;

}

Результат:

Соответственно, если нам надо наоборот сделать сортировку по убыванию, то достаточно поменять оператор «<» в строке 135 на «>»

return number_lhs > number_rhs;

и тогда мы получим:

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

*