Как реализовать естественный алгоритм сортировки в 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;

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

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

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

*