Witam! Przeszukałem trochę net i nic nie znalazłem na temat sortowania string'ów. Mam taki plik polish.txt, znalazłem go w katalogu z jednym programem. Jest to zapewne słownik języka polskiego + inne wyrazy (pewnie nie wszystkie słowa są). Plik zawiera 148.655 słów. Chciałbym teraz napisać program do zarządzania tym słownikiem. Rzeczy typu dodaj/usuń to dla mnie żaden problem. Problemem jest dla mnie posortowanie tego (alfabetycznie oczywiście). Nie wiem jakiego algorytmu użyć ani w ogóle jak się do tego zabrać. Niby plik jest posortowany, ale jak patrzę to nie zbyt do końca, poza tym przy dodawaniu wyrazów miło by było jakby posortował jeszcze raz lub może wsadził od razu we właściwe miejsce, co by zajęło mniej czasu. Proszę o pomoc fachowców.
Kiedyś (w sumie to już dość dawno) miałem za zadanie posortować trochę stringów, na szczęście mieściło się to w pamięci (640kB).
Sprawdziłem pierwsze co przyszło do głowy (bąbelki), dałem kilka słów do posortowania, przeszło ładnie to dawaj...
I program się zepsuł :-) nie mogłem doczekać się na wyniki.
Sprawdź Quicksort, pesymistycznie tak zły jak sortowanie bąbelkowe, praktycznie nie zastąpiony (prawie).
Dobry może być też kopiec (heap)
std::set powinien załatwić sprawę.
Na dużo stringów nic lepszego niż Radix nie wymyślisz
Przy założeniu że słownik jest cały czas posortowany to std::set starcza.
A czy mógł by ktoś opisać działanie std::set, bo z tego co na cplusplus.com piszą to zbytnio nie wiem jak się z tym obejść. Może jakieś przykłady? Kurde, wy-Google'ować na polskich stronach nic nie mogę ;/ W tym czasie poszukam coś o innych sposobach co podaliście.
#include <cstdio>
#include <set>
#include <string>
int main() {
std::set<std::string> mapaStringow;
mapaStringow.insert("Gienek");
mapaStringow.insert("Zdzisiek");
mapaStringow.insert("Andrzej");
mapaStringow.insert("Jasiek");
for (std::set<std::string>::iterator it = mapaStringow.begin(); it != mapaStringow.end(); ++it) {
puts(it->c_str());
}
return 0;
}
Są też zresztą przykłady na stronie: http://www.cplusplus.com/reference/stl/set/insert/
Ok, czyli po wykonaniu tego mam już posortowany tą mapę stringów? A parametry inserta to u mnie będzie getline z pliku?
albo std::sort, użyłem go do zrobienia pewnego zadania i tekst 1,5MiB dość szybko posortował.
Musisz napisać samemu funkcję porównującą, bo powineneś potraktować jeszcze polskie znaki. Przede wszystkim sprawdź jakie masz kodowanie pliku i jakie kody mają dane znaki (niektóre kodowania takie jak UTF8 dla znaków specjalnych i narodowych potrzebują 2 bajty, więc 2 chary).
Dałbym ci mój algorytm, ale on niezbyt specjalnie uważał na te znaki (w zadaniu nie było sprecyzowanego kodowania, a komisja na moje maile nie odpowiadała, więc wziąłem pod uwagę kilka, w rezultacie nie wszystkie znaki prawidłowo były sortowane)
Ten słownik nie ma polskich znaków :) na razie bawię się Radix Sort'em, działa z int'ami tylko nie wiem jak teraz przerobić to na stringi :( Kod:
int RadixSort(int array[], int size) //jak tablicę int'ów przemienić na tablicę stringów to wiem, ale żeby sortowało czyli rozkładało na pojedyncze znaki
{
int temp;
int m = 0;
vector < vector <int> > buckets;
buckets.resize(10);
//Begin Radix Sort:
for (int i = 0; i < 7; i++) //Determine which bucket each element should enter
{
for (int j = 0; j < size; j++)
{
temp = (int)( (array[j] ) / pow(10, i) ) % 10;
buckets[temp].push_back( (array[j]) );
}
for (int k = 0; k < 10; k++) //Transfer wynikow do glownej tablicy
{
for (int l = 0;l < buckets[k].size(); l++)
{
array[m] = buckets[k][l];
m++;
}
buckets[k].clear(); //Czyszczenie poprzedniego kontenera
}
m = 0;
}
buckets.clear();
PrintArray(array, size);
}
void PrintArray(int array[], int length)
{
for (int i = 0; i < length; i++) cout << array[i] << endl;
}
int main()
{
int size;
cout << "Podaj wielkosc tablicy: ";
cin >> size;
int input[size];
for (int i = 0; i < size; i++)
{
cout << "Podaj wartosc dla elementu " << i << ".: ";
cin >> input[i];
}
RadixSort(input, size);
return 0;
}
No i nie wiem jak przemianować algorytm na pojedyncze znaki to znowu on je posortuje i z wyrazu "babcia" będę miał "aabbci", a ja chcę całe wyrazy, kur...
wersja 1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 20
char t[100][MAX];
int main(void) {
int i, n=0;
while(gets(t[n++]))
;
for(i=0;i<n;i++) printf("%s\n",t[i]); printf("\n");
qsort(t, n, MAX, strcmp);
for(i=0;i<n;i++)printf("%s\n",t[i]); printf("\n");
return 0;
}
wersja 2, to samo, ale wszystko pokazane
#include <stdio.h>
#define MAX 20
char t[100][MAX];
int cmp(char * a, char * b){
while(((*a) * (*b)) && ((*a) == (*b)) {
a++; b++;}
return (*a) - (*b);
}
void QuickSort(int Lo, int Hi) {
int i,j;
char * x;
x = t[(Lo+Hi)>>1];
i = Lo;
j = Hi;
do {
while (cmp(t[i], x)<0) ++i;
while (cmp(t[j], x)>0) --j;
if (i<=j) {
char tmp; int k;
for(k=0;k<MAX;k++){
tmp= t[i][k]; t[i][k] = t[j][k]; t[j][k] = tmp;
}
++i; --j;
}
} while(i < j);
if (Lo < j) QuickSort(Lo, j);
if (Hi > i) QuickSort(i, Hi);
}
int main(void) {
int i, n=0;
while(gets(t[n++])) ;
for(i=0;i<n;i++)printf("%s\n",t[i]); printf("\n");
QuickSort(0, n-1);
for(i=0;i<n;i++)printf("%s\n",t[i]); printf("\n");
return 0;
}
i wersja 3, szybsza. nie przestawia słów tylko wskaźniki
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int cmp(char ** a, char ** b){
return strcmp(*a,*b); }
char * t[100];
int main(void) {
int i,n=0; char buf[100];
while(gets(buf)) {
t[n]=malloc(strlen(buf)+1);
strcpy(t[n++], buf);
}
for(i=0;i<n;i++)printf("%s\n", t[i]); printf("\n");
qsort(t, n, sizeof(t[0]),cmp);
for(i=0;i<n;i++)printf("%s\n", t[i]); printf("\n");
return 0;
}
Mój faworyt
char * t[DoSyta];
void QuickSort(int Lo, int Hi) {
int i,j;
char * x;
x = t[(Lo+Hi)>>1];
i = Lo;
j = Hi;
do {
while (strcmp(t[i], x)<0) ++i;
while (strcmp(t[j], x)>0) --j;
if (i<=j) {
char * tmp;
tmp= t[i]; t[i] = t[j]; t[j] = tmp;
++i; --j;
}
} while(i < j);
if (Lo < j) QuickSort(Lo, j);
if (Hi > i) QuickSort(i, Hi);
}
Spoko, tyle, że zbytnio nie kapuję jak to działa. Co to jest Lo a co Hi? Tzn. co podaje się za te parametry. I ogólnie o co tu chodzi, nie sam algorytm, ale po krótce. Chodzi mi o ten twój faworyt. I jak wielką dać tablicę char *t[DoSyta];? Ta tablica to jeden wyraz czy jak, bo chyba do niej nie wrzucę wszystkich słów?
na razie nic nie wymyśliłem i zacząłem pisać własny algorytm :D Tylko nie wiem dlaczego, po "sortowaniu" vector staje się puuusty. Kod:
int main()
{
fstream file("polish.txt", fstream::in);
char word[256];
cout << "Wczytywanie danych..." << endl;
while ( file.getline(word, 256) )
{
words.push_back(word); //tu wiadomo
}
cout << "Zakonczono wczytywanie" << endl;
cout << "Sortowanie..." << endl;
for (int i = 0; i < (int)words.size(); i++) //1. pętla do wczytywania po kolei wyrazów...
{
string s1 = words[i]; //biorę jeden wyraz
for (int j = 0; j < (int)words.size(); j++) ...2. pętla do sprawdzania czy jakiś wyraz nie poprzedza go w słowniku, jak tak to zamienia
{
string s2 = words[j]; //biorę drugi do sprawdzenia
if (s1 > s2) //moja świetna procedura na zamianę stringów w vectorze, może tu jest coś źle?
{
string stary;
stary = words[i];
words[i] = words[j];
words[j] = stary;
}
}
}
file.close();
for (int i = 0; i < (int)words.size(); i++)
{
cout << words[i] << endl;
}
//to skomentowałem, bo mi plik psuł przez to, że vector pusty:
/*
file.open("polish.txt", fstream::trunc | fstream::out);
for (int i = 0; i < (int)words.size(); i++)
{
file << words[i];
}
*/
cout << "Zakonczono sortowanie" << endl;
return 0;
}
I tak sobie to wymyśliłem, lecz nie wiem gdzie jest błąd. Dodam też, że if (s1 > s2) wziąłem z mojej książki do infy, tam takie coś było tylko, że na odwrót if (s1 < s2) to wtedy jest wcześniej a ja zrobiłem na odwrót i jeżeli później (tak mi się wydaje) to zamień. Pewnie tu coś gdzieś zwaliłem.