BitCell

Problema: in fisierul numere.in se dau citeva numere intregi in intervalul [-10000, 10000] (si nu mai mult de 1000 de numere). Sa se afiseze in fisierul numere.out numerele sortate in ordine crescatoare.

Exemplu: pentru numere.in


se va afisa in fisierul numere.out

Ca şi adăugire, cu limitele impuse de tine (maxim 1000 de numere din [-10000,10000]) se dovedeşte mult mai eficientă sortarea prin numărare dacă vectorul citit are peste 200 de numere. Fiind şi foarte uşor de implementat, eu zic că are un avantaj clar în faţa sortării prin selecţie.
O scurtă implementare în C++:

Ce am urmarit prin postarea acestui algoritm: ceva accesibil si usor de retinut.
Nu am testat programul tau, si ca regula generala nu posta ceva netestat.
Daca vrei sa explici mai bine ca mine, te rog fa asta si nu cu ceva criptic.
Thanks.

emi wrote:Ce am urmarit prin postarea acestui algoritm: ceva accesibil si usor de retinut.

Sortarea prin numărare este (după părerea mea) mult mai simplu de înţeles decât orice altă metodă de sortare din simplul fapt că nu presupune comparări directe ale elementelor. Scopul meu a fost să atrag atenţia că, pentru problema de faţă, este o variantă foarte eficientă şi scurtă, nu să explic cum funcţionează pentru că există deja multă documentaţie pe tema asta.

emi wrote:Nu am testat programul tau, si ca regula generala nu posta ceva netestat.

Asta chiar mi-a stârnit curiozitatea. Cam cum te-ai gândit tu că aş pune pe forum un cod care aş ştii că nu e corect?

Am citeva comentarii:
1. nu respecti enuntul problemei: unde citesti fisierul numere.in ?
2. nu explici algoritmul folosit.
3. solicitarea era sa se afiseze in fisierul numere.out rezultatul.
4. daca ai spus ca algoritmul e mai bun, automat precizeaza ordinul de complexitate, sau macar niste timpi de executie, ca sa arati asta.

1.Nu contează de unde citește numerele. Putea să redirecționeze imputul printr-o singură linie dar era redundant.


2.Putea să explice într-adevăr dar din nou era puțin redundant. Dacă luăm în considerare raportul dintre explicațiile_tale și codul_tău, Mihai dacă ar fi respectat acest raport ar fi trebuit să scrie o linie în care să explice ce face.
Pune fiecare număr într-un vector la indicii potriviți:
Ex: 2 la A[2] , -500 la A[-500] etc.
Singura șmecherie e să știi cum funcționează pointerii și să observi acel define care te lasă să folosești indici negativi.

3. La fel ca și la 1. Din nou se poate redirecționa outputul.


4.Nici tu nu ai precizat niciunde ordinul de complexitate pentru algoritmul prezentat de tine. Ordinul de complexitate pentru algoritmul tău este O(n2) pe când ordinul de complexitate al algoritmului lui Mihai este O(n).

Să nu crezi că îi iau apărarea lui Mihai pentru că este moderator. Enunțul problemei vine ca o mănușă pentru algoritmul propus de el. Este doar o propunere de algoritm de sortare mai bun. Nu cred că este offtopic atât timp cât vine cu o sugestie constructivă.

Ordinul de complexitate pentru algoritmul de sortare prin selectia minimului:

Cautam intr-un vector de n elemente minimul, si il punem primul.
Apoi cautam intr-un vector de n-1 elemente minimul, si il punem al doilea.
Si asa mai departe pina ajungem la ultimul element.
Costul acestor operatii este:
S1 = n + (n-1) + (n-2) + .. + 1.

sa notam sirul urmator:

S2 = 1 + 2 + .. + n.

Daca facem S1 + S2, si adunam pe componente, rezulta n*(n+1).

Deci ordinul de complexitate este n*(n+1)/2 sau simplificat O(n*n).

Algoritmul de sortare prin numarare nu e in nici un caz O(n).
Iti spun ca nici macar teoretic nu se poate sa existe algoritm de sortare O(n).

Sunt alti algoritmi cu ordin de complexitate mai mic, dar asta se dorea ceva introductiv, nu sa fie cel mai eficient.
Pentru mai multe detalii: http://en.wikipedia.org/wiki/Sorting_algorithm

Nici un algoritm de sortare bazat pe comparatii de elemente nu poate fi mai eficient decat O(n * log n) in cazul cel mai nefavorabil. Limita respectiva poate fi demonstrata teoretic.
Evident ca exista algoritmi de sortare in timp liniar, care nu se bazeaza pe comparatii (de exemplu cel explicat deja, sortare prin numarare).

^ se pare ca stii mai mult ca mine, poti sa faci un demo la ordinul de complexitate ?
(stiu ca nu e usor)

La ce demonstratie te referi ? La faptul ca nici un algoritm de sortare bazat pe comparatii nu poate fi mai eficient decat O(n * log n) in cazul cel mai defavorabil ?

^ ai spus liniar, as dori niste precizari.

Eu nu inteleg cum se poate sa existe algoritm de sortare in care NU compari elemente.

http://en.wikipedia.org/wiki/Counting_sort

Eu mă dau bătut...

Problema de baza care trebuie inteleasa aici este: complexitatea unui algoritm de sortare e perfect dependenta de multimea de elemente care se sorteaza. Fiind date anumite proprietati speciale se poate reduce cu mult complexitatea algoritmului de sortare. Mai precis:

- pentru o multime fara niciun fel de precizare referitoare la elementele din ea, adica o multime aleatoare, cea mai buna sortare care se poate obtine prin comparatii e de ordinul O(N*lgN) - dupa cum a spus si Morpheus. Atentie, aici se face referire la numere complet aleatoare, despre care nu se stie nimic altceva.

- pentru multimi cu anumite restrictii / proprietati speciale, se poate reduce cu mult timpul necesar. Sa luam doua exemple:
- pentru un sir de elemente a(1,2*m) care are proprietatea ca prima jumatate a multimii este sortata si cea de-a doua este si ea dar nu neaparat in continuarea primeia, problema se reduce la interclasarea celor doua siruri - adica se va ajunge la O(n)
- acum discutam cazul de fata - cunoscand restrictia ca toate numerele noastre se incadreaza intr-un interval predefinit de forma [a, b] putem crea un vector de elemente v[b-a + 1] in care vom retine, pentru fiecare element, numarul de aparitii. In acest fel, la sfarsit, putem afisa numerele in ordine crescatoare (dupa cum s-a facut si mai sus), rezultand practic vectorul sortat fara niciun fel de comparatie - complexitate: O(n), adica se rezuma la citirea numerelor si incrementarea pozitiei din vector corespunzatoare numarului de aparitii al valorii respectiv. Nu este o sortare "propriu-zisa", dupa cum se prezinta intuitiv o sortare (si anume, folosind comparatii), dar e o solutie paralela care rezolva practic aceasta problema.

Partea dificila din codul oferit de Mihai o constituie macro-ul pe care l-a folosit acolo, #define A (A + 10000). In limbaj matematic, chestia asta s-ar numi abuz de notatie - preprocesorul va avea grija sa inlocuiasca pe A cu A + 10000, care e echivalent cu A[10000] iar in cazul in care am fi avut A[x] ar fi rezultat A[10000 + x], care ar fi rezolvat problema ca vectorul de numarare v este indexat, in "spatiul problemei", de la a la b - in cazul nostru de la -10000 la 10000 - pe cand limbajele C/C++ folosesc indexarea "zero-based" adica pornind de la 0 - practic multimea -10000, -9999, ... , 10000 e mapata catre 0, 1, ..., 20002, dupa care se face artificiul prezentat mai sus - se incrementeaza pozitia din vector corespunzatoare valorii a - adica v[10000 + a] - la fiecare citire a ei. La sfarsit, se vor afisa toate elementele cu numarul de "aparitii" > 0, de un numar de ori egal cu v[10000 + a].

Hope that settles everything

Foarte bine explicat, Adrian! Există o (foarte) mică discordanţă totuşi, care a fost introdusă din vina mea:

Adrian wrote:pe cand limbajele C/C++ folosesc indexarea "zero-based" adica pornind de la 0 - practic multimea -10000, -9999, ... , 10000 e mapata catre 0, 1, ..., 20002

Mulţimea -10000, -9999, ... , 10000 este mapată către 0,1, ... , 20000. Ultimul element al vectorului este "în plus", neputând fi folosit niciodată dacă numerele sunt din intervalul specificat. M-am cam grăbit când am tastat şi am greşit o cifră.
Sunt convins că ţie îţi era clar acest lucru, am specificat pentru ceilalţi pentru a nu-i induce în eroare. Voi modifica şi codul, linia:

devenind

Bineînţeles, codul funcţiona corect şi înainte, este doar un mic retuş.

Salut, Mihai

Corect, ai dreptate, si eu am preluat acolo din codul tau, m-am grabit Oricum, codul ar fi functionat (zic eu) si cu vectorul de dimensiune mai mare fara niciun fel de problema.