636 Restante

[•filipb]

Aici puteţi discuta despre problema Restante.

[•Protoman]

  sunt putin nedumerit... Imi poate explica si mie cineva cum de ia quicku 100 si heapsortu 80 ?

[•wefgef]

Quicksort e cel mai rapid algoritm de sortare .

[•tvlad]

Ce inseamna error: assignment of data-member 'cuvant::orig' in read-only structure?

[•Protoman]

Multumesc.  Eu unul stiam ca heapsortu e cel mai bun... si ca ( , ) quicku trage spre n^2 in caz ca ele sunt deja sortate... eh de-acu in colo daca e fac quick randomizat...

[•cos_min]

Multumesc.  Eu unul stiam ca heapsortu e cel mai bun... si ca ( , ) quicku trage spre n^2 in caz ca ele sunt deja sortate... eh de-acu in colo daca e fac quick randomizat...

Nu are cum sa 'traga' spre O(n^2) cand sunt sortate deja, ci mai degraba 'trage' spre O(n).

[•stef2n]

Nu are cum sa 'traga' spre O(n^2) cand sunt sortate deja, ci mai degraba 'trage' spre O(n).

Ba 'trage' spre O(N^2) pentru ca intotdeauna pivotul e gasit pe prima pozitie. Recurenta e T(N)=O(N)+T(N-1), ceea ce duce la O(N^2).

[•cos_min]

Nu are cum sa 'traga' spre O(n^2) cand sunt sortate deja, ci mai degraba 'trage' spre O(n).

Ba 'trage' spre O(N^2) pentru ca intotdeauna pivotul e gasit pe prima pozitie. Recurenta e T(N)=O(N)+T(N-1), ceea ce duce la O(N^2).

My bad, m-am grabit aiurea.

[•wefgef]

Invatati C++ si STL. Iata un program care sorteaza un vector in C++:

Cod:

#include <cstdio>
#include <algorithm>
using namespace std;

int N;
int v[1024];

void ReadArray() {
    scanf("%d", &N);
    for (int i = 0; i < N; ++i)
        scanf("%d", v+i);
}

int main() {
    ReadArray();
    sort(v, v+N);
}

[•Protoman]

Multumesc de indicatie. Am folosit si eu sortul din stl de cateva ori ( 2 ) dar nu trec de tot in c decat in clasa a 9-a.

[•wefgef]

Ar fi bine sa treci mai repede. Daca te califici la JBOI ai avea un avantaj fata de cei in Pascal .

[•Protoman]

  Daca JBOI pica in vara ca anu trecut atunci se incadreaza la clasa a 9-a .

[•Sycron]

am cateva intrebari.. offtopic
cand vreau sa citesc din fisiere spatiile albe si endline-urile
care e cea mai eficienta metoda?
cea cu resetiosflags sau cu f.get() nu mai stiu cum :/
metoda de sortare din STL e quicksortu' nu ? nam folosit-o niciodata

care e diferenta dintre scanf ("%g", &N)si f<<g

[•Tabara]

care e diferenta dintre scanf ("%g", &N)si f<<g[/i]

Pai scanf e mai rapida.E citire specifica limbajului C, pe cand cu f >> g este specifica C++.
Exemplu daca citesti de la tastatura numarul intreg n, atunci o sa ai

Cod:

scanf( "%d", &n )

sau

Cod:

f >> n; // citirea cu streamuri

[•Sycron]

Si raspunsu' la celelalte 2 intrebari?

cand vreau sa citesc din fisiere spatiile albe si endline-urile
care e cea mai eficienta metoda?
cea cu resetiosflags sau cu f.get() nu mai stiu cum :/
metoda de sortare din STL e quicksortu' nu ? nam folosit-o niciodata

Multumesc 

[•wefgef]

Metoda de sortare din STL este un quicksort modificat. Oricum e mai bun decat ar putea sa scrie cineva de mana (in concurs cel putin).

[•domino]

Metoda de sortare din STL este un quicksort modificat. Oricum e mai bun decat ar putea sa scrie cineva de mana (in concurs cel putin).

Se numeste introsort (http://en.wikipedia.org/wiki/Introsort) de fapt

[•Sycron]

STL se regăseşte şi în BC 3.1 ? (inafară de DJGPP)

[•stef2n]

Nu

[•ciprianf]

Imi poate spune si mie cum fac cu sortarea din STL(introsort) sa sortez liniile la matrici? (in cazul de fata matricea e char)

[•byndrsn]

sort(a[ i ], a[ i ] + N) sorteaza primele N elemente pe linia i

[•ciprianf]

Si eu daca vreau sa sortez liniile?

[•toni2007]

adica? vrei sa sortezi pe linii sau pe coloane? sau vrei sa sortezi liniile intre ele dupa un anumit criteriu?

[•sima_cotizo]

Faci un vector O[ x ]=y => a x-a linie din matricea ordonata este y. Apoi sortezi pe O, dar functia de comparare de fapt va testa liniile corespunzatoare din matrice. Mai clar:

Cod:

int comp(int a, int b) {
	return strcmp( A[a], A[b] ); // compari liniile a si b din matrice
}

int main() {
	// citesti matricea, ii faci ce vrei

	for (i=0; i<n; ++i) O[i] = i;
	sort(O, O+n, comp);

	return 0;
}

[•ciprianf]

adica? vrei sa sortezi pe linii sau pe coloane? sau vrei sa sortezi liniile intre ele dupa un anumit criteriu?

Vreau sa sortez liniile intre ele dupa un anumit criteriu

sima_cotizo nu cred ca ma ajuta ideea ta.....eu vreau sa le sortez sortez:D