Обсуждение:Поразрядная сортировка

== Код на C++ ==

Добавил реализацию на С++. Просьба проверить.UlanovDmitry 15:57, 5 мая 2009 (UTC)

Данную функцию вставлял в Bulder C++, настроил свой ввод и вывод списка. Ввыводимый список получился не только не отсортированный , но и больше по длинне. Пример: Ввод: "Текст" Вывод: "Текстексткстст".

Пример реализации

Могу предложить реализацию алгоритма, выполненную в качестве учебного задания в вузе :). Если кому-то не понравится кривой код, ВП:ПС

i/d — сортировка по возрастанию/убыванию

сортировка.exe входной_файл выходной_файл i

/*Uses*/
#include "stdafx.h"
#include "iostream"
#include "fstream"

using namespace std;

/*Constants*/
const int MaxN= 200;

class TArrayInfo{
	public:
		int Beg, End, Length;
};

/*Variables*/
ifstream Input;
TArrayInfo InArr[MaxN];
int N= 0, OutArr[2* MaxN], MaxLength= -1;
bool IncOrd;
_TCHAR *FileNameInput, *FileNameOutput;

/*Functions*/
void ReadLF(){
	ifstream Input(FileNameInput);
	char Ch;
	bool LF= false;
	InArr[N].Beg= 0;
	while (Input.get(Ch)){
		if (Ch== '\n'){
			if (!LF)
				InArr[N].Length= InArr[N].End- InArr[N].Beg+ 1;
			LF= true;
		}
		else{
			if (LF){
				LF= false;
				InArr[++N].Beg= int(Input.tellg())- 1;
				InArr[N].End= InArr[N].Beg;
			}
			else{
				InArr[N].End= int(Input.tellg())- 1;
			};
		};
	};
	InArr[N].Length= InArr[N].End- InArr[N].Beg+ 1;
	for (int I= 0; I<= N; I++){
		OutArr[I]= I;
		InArr[I].Length= InArr[I].End- InArr[I].Beg+ 1;
		if (MaxLength< InArr[I].Length)
			MaxLength= InArr[I].Length;
	};
	Input.close();
};

void OutFile(){
	ifstream Input(FileNameInput);
	ofstream Output(FileNameOutput);
	char Ch;
	for (int I= 0; I<= N; I++){
		if (I> 0)
			Output<< '\n';
		Input.seekg(InArr[OutArr[I]].Beg);
		for (int J= 0; J<= InArr[OutArr[I]].Length- 1; J++){
			Input.get(Ch);
			Output.put(Ch);
		};
	};
	Output.close();
	Input.close();
};

char GetChar(int Index, TArrayInfo Cell){
	int Pos= Cell.Beg+ Index;
	if (Pos> Cell.End)
		return 0;
	else{
		char Ch;
		Input.seekg(Pos);
		Input.get(Ch);
		return Ch;
	};
};

/*Main*/
int _tmain(int argc, _TCHAR* argv[])
{
	if (argc< 4)
		return 0;
	switch (char(*argv[3])){
		case 'i':
			IncOrd= true;
			break;
		case 'd':
			IncOrd= false;
			break;
		default:
			return 0;
	};
	FileNameInput= argv[1];
	FileNameOutput= argv[2];
	Input.open(FileNameInput);
	ReadLF();
	int CharArr[256], Column[MaxN];
	int Shift= 0, Pos;
	for (int Index= MaxLength- 1; Index>= 0; Index--){
		for (int I= 0; I< 256; I++)
			CharArr[I]= 0;
		for (int I= 0; I<= N; I++){
			Column[I]= GetChar(Index, InArr[I])+ 128;
			CharArr[Column[I]]++;
		};
		if (IncOrd)
			for (int I= 1; I< 256; I++)
				CharArr[I]+= CharArr[I- 1];
		else
			for (int I= 254; I>= 0; I--)
				CharArr[I]+= CharArr[I+ 1];
		Shift= N+ 1- Shift;
		for (int I= 2* (N+ 1)- Shift- 1; I>= (N+ 1)- Shift; I--){
			Pos= Column[OutArr[I]];
			OutArr[CharArr[Pos]+ Shift- 1]= OutArr[I];
			CharArr[Pos]--;
		};
	};
	if ((MaxLength% 2)== 1)
		for (int I= 0; I<= N; I++)
			OutArr[I]= OutArr[I+ N+ 1];
	OutFile();
	Input.close();
	return 0;
}

BSE 12:11, 7 января 2013 (UTC)