Programare

[Ganav]

Avem banalul algoritm de sortare bubblesort implementat in C++:

void bubblesort(std::vector<int>& a) {
	int temp = 0;
	for(size_t i = 1; i < a.size(); i++) 
		for(size_t j = 0; j < a.size(); j++) {
			if(a[j] > a[i]) {
				temp = a[j];
				a[j] = a[i];
				a[i] = temp;
			}
		} 
}

int main(int argc, char **argv) {

	std::vector<int> a;
	a.push_back(23);
	a.push_back(12);
	a.push_back(15);
	bubblesort(a);
        return 0;
}

Care ar fi mijloacele prin care am putea optimiza functia de mai sus astfel incat sa nu modificam algoritmul(de ex in quicksort, shackersort, insertsort, etc)?

Nu avem voie sa folosim inline assembly si nici sa implementam functia in limbaj de asamblare. Statia de lucru este o masina generica IA32.

[dancezar]

Ca o completare pleci cu i de la 0 (bine acolo e 1 dar ipotetic vorbind) sa zicem , j o sa porneasca tot de la 0 cea ce inseamnaca se v-a compara elementul a[0] cu a[0] + elementele din spate care au fost deja comparate si interschimbate , consuma timp ca sa fie mai ok j trebuie sa porneasca de la elemntul i +1 pana la ultimul

for(i=0;i<a.size;i++)

for(j=i+1;j<a.size;j++)

..........................

Edited June 20, 2014 by danyweb09

[Ganav]

Esti pe drumul cel bun. Dar inca se mai pot aduce imbunatatiri.

[H3xoR]

Esti pe drumul cel bun. Dar inca se mai pot aduce imbunatatiri.

Dac? nu e prea old thread-ul, o idee de optimizare ar fi:

void bubblesort(std::vector<int>& a)
{
	bool sortat;
	size_t k = a.size() - 1;
	do
	{
		sortat = true;
		for (size_t i = 0; i < k; i++)
		{
			if (a[i] > a[i + 1])
			{
				int aux = a[i];
				a[i] = a[i + 1];
				a[i + 1] = aux;
				sortat = false;
			}
		}
	}
	while (!sortat);
}