Jump to content

SUBIECTE NOI
« 1 / 5 »
RSS
Incalzire casa fara gaz/lemne

Incalzire in pardoseala etapizata

Suprataxa card energie?!

Cum era nivelul de trai cam din a...
 probleme cu ochelarii

Impozite pe proprietati de anul v...

teava rezistenta panou apa calda

Acces in Curte din Drum National
 Sub mobila de bucatarie si sub fr...

Rezultat RMN

Numar circuite IPAT si prindere t...

Pareri brgimportchina.ro - teapa ...
 Lucruri inaintea vremurilor lor

Discuții despre TVR Sport HD.

Cost abonament clinica privata

Tremura toata, dar nu de la ro...
 

Sortarea din perspectiva ingineriei software

- - - - -
  • Please log in to reply
9 replies to this topic

#1
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 30,194
  • Înscris: 24.02.2007
La inceput, elevii/studentii invata cum sa sorteze un vector de intregi folosind un algoritm banal. Toate bune pana aici. Mai departe invata algoritmi tot mai complecsi, dar mai rapizi de sortare. Utili si acestia.

Apoi insa apare un vid, lipseste cel mai important lucru din punct de vedere al practicii: cum sortam structuri mai complexe, eventual chiar dupa multiple criterii?

Pasii de mai jos arata cum se poate adapta o functie banala de sortare pentru a face fata acestor nevoi practice. Ea ajunge sa semene foarte mult cu std::sort, functia oferita de standardul C++.

Cod initial
#include <algorithm>

void sorteaza(int valori[], int numarValori)
{
	bool efectuatInterschimbare;
	do
	{
		efectuatInterschimbare = false;
		for (int i = 1; i < numarValori; ++i)
		{
			if (valori[i] < valori[i - 1])
			{
				std::swap(valori[i], valori[i - 1]);
				efectuatInterschimbare = true;
			}
		}
	}
	while (efectuatInterschimbare);
}

int main()
{
	int valori[] = { 1, 3, 5, 7, 2, 4, 6 };
	sorteaza(valori, 7);
}


Pas 1 – Numarul de valori nu poate fi negativ, deci folosim un tip unsigned
#include <algorithm>

void sorteaza(int valori[], unsigned int numarValori)
{
	bool efectuatInterschimbare;
	do
	{
		efectuatInterschimbare = false;
		for (unsigned int i = 1; i < numarValori; ++i)
		{
			if (valori[i] < valori[i - 1])
			{
				std::swap(valori[i], valori[i - 1]);
				efectuatInterschimbare = true;
			}
		}
	}
	while (efectuatInterschimbare);
}

int main()
{
	int valori[] = { 1, 3, 5, 7, 2, 4, 6 };
	sorteaza(valori, 7);
}


Pas 2 – Poate nu dorim sa sortam intreg vectorul ci doar o parte a sa, asa ca il transmitem ca pointer
#include <algorithm>

void sorteaza(int* valori, unsigned int numarValori)
{
	bool efectuatInterschimbare;
	do
	{
		efectuatInterschimbare = false;
		for (unsigned int i = 1; i < numarValori; ++i)
		{
			if (valori[i] < valori[i - 1])
			{
				std::swap(valori[i], valori[i - 1]);
				efectuatInterschimbare = true;
			}
		}
	}
	while (efectuatInterschimbare);
}

int main()
{
	int valori[] = { 1, 3, 5, 7, 2, 4, 6 };
	//sorteaza(valori, 7);
	sorteaza(valori + 2, 4); //sortam doar 5, 7, 2, 4
}


Pas 3 – Vrem sa sortam alte tipuri de date, nu doar valori intregi, asa ca introducem templates
#include <algorithm>

template<typename T>
void sorteaza(T* valori, unsigned int numarValori)
{
	bool efectuatInterschimbare;
	do
	{
		efectuatInterschimbare = false;
		for (unsigned int i = 1; i < numarValori; ++i)
		{
			if (valori[i] < valori[i - 1])
			{
				std::swap(valori[i], valori[i - 1]);
				efectuatInterschimbare = true;
			}
		}
	}
	while (efectuatInterschimbare);
}

int main()
{
	int valori[] = { 1, 3, 5, 7, 2, 4, 6 };
	sorteaza(valori, 7);

	double alteValori[] = { 2.5, 3.1, 1.6 };
	sorteaza(alteValori, 3);
}


Pas 4 – Vrem sa sortam un vector compus din structuri, invatam compilatorul ce inseamna < in cazul structurilor
#include <algorithm>

struct Elev
{
	int varsta;
	double medieLimbaRomana;

	bool operator<(const Elev& altElev) const
	{
		return varsta < altElev.varsta; //comparam doar varsta celor doi elevi
	}
};

template<typename T>
void sorteaza(T* valori, unsigned int numarValori)
{
	bool efectuatInterschimbare;
	do
	{
		efectuatInterschimbare = false;
		for (unsigned int i = 1; i < numarValori; ++i)
		{
			if (valori[i] < valori[i - 1])
			{
				std::swap(valori[i], valori[i - 1]);
				efectuatInterschimbare = true;
			}
		}
	}
	while (efectuatInterschimbare);
}

int main()
{
	Elev elevi[] =
	{
		{ 15, 8.5 },
		{ 18, 10 },
		{ 17, 7.6 },
		{ 17, 4.5 }
	};
	sorteaza(elevi, 4); //sortam elevii crescator dupa varsta
}


Pas 5 – Dorim sa putem sorta si in alt mod (elevi dupa medie de exemplu) sau in alta ordine (descrescator) asa ca extragem comparatia separat
Codul de mai sus functioneaza atunci cand dorim sortarea crescatoare a elevilor dupa varsta, dar are un mare neajuns cand dorim sa ii sortam dupa un alt criteriu: operator< nu poate fi definit in mai multe moduri in acelasi timp. Drept urmare, trebuie gasit un mod de a transmite la fiecare sortare cum dorim sa comparam structurile.z
#include <algorithm>

struct Elev
{
	int varsta;
	double medieLimbaRomana;
};

bool comparaEleviDupaVarstaCrescator(const Elev& elev1, const Elev& elev2)
{
	return elev1.varsta < elev2.varsta;
}

bool comparaEleviDupaMedieLimbaRomanaDescrescator(const Elev& elev1, const Elev& elev2)
{
	return elev1.medieLimbaRomana > elev2.medieLimbaRomana;
}

template<typename T, typename FunctieComparareMaiMic>
void sorteaza(T* valori, unsigned int numarValori, FunctieComparareMaiMic comparareMaiMic)
{
	bool efectuatInterschimbare;
	do
	{
		efectuatInterschimbare = false;
		for (unsigned int i = 1; i < numarValori; ++i)
		{
			if (comparareMaiMic(valori[i], valori[i - 1]))
			{
				std::swap(valori[i], valori[i - 1]);
				efectuatInterschimbare = true;
			}
		}
	}
	while (efectuatInterschimbare);
}

int main()
{
	Elev elevi[] =
	{
		{ 15, 8.5 },
		{ 18, 10 },
		{ 17, 7.6 },
		{ 17, 4.5 }
	};
	sorteaza(elevi, 4, comparaEleviDupaVarstaCrescator); //sortam elevii crescator dupa varsta
	sorteaza(elevi, 4, comparaEleviDupaMedieLimbaRomanaDescrescator); //sortam elevii descrescator dupa medie limba romana
}


Pas 6 – Dorim sa putem sorta si alte structuri de date, de exemplu std::vector asa ca solicitam iteratori
#include <algorithm>
#include <iterator>
#include <vector>

struct Elev
{
	int varsta;
	double medieLimbaRomana;
};

bool comparaEleviDupaVarstaCrescator(const Elev& elev1, const Elev& elev2)
{
	return elev1.varsta < elev2.varsta;
}

bool comparaEleviDupaMedieLimbaRomanaDescrescator(const Elev& elev1, const Elev& elev2)
{
	return elev1.medieLimbaRomana > elev2.medieLimbaRomana;
}

template<typename Iterator, typename FunctieComparareMaiMic>
void sorteaza(Iterator delaInclusiv, Iterator panaLaExclusiv, FunctieComparareMaiMic comparareMaiMic)
{
	bool efectuatInterschimbare;
	do
	{
		efectuatInterschimbare = false;
		Iterator curent = delaInclusiv;
		Iterator urmator = curent;
		++urmator;

		for (; urmator < panaLaExclusiv; ++curent, ++urmator)
		{
			if (comparareMaiMic(*urmator, *curent))
			{
				std::swap(*curent, *urmator);
				efectuatInterschimbare = true;
			}
		}
	}
	while (efectuatInterschimbare);
}

int main()
{
	Elev elevi[] =
	{
		{ 15, 8.5 },
		{ 18, 10 },
		{ 17, 7.6 },
		{ 17, 4.5 }
	};
	sorteaza(std::begin(elevi), std::end(elevi), comparaEleviDupaVarstaCrescator);

	std::vector<Elev> altiElevi =
	{
		{ 15, 8.5 },
		{ 18, 10 },
		{ 17, 7.6 },
		{ 17, 4.5 }
	};
	sorteaza(std::begin(altiElevi), std::end(altiElevi), comparaEleviDupaMedieLimbaRomanaDescrescator);
}


Tema de casa

  • Sortarea elevilor atat dupa varsta cat si dupa medie (cei ce au aceeasi varsta, sa fie sortati duap medie).
  • Adaptarea functiei sorteaza cu un algoritm mai rapid de sortare


#2
halflife

halflife

    Member

  • Grup: Members
  • Posts: 761
  • Înscris: 31.05.2015
Programatorii de succes trebuie sa stie algoritmi din astia in C++ ?

#3
baliosss

baliosss

    Unstoppable

  • Grup: Senior Members
  • Posts: 6,374
  • Înscris: 30.01.2016
^Posted Image

Edited by baliosss, 16 December 2017 - 15:58.


#4
Al3xandru35

Al3xandru35

    Active Member

  • Grup: Members
  • Posts: 1,325
  • Înscris: 30.09.2011
Tot nu ai plecat ma? Ti-e rau de viata de stai si pierzi vremea pe forum-uri in loc sa pui osu' la treaba?

#5
DaculScoril0

DaculScoril0

    Senior Member

  • Grup: Senior Members
  • Posts: 6,670
  • Înscris: 03.12.2014

View Postdani.user, on 16 decembrie 2017 - 15:20, said:

La inceput, elevii/studentii invata cum sa sorteze un vector de intregi folosind un algoritm banal. Toate bune pana aici. Mai departe invata algoritmi tot mai complecsi, dar mai rapizi de sortare. Utili si acestia.

Apoi insa apare un vid, lipseste cel mai important lucru din punct de vedere al practicii: cum sortam structuri mai complexe, eventual chiar dupa multiple criterii?

Pasii de mai jos arata cum se poate adapta o functie banala de sortare pentru a face fata acestor nevoi practice. Ea ajunge sa semene foarte mult cu std::sort, functia oferita de standardul C++.

[.....]

Tema de casa
  • Sortarea elevilor atat dupa varsta cat si dupa medie (cei ce au aceeasi varsta, sa fie sortati duap medie).
  • Adaptarea functiei sorteaza cu un algoritm mai rapid de sortare

tot ce pot zice e să-ți recomand volumul I din ”Arta programării calculatoarelor” a lui Donald Knuth. A fost tradus și în română cred că că la editura Teora prin anii 90.
Tot ce zicea omul ăla acum 30 de ani când a scris volumele astea (șapte + la număr) este la fel de actual și acum și va fi și peste 50 de ani că sunt chestii de teorie fundamentală.
Astea fiind zise, spor la citit!

PS: algoritmul prezentat de tine e unul din cele mai puțin eficiente, poți lua ca temă  de casă să vezi de ce.

View Posthalflife, on 16 decembrie 2017 - 15:53, said:

Programatorii de succes trebuie sa stie algoritmi din astia in C++ ?
nu, acum e c#

Edited by DaculScoril0, 17 December 2017 - 05:34.


#6
Geth

Geth

    Senior Member

  • Grup: Senior Members
  • Posts: 2,903
  • Înscris: 17.11.2017

View PostDaculScoril0, on 17 decembrie 2017 - 05:35, said:

tot ce pot zice e să-ți recomand volumul I din ”Arta programării calculatoarelor” a lui Donald Knuth.
Tu l-ai citit si l-ai inteles? Cumva si pe celalalte?

#7
Mosotti

Mosotti

    Geniu umil

  • Grup: Senior Members
  • Posts: 33,295
  • Înscris: 21.04.2004

View PostDaculScoril0, on 17 decembrie 2017 - 05:35, said:

PS: algoritmul prezentat de tine e unul din cele mai puțin eficiente, poți lua ca temă  de casă să vezi de ce.
A folosit intentionat acel "algoritm ineficient", pentru ca nu algoritmul este idea acestui thread, ci cum poti folosi alte tipuri de date decit ce te invata la liceu (de obicei sa sortezi niste integeri). Chiar spune la sfirsit "Adaptarea functiei sorteaza cu un algoritm mai rapid de sortare". Deci faptul ca a folosit bubble sort este irelevant, la fel de irelevant este si faptul ca vorbesti de Donald Knuth. Crezi ca ai citit Donald Knuth si esti bazat? Facem o sesiune Skype inregistrata in care sa-ti pun intrebari din cartile alea, ca sa vedem ce-ai retinut?

#8
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 30,194
  • Înscris: 24.02.2007
Nu-i nevoie de atacuri in stilul "esti bazat". In rest a rezumat bine Mosotti scopul acestui topic.

#9
Mosotti

Mosotti

    Geniu umil

  • Grup: Senior Members
  • Posts: 33,295
  • Înscris: 21.04.2004
"Esti bazat" nu-i atac. Bazat inseamna bogat sau profi in limbaj de carter, zi de zi impreuna, dusmanii mor cind ne descurcam mabine :w00t:

#10
DaculScoril0

DaculScoril0

    Senior Member

  • Grup: Senior Members
  • Posts: 6,670
  • Înscris: 03.12.2014

View PostGeth, on 17 decembrie 2017 - 08:52, said:

Tu l-ai citit si l-ai inteles? Cumva si pe celalalte?

nu cred că  te născusei când le-am citit eu.

Anunturi

Bun venit pe Forumul Softpedia!

0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users

Forumul Softpedia foloseste "cookies" pentru a imbunatati experienta utilizatorilor Accept
Pentru detalii si optiuni legate de cookies si datele personale, consultati Politica de utilizare cookies si Politica de confidentialitate