Sortowanie łańcuchów string

0

Witam
Mam problem z sortowaniem łańcuchów string.

#include <iostream>
#include <string>
using namespace std;

int main()
{
	int n;
	cout << "Podaj ilość łańcuchów\n";
	cin  >> n;
	string *p;
	p = new string[n]; // dałem tablicę stringów bo nic innego nie przyszło mi do głowy
	
	cout << "Podaj elementy biżuterii\n";
	for (int i = 0; i < n; i++)
	{
		cin >> p[i];
	}
	string min = p[0];
	for (int j = 0; j < n; j++)
	{
		for (int i = j; i < n; i++)
		{
			if (min > p[i])
			{
				min = p[i];
			}	
		}
		p[j] = min;
	}
	cout << "Uporządkowane łańcuchy\n";
	for (int i = 0; i < n; i++)
	{
		cout << p[i] << endl;
	}
	delete [] p;
	return 0;
}
 

Po wpisaniu danych wejściowych na ekranie cztery razy ukazuje się jeden (losowy) z wpisanych łańcuchów. Nie wiecie gdzie popełniłem błąd? korzystam z g++.
PS jest to zadanie ze strony main.edu.pl/pl/archive/oig/1/sor

0

w C++ nie wolno tworzyć tablic.
hę? kto tak powiedział. oczywiście że można.

dałem tablicę stringów bo nic innego nie przyszło mi do głowy
vector<string> byłoby chyba lepsze (dodaj #include <vector>).

i poczytaj o jakimkolwiek algorytmie sortowania.

0

Chyba głównym problemem jest tu to, że chcesz porównywać łańcuchy znaków za pomocą operatora porównania :) No chyba że mnie coś ominęło :)

0

a jak wypełnić wektor z wejścia cin?

string tekst; cin >> tekst; v.push_back(tekst); 

coś takiego?

0

zmieniłem na tablice string na wektor i mam to samo. nie jestem biegly w wektorach wiec dam caly kod jak teraz wyglada:

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main()
{
	int n;
	cout << "Podaj ilość łańcuchów\n";
	cin  >> n;
	vector<string> v;
	cout << "Podaj elementy biżuterii\n";
	string tekst;
	for (int i = 0; i < n; i++)
	{//tu jestem prawie pewien ze cos jest nie tak
		cin >> tekst;
		v.push_back(tekst);
		tekst = 'NULL';
	}
	string min = v[0];
	for (int j = 0; j < n; j++)
	{
		for (int i = j; i < n; i++)
		{
			if (min > v[i])
			{
				min = v[i];
			}	
		}
		v[j] = min;
	}
	cout << "Uporządkowane łańcuchy\n";
	for (int i = 0; i < n; i++)
	{
		cout << v[i] << endl;
	}
	return 0;
}

 

jesli widzicie co jest nie tak to prosze, pomagajcie

0

Przy okazji, to błąd nie jest spowodowany użyciem tablicy (choć wektor jest i tak o wiele lepszy), tylko duplikowaniem minimalnego elementu.

0
Zjarek napisał(a)

Przy okazji, to błąd nie jest spowodowany użyciem tablicy (choć wektor jest i tak o wiele lepszy), tylko duplikowaniem minimalnego elementu.

Dziękuję za pomoc, dzięki Tobie znalazłem błąd. Ale niestety nadal jest źle.

string min;
	for (int j = 0; j < n; j++)
	{
		min = v[j];
		for (int i = j; i < n; i++)
		{
			if (min > v[i])
			{
				min = v[i];
			}	
		}
		v[j] = min;
	}
 

za każdym razem program zachowuje się inaczej, za każdym razem niezrozumiale.

0

Nadal go duplikujesz. Wpisujesz na pozycji j minimalny z następnych stringów w tablicy, zostawiając go na tej pozycji na której był, przez co w tablicy masz po tej operacji dwa stringi minimalne..

0

odnajdujesz najmniejszą wartość dla przdziału <j, n-1>, to jest dobrze.
Problem stanowi co robisz z tym minimum. Twoje przypisanie "v[j] = min;" powoduje, że stara wartość v[j] jest zapominana (tracona bezpowrotnie), a odnalezione minimum jest duplikowane (maż dwie kopie tej wartości: w nowej i starej pozycji).
Poprawa to tak, by zamieniać wartości miejscami i będzie dobrze.

0

nadal źle... ale co?

string min;
	int indeks;
	for (int j = 0; j < n; j++)
	{
		min = v[j];
		for (int i = j; i < n; i++)
		{
			if (min > v[i])
			{
				min = v[i];
				indeks = i;
			}	
		}
		v[indeks] = v[j];
		v[j] = min;
	}
0

dałem w deklaracji indeks na 0, a w warunku pierwszej pętli zamiast

j < n

na

j < n-1

nadal źle

0

Z tym sobie poradziłem.

	string min;
	int indeks = 0;
	for (int j = 0; j < n - 1; j++)
	{
		min = v[j];
		for (int i = j; i < n; i++)
		{
			if (min > v[i])
			{
				min = v[i];
				indeks = i;
			}	
		}
		if (min != v[j])
		{
			v[indeks] = v[j];
		}
		v[j] = min;
	}

Teraz jest taki problem, że owszem, łańcuchy są porównywane... ale tylko kolejnością alfabetyczną. Np.: zamiast kolejno
v
bs
jest:
bs
v
bo 'b' jest w alfabecie przed v. Z tego co czytałem w klasie string < i > są tak przeciążone, żeby dłuższy łańcuch był większy od krótszego. więc co mam zrobić?

0

No to posortuj sobie najpierw od najkrotszego do najdluzszego jesli o to Ci chodzi. Masz funkcje string::length() ktora zwraca dlugosc stringa.

0

ale nawet jeżeli uporządkuje wg dlugosci to pozniej porzadkowanie wg alfabetu to wszystko zepsuje

0

Nie? Po prostu dodaj warunek zeby sortowalo wtedy alfabetycznie kiedy dlugosci zadanych ciagow sa rowne i tyle.

0

Nadal jest źle! Zaraz po pierwszym "min = v[j];" (przed 2 for-em) powinieneś mieć "index = j;", to że na twoim przykładzie zadziałało to przypadek.

0

Jest! Działa, wszystko działa:D Dziękuję Wam wszystkim za pomoc:) Oto ostateczna wersja:

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main()
{
	int n;
	cout << "Podaj ilość łańcuchów\n";
	cin  >> n;
	vector<string> v;
	cout << "Podaj elementy biżuterii\n";
	string tekst;
	for (int i = 0; i < n; i++)
	{
		cin >> tekst;
		v.push_back(tekst);
	}
	string min;
	int indeks;
	unsigned int mindl;
	for (int j = 0; j < n - 1; j++)
	{
		min = v[j];
		indeks = j;
		mindl = v[j].length();
		for (int i = j; i < n; i++)
		{
			if (v[i].length() < mindl)
			{
				mindl = v[i].length();
				min = v[i];
				indeks = i;
			}
		}
		if (mindl != v[j].length())
		{
			v[indeks] = v[j];
		}
		v[j] = min;
	}
	for (int j = 0; j < n; j++)
	{	
		min = v[j];
		indeks = j;
		for (int i = j; i < n; i++)
		{
			for (int i = j; i < n; i++)
			{
				if (v[j].length() == v[i].length())
				{
					if (min > v[i])
					{
						min = v[i];
						indeks = i;
					}        
				
					if (min != v[j])
					{
						v[indeks] = v[j];
					}	
					v[j] = min;
				}
			}
		}
	}

	cout << "Uporządkowane łańcuchy\n";
	for (int i = 0; i < n; i++)
	{
		cout << v[i] << endl;
	}
	return 0;
}
0

coś mi się wydaje że nadal jest źle. Kryterium sortowania masz źle zaimplementowane. powinno być:

                    for (int i = j; i < n; i++)
                        {
                                  if (kryterimPorownania(min, v[i]))
                                  {
                                       min = v[i];
                                       indeks = i;
                                  }        
 
                                   if (min != v[j])
                                   {
                                           v[indeks] = v[j];
                                           v[j] = min;
                                   }      
                        }

Gdzie kryterimPorownania to funkcja opisująca jaką relacje ma spełniać dwa string'i by być we właściwej kolejności.

bool kryterimPorownania(const string& a, const string& b) {
       if (a.lenght()==b.lenght()) {
             return a>b;
       }
       return a.lenght()>b.lenght()
}
0

mi się wydaje, że to to samo tylko inaczej napisane (i ewentualnie wydajniejsze). w każdym razie to co mam działa na wszelkich danych wejściowych więc raczej jest dobrze

0

Napisałem funkcję która porównuje 2 teksty. Opis funkcji jest w komentarzu w kodzie. Funkcja porównuje 2 wyrazy i zwraca odpowiedni znak ">, <, ="

 
#include <iostream>
#include <conio.h>
#include <windows.h>
#include <cmath>
using namespace std;
char STR_SORTOWANIE(char* wyraz1, char* wyraz2, char* wzorzec, int* inny);

/*
Funkcja na podstawie wzorca określi, który wyraz jest mniejszy
Jeżeli wzorzec == NULL wtedy sortowanie będzie alfabetyczne
Funkcja sprawdz we wzorcu co 2 znaki tzn.
wzorzec  = "AaBb" Aa - są równoważne
                  Bb - są równoważne
tak więc jak chcesz posegregować bez znaków równoważnych wpisz "aabb"
Funkcja zwraca > jeżeli wyraz1 jest pierwszy w słowniku
               < jeżeli drugi
               = jeżeli wyrazy są takie same 
Jeżeli ciągi nie są takie same, w zmiennej 'inny' zostanie zapisana pozycja
pierwszego sprawdzanego znaku, który nie był taki sam.
Parametr 'inny' moze przyjąć wartość NULL

*/
char STR_SORTOWANIE(char* wyraz1, char* wyraz2, char* wzorzec, int* inny)
{
     char wzorzec2[]="AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz00112233445566778899";
     if(wzorzec == NULL)
      wzorzec = &wzorzec2[0];
     int d1 = strlen(wyraz1);
     int d2 = strlen(wyraz2);
     int d3 = strlen(wzorzec);
     int d;
     if(d1 >= d2)
      d = d2;
     if(d2 >= d1)
      d = d1;
     for(int n=0; n<d; n++)
     {
          int pozycja1, pozycja2;
          for(int m=0; m<=d3; m+=2)
           if(wyraz1[n] == wzorzec[m] || wyraz1[n] == wzorzec[m+1])
            pozycja1 = m;
          for(int m=0; m<=d3; m+=2)
           if(wyraz2[n] == wzorzec[m] || wyraz2[n] == wzorzec[m+1])
            pozycja2 = m;
          if(pozycja1 < pozycja2)
          {
           if(inny != NULL)
            *inny = n;
           return '>';
          }
          if(pozycja2 < pozycja1)
          {
           if(inny != NULL)
            *inny = n;
           return '<';
          }
     }
     
     if(d1 > d2){
     if(inny != NULL)
      *inny = d1-(d1-d2);
      return '<';}
     if(d2 > d1){
     if(inny != NULL)
      *inny = d2-(d2-d1);
      return '>';}
     if(d2 == d1){
     if(inny != NULL)
      *inny = -1;
      return '=';}
}




int main()
{
    int inny;
    char znak = STR_SORTOWANIE("pUkAwki", "pukawka", NULL, &inny);
    cout<<znak<<endl;
    cout<<inny;
    getch();
}

Według mnie jak masz tablicę char[150][200] wypełnioną tekstem porównuj pierwszy tekst z drugim, z trzecim itd. Jak któryś tekst jest "większy" (nie wiem jak to powiedziec) to porównujesz jego z kolejnymi wyrazami. Jak doszedleś do końca tablicy zerujesz komórki tego wyrazu (największego), wstawiasz go na pierwsza pozycję listy i omijając wyzerowane komórki sprawzdasz od początku wyrazy na tej samej zasadzie jak poprzednio, tym razem zapisujesz je na 2 pozycję listy. Jak wszystkie komórki będą wyzerowane wtedy masz gotowy posortowany tekst.

1 użytkowników online, w tym zalogowanych: 0, gości: 1