|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergiy Kanilo 2:5020/400 30 Apr 2002 00:19:14
To : Andrey Belyakov
Subject : Re: Сортировка
--------------------------------------------------------------------------------
"Andrey Belyakov" <andrejb@netmail.lv> wrote in message
news:aak4tm$ook$1@host.talk.ru...
> > >> >> Кто-нибудь не подскажет алгоритмы сортировки массива строк по
> > >> >> алфавиту?
> > >> AB> Пузырьком. Hичто другое на произвольных строках не будет
> > >> AB> работать.
> > >> Что значит не будет работать ?
> Я уже объяснил - ничто другое работать не будет.
Это ИМХО не объяснение, ну и что с того, что ручками сделали ошибку,
возможно, ты подразумеваешь какое-то дополнительное требование,
которого не говоришь (например невыделение дополнительной памяти,
но этого в исходной постановке не было).
Вот результат
Before sort
zzxxc
abc
zzzxxc
abbc
After sort
abbc
abc
zzxxc
zzzxxc
Я засчитал \0\0 за конец списка, если это должно считаться строкой
нулевой длины - это легко принять во внимание.
Hиже сама программка. Писана на скорую руку, но следует учесть,
что стандартная C++ std::sort основана на quicksort и обеспечивает
в среднем O(NlnN) операций сравнения, а для std::string операция
сравнения (упорядочивания) определена
#include <algorithm>
#include <string>
#include <vector>
#include <iostream>
char input[] ="zzxxc\0abc\0zzzxxc\0abbc\0";
int main(){
std::vector<std::string> vs;
const char* begin =input;
const char* end =input+sizeof(input)/sizeof(*input);
while(*begin){
const char *lineend =&*std::find(begin,end,'\0');
if(lineend==begin) break;
vs.push_back( std::string(begin,lineend) );
begin =lineend+1;
}
// vs.push_back(""); // для теста добавить строку нулевой длины
std::cout << "Before sort" << std::endl;
std::copy(
vs.begin(),
vs.end(),
std::ostream_iterator<std::string>(std::cout,"\n")
);
std::sort(vs.begin(),vs.end());
std::cout << "\nAfter sort" << std::endl;
std::copy(
vs.begin(),
vs.end(),
std::ostream_iterator<std::string>(std::cout,"\n")
);
}
Cheers,
Serge
--- ifmail v.2.15dev5
* Origin: Sent via Graf's Inn at news://news.relhum.org (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
