Verificare sortare lista C#

Am urmatoarea lista si am adaugat anumite valori cu functia Add()

List<Int32> list = new List<Int32>();
...
list.Add(varNumar);

Lista are avea urmatoarele valori: {0, 3, 6, 9} sau {1, 7, 9, 5}

Cum verific ca lista e sortata? Din pacate nu stiu sa caut pe net sa gasesc un exemplu care sa se potriveasca cu ce vreau eu. Peste tot e cum sa sortez lista sau cum sa compar valorile a doua liste.

Se poate face cu foreach ceva de genul?

foreeach ( int s in list)
{
...
}

Daca da, cum?
Daca nu, cum altcumva?

Edited by Bursul, 23 May 2022 - 13:40.

Sortata in ordine crescatoare? In for compari fiecare element cu elementul precedent si daca e mai mare sau egal inseamna ca e sortata.

 Bursul, on 23 mai 2022 - 13:38, said:

Daca ai doar astea functii sort() si compare(), cum iti dai seama ca o lista este sortata?
In romana, fara cod.

int minim=int.MinValue;
bool sortat=true;

foreach(int i in list)
{
   if( i< minim)
   {
	  sortat=false;
	  break;
   }
   minim=i;
}
// aici variabila sortat va avea valoarea care trebuie

Cum depisteaza asta ca 1 2 4 3 nu e sortat?

 maccip, on 23 mai 2022 - 21:04, said:

Mersi Codul ala gaseste minimul din lista, nu e exact ce vreau.

Insa sigur nu m-am exprimat la inceput cum trebuie. Deci avem o lista si speram sa pot face ceva de genul:

foreach ( int s in list)
{
	 if (s.actual > s.urmator)
		 Eroare
}

Nu intreb de algoritm in sine, ci intrebarea tine mai mult de C#, daca se poate verifica simplu daca o lista e ordonata crescator sau descrescator. Poate e o functie de genul: list.isSort().
De exemplu exista functie care iti sorteaza automat lista: list.Sort(). Poate era si o functie care sa verifice.

Doream sa scap de "for".

Nu cred sa existe o asemenea functie in librarie, insa functiile din librarie nu sunt mai presus de cele scrise de tine.
Daca vrei sa para mai "dă librărie", atunci poti folosi "Extension Methods in C#" pentru clasa List<int> .Chestia asta a fost introdusa mai tarziu in C#, pe la versiunea 3.0 parca.

Adica scrii functia care testeaza daca e sortata cam asa...

public static bool IsSorted(this List<int> list)
{
		 //bla bla bla
}

Si o folosesti in codul tau ca si cum ar fi parte din List<>, "dă librărie", cam asa.

if( list.IsSorted() )
{
//bla bla bla
}

Acuma, deoarece limbajul permite existenta acestor extensii, care aduc mai multa functionalitate unei clase in afara acestei clase, exista teoretic posibilitatea ca extensia care face IsSorted() sa existe undeva (altundeva decat in List<> ). Si cat timp exista aceasta posibilitate, cum non-existenta nu poate fi dovedita decat prin cautare exhaustiva in toata libraria, e greu de dat raspuns solid la aceasta intrebare.
Daca aceasta extensie ar exista intr-un anume DLL si sub un anume namespace, atunci trebuie referit acel DLL la proiect si acel namespace

using DăLibrărieExtensionNamespace;

Pentru ca apoi, IDE-ul sa-ti recunoasca extensia (sa ti-o arate dupa ce pui punctul dupa o lista) si pentru a o putea folosi.

Dar mai bine o scrii tu, ca nu-i cu nimic mai prejos fata de una din librarie.

Edited by maccip, 24 May 2022 - 10:11.

e mai siplu sa te asiguri ca e sortata asa de cate ori ai nevoie.

list.Sort( e => e.element);

sau cu linq

pets = pets.OrderBy(pet => pet.Age).toList()

Logica spune ca ai nevoie oricum de sortare daca vrei s-o verifici asa ca de ce ai mai consuma timp cu verificarea ?

Referinte
https://docs.microso...by?view=net-6.0
https://docs.microso...rt?view=net-6.0

 Bursul, on 24 mai 2022 - 08:43, said:

Pentru ca se sorteaza cand ai nevoie, nu se mai verifica.
S-a eliminat pasul de verificare ptr ca nu are sens, oricum ai nevoie de ea sortata mai departe asa ca o sortezi si gata
Sortarea aplicata (inutil) pe o lista deja sortata este fix la fel de costisitoare ca verificarea daca e sortata scrisa manual de utilizator ptr ca oricum a fost eliminata din framework ca fiind operatie inutila

Edited by radu103, 24 May 2022 - 10:17.

 Nenea Zap, on 23 mai 2022 - 14:49, said:

Tot nu ai răspuns la întrebarea asta.
Așa afli și cum arată codul.

Sort() dureaza O(n log(n)) iar IsSort() dureaza doar O(n).

 Bursul, on 24 mai 2022 - 08:43, said:

C++ are https://en.cpprefere...rithm/is_sorted
.NET nu stiu sa aibe, dar e banal de scris/generalizat pentru ICollection<>

Quote

Logica nu spune neaparat asta, dar in general, functie de algoritmul de sortare, s-ar putea sa nu fie O(N) pe 'best case scenario':
https://en.wikipedia...n_of_algorithms

 Nenea Zap, on 24 mai 2022 - 10:24, said:

Doream o solutie rapida, nu am timp de dezbateri.

Dpmdv subiectul e terminat. S-a rezolvat cu un for, nu e ceea ce am vrut, dar isi face treaba. Consider ca nu se poate face cum am vrut eu, asta e, astept pe aia de la MS sa vina cu ceva mai inteligent

Microsoft au o privire mai lolistica asupra a ceea ce pun in librarii.
IsSorted nu e o functie care sa foloseasca la ceva din mai multe puncte de vedere.

Asta pentru ca, de regula un algoritm "bine facut", are nevoie sa afle daca IsSorted() si apoi are nevoie imediat de prima valoare pentru care IsSorted() face sa returneze false, iar metoda IsSorted() asa cum este ea, nu poate returna decat acel boolean. Daca ti-a returnat false, atunci se presupune ca trebuie sa faci ceva cu lista aia, incepand tocmai din pozitia unde ti-a dat fail la verificarea sortarii.
Altfel, functia ar fi doar una de tip informativ, care returneaza un singur bit de informatie cu privire la o cantitate posibil uriasa de informatie. In general subalgoritmii, priviti dintr-o perspectiva holistica, nu fac asa ceva. Sau fac, daca ar fi necesar doar un timp foarte scurt. Insa IsSorted() are nevoie de O(n) timp, oferind un singur bit de informatie. Sub aspectul asta, funtia respectiva e de evitat, nu de pus intr-o librarie.
In cazurile absolut izolate cand ar fi nevoie de asa ceva, poti scrie functia.  Acel caz izolat ar fi si unul terminal, nu ar face parte din ceva mai complex, care sub o abordare de tip holistic ar face necesara implementarea functiei la nivel de librarie.
Mai pe scurt, IsSorted() furnizeaza un tip de informatie elementara, dar elementara pentru om, nu pentru masina. Operatiile elementare din perspectiva masinii sunt cele care furnizeaza informatii pe masura timpului pe care-l consuma.

Daca chiar ar fi necesar un IsSortted(), poate ca ar trebui o structura derivata din List<> care sa mai contina un camp care sa fie updatat la fiecare introducere de date Add().
Chestie care se face de exemplu in functia Count() pe care ai atasa-o unei liste simplu inlantuita.
Ar fi utila cand numarul de apeluri IsSorted() sau Count() e suficient de mare in raport cu numarul de apeluri Add(), deoarece se muta harababura de pe IsSorted() sau Count()  pe Add() , iar chestia asta trebuie sa se justifice cumva.
In realitate, daca sa zicem ca poate folosesti Count() pe o lista simplu inlantuita, rareori folosesti IsSorted() pentru ca mutarea harababurii pe Add() sa se justifice. De fapt nici apelarea Count() pe o lista nu e o practiva buna, iar o librarie nu ar trebui sa includa asa ceva.
Poti insa deriva tu un tip, plecand de la altul din librarie care sa inglobeze functionalitatea, dar nu-i bine sa strici libraria pentru o utilizare incorecta din perspectiva holistica.

Edited by maccip, 24 May 2022 - 11:33.

Quote

Sa nu uiti sa le spui asta si alora responsabili cu stl-ul c++. A nu se uita ca algoritmul poate fi rulat si cu 'parallel policy', ceea ce deja nu mai e trivial pentru cineva care gaseste o bucla 'for' ca fiind dificila.

Un singur bit de informatie e adesea suficient ca sa realizezi ca gigel a dat inapoi contorul de apa sau ca cine stie ce valoare 'meter' s-a dat 'peste cap'.

Iar uneori acel contor nu permite cine stie ce 'cantitate posibil uriasa' de date, putand fi de exemplu pe 8 biti. Caz concret, chiar am intalnit asemenea contoare in pachete de retea IoT, iar o varianta in care se pierdea ordinea putea insemna de exemplu ca 's-a dat peste cap', sau mai rau, o incercare de https://en.wikipedia...i/Replay_attack (exista astfel de contoare si in protocoalele 'uzuale' de retea, dar acolo pierderea ordinii poate fi datorata rutarii diferite, de exemplu).

Edited by parabellum, 24 May 2022 - 13:43.

 maccip, on 24 mai 2022 - 10:48, said:

Nesemnificativ la cate elemente se iau in memorie si procesoarele de azi.
Daca lista e prea mare deja trebuie sortata pe sursa de date, in speta la db level

Edited by radu103, 24 May 2022 - 14:44.

Nesemnificativ?
Cu cat ai mai multe elemente in lista, cu atat e mai semnificativ. Iar procesorul nu poate schimba clasa de complexistate a algoritmului.

Pentru suficient de multe elemente, un algoritm bun pe un abac e mai rapid decat un calculator mainframe de ultima ora intins pe un hectar pe care ruleaza un algoritm de clasa inferioara de complexitate.


Werever, acel numar va fi foarte mare, dar ideea e ca exista.

Si cel mai important e ca programator sa te obisnuiesti sa folosesti algoritmul adecvat in ceea ce priveste viteza si complexitatea, mai ales la "taskuri  generice" care pot fi scalate foarte mult.

 parabellum, on 24 mai 2022 - 13:40, said:

Daca nu uiti sa le zici alora responsabili cu C#-ul, nu uit nici eu.
eu am argumentat "de ce nu", tu "de ce da". De aia nu-ti iese bine la parsing.

Quote

Problema e ca argumentatia ta nu prea rezista, o implementare daca chiar necesita si pozitia unde se descopera dezordinea, poate returna un iterator, de exemplu.

Quote

Cat am auzit eu povestile astea cu 'suficient de rapide', 'suficienta memorie', etc.

Pentru unele chestii chiar si memorie si viteza infinite sunt insuficiente

Edited by parabellum, 24 May 2022 - 16:07.