Witam!
Czy jest jakaś funckja w php, która umożliwi mi wybranie największej liczby np.: spośrud 5 liczb?
czy może musze robić to ręcznie i bardzo długo np.:

Z góry dzięki za pomoc

możesz dac wszystkie do tablicy i posortować dzięki czemu $tablica[0] = max
albo max" title="Zobacz w manualu PHP" target="_manual

z manuala:

[PHP] pobierz, plaintext 
<?php
$array = array(1, 2, 5, 7, 4);
echo max($array); // 7
?>
[PHP] pobierz, plaintext 

Taaa, sortowanie, przeciez to bez sensu skoro jest wlasnie max()

no to przecież podałem

a to z sortowaniem uznajmy za ciekawostkę

Ta sama złożoność obliczeniowa - O(n)

Ta sama, czy zartujesz?

Odpowiedz mi, bardzo proszę, na dwa pytania:
1. jaką złożoność ma sortowanie?
2. jaką złożoność ma max()?

@TomASS jak jestes w stanie posortowac dane jedną iteracją to ty jestes normalnie gość

Jestem w stanie posortować liczby całkowite (bo o takich tu mówię), jedną pętlą for...

no a w tej jednej petli sa kolejne.

No ale moge sie mylic, moze matematyka ruszyla do przodu przez te kilka lat wiec pokaz mi prosze ten kod

Proszę bardzo:
sortowanie kubełkowe


Albo inny pomysł:
Lecisz pętlą po całej tablicy i zapamiętujesz ile razy wystąpiła dana liczba. Potem już tylko wystarczy wyświetlić odpowiednią ilość liczb:

[PHP] pobierz, plaintext 
<?php
$arrDane = array();
$iRozmiarTablicy = 30;
/*
 * Losowanie elementów
 */
for($i=0;$i<$iRozmiarTablicy;$i++){
    $arrDane[]=rand(0,$iMaxValue);
}
/*
 * Wyświetlenie nieposortowanej tabeli
 */
echo '<pre>'; 
    print_r($arrDane);
echo '</pre>';
 
/*
 * Sortowanie tabeli
 */
for($i=0;$i<$iRozmiarTablicy;$i++){
    $arrSort[$arrDane[$i]]++;
}
/*
 * Wyświetlenie posortowanej tabeli
 */
echo '<pre>'; 
    print_r($arrSort);
echo '</pre>';
?>
[PHP] pobierz, plaintext 

Poza tym nawet w przypadku optymalnym nie jest to tylko jedna iteracja.
Wyliczenie max to jest jedna iteracja niezaleznie czy to jest przypadek optymalny czy nie

Podejrzewam, że teraz wszyscy czytający ten temat próbują rozkminić co takiego TomASS wymyślił, ale ja Wam mogę z całą pewnością oznajmić, iż nasze (a przynajmniej większości) rozumienie sortowania mija się zdecydowanie z jego własnym.

Drogi kolego shazarre.

Ja z kolei podejrzewam, że nawet nie zadałeś sobie trudu aby zrozumieć to co napisałem. Nie winię Cię jednak za to - ale nie mierz wszystkich swoją miarą.


Nie ja to wymyśliłem. Podejrzewam, że wymyślił to twórca wspaniałej książki o algorytmach - Pan Thomas (zbieżność imion?) Cormen. Algorytm "Counting Sort" jest szeroko opisywany np. tutaj (jeśli wolisz czytać po polsku, to proszę bardzo).

Kod w C++ masz tutaj. Nie widzę nigdzie zagnieżdżonych pętli. Złożoność obliczeniowa jest O(n) (dobra, niech będzie O(n+k), zmienna nie ma tutaj znaczenia). Natomiast tutaj masz aplet Javy pokazujący jak to działa.


Widać jaką miałeś pewność - swoje "widzimisie".


Tak - jakie to jest sortowanie rozumiane przez "większość"? Ja np. mogę zgodzić się z takim pojęciem:

"Sortowanie – jeden z podstawowych problemów informatyki. Polega na uporządkowaniu zbioru danych względem pewnych cech charakterystycznych każdego elementu tego zbioru. Szczególnym przypadkiem jest sortowanie względem wartości każdego elementu, np. sortowanie liczb, słów itp.

Algorytmy sortowania są stosowane w celu uporządkowania danych, umożliwieniu stosowania wydajniejszych algorytmów (np. wyszukiwania) i prezentacji danych w sposób czytelniejszy dla człowieka."

I to właśnie robię algorytmem Counting Sort, mało tego - żąda tego (pośrednio) autor wątku - posortowania i wybór ostatniego/pierwszego elementu. Chciałbym poznać Twoje (większości?) rozumienie słowa "sortowanie".

Wczytując się w niuanse tego algorytmu, znaleźć można zmienną o wartości największego elementu:

[PHP] pobierz, plaintext 
<?php
$k = max($tablica);
?>
[PHP] pobierz, plaintext 

otóż, funkcja max() (jak nospor słusznie zauważył: "Wyliczenie max to jest jedna iteracja niezaleznie czy to jest przypadek optymalny czy nie") również działa w czasie O(n) co nie wpływa w żaden sposób na jakość algorytmu (przypominam, że O(k*n) = O(n), gdzie k jest dowolną, ale skończoną wartością).

Aby jeszcze bardziej zobrazować Ci działanie tego algorytmu, pokusiłem się o napisanie go w PHP:

[PHP] pobierz, plaintext 
<?php
function countSortTomass($arrToSort){
    $arrSorted = array();
    $k = max($arrToSort);
    $length = count($arrToSort)-1;
    
    $arrTmp = array();
    for ($i=0;$i<=$k;$i++){
        $arrTmp[$i]=0;
    }
    
    for ($i=0;$i<=$length;$i++){ 
        $arrTmp[$arrToSort[$i]]++; 
        $arrSorted[]=0;
    }
    
    for ($i=1;$i<=$k;$i++){ 
        $arrTmp[$i] = $arrTmp[$i] + $arrTmp[$i-1]; 
    }
    
    for ($i=$length;$i>=0;$i--){
        $arrSorted[$arrTmp[$arrToSort[$i]]-1]=$arrToSort[$i];
         $arrTmp[$arrToSort[$i]]--; 
    }
    return $arrSorted;
}
 
$arrayToSorting = array(1,7,6,10,7,1,5,7,10,3);
$sorted = countSortTomass($arrayToSorting);
echo '<pre>';
    print_r($sorted);
echo '</pre>';
?>
[PHP] pobierz, plaintext 

Nie ma żadnych pętli zagnieżdżonych. Złożoność obliczeniowa to O(n) (dla formalistów O(n+k)).

Kluczowym momentem jest zliczanie elementów:

[PHP] pobierz, plaintext 
<?php
for ($i=0;$i<=$length;$i++){ 
        $arrTmp[$arrToSort[$i]]++; 
}
?>
[PHP] pobierz, plaintext 

o którym pisałem wcześniej, lecz kolega shazarre nie raczył tego zagłębić.

odpalając

[PHP] pobierz, plaintext 
<?php
$arrayToSorting = array(12,3456,6,9887,0);
$sorted = countSortTomass($arrayToSorting);
echo '<pre>';
    print_r($sorted);
echo '</pre>';
?>
[PHP] pobierz, plaintext 

Także uzyskamy prawidłowy wynik (jak chciał autor postu) w czasie porównywalnym (przy nieskończonej ilości danych w takim samym czasie) co max() czyli O(n)

No ale generalnie dyskusja zaczęła się od tego żeby udowodnić że sortowanie da się zrobić JEDNĄ iteracją.

Jak widać nie jesteś w stanie
Poza tym sortowanie przez zliczanie to nie jest szczyt szczytów jeśli chodzi o przydatność algorytmu bo niestety jak każdy z algorytmów sortowania ten też ma swoje wady. Faktycznie wydajny jest, ale tylko w określonych sytuacjach.

Po pierwsze:

Sytuacja zaczęła się od tego, że twierdziłem, że sortowanie liczb całkowitych ma taką samą złożoność obliczeniową jak max() - co jak widać udowodniłem i nie żartowałem

Po drugie:

Umiem jedną iteracją.
Sortowanie właściwe to jedna pętla - bez żadnych zgłębień kolejnych pętli - jest to robione tak jak max w JEDNEJ itereacji. Reszta forów jest tylko do "znośnej" prezentacji wyników. Po za tym, okej, nawet jakby było 100 forów pod sobą to i tak złożoność obliczeniowa byłaby O(100n) czyli O(n). Ale faktycznie, zwrot że "tylko" jedną mogę posortować nie był przeze mnie idealnie trafiony.

Po trzecie:

Dla liczb całkowitych ma najlepszą złożoność obliczeniową i jest szczytem szyczytów - znasz algorytm sortowania o lepszej złożoności (nawet z tymi wadami - o których wspomniałem)?

Po czwarte:

To zaznaczyłem na samym początku, że chodzi o liczby całkowite, dodatkowo zmienia klucze i jest niestabilny - ale w tym przykładzie nie przeszkadza to niczemu.


Po piąte:
Dzięki za odpowiedzieć - jak widać shazarre podczas gdy nie mógł "rozkminić" stwierdził, że nikt z Was nie doczyta tego, ani nie zrozumie (albo zrozumie na opak) - na szczęście się mylił, co krowal udowodnił

@TomASS:
No wlasnie nie na poczatku...


-> wprowadzasz zamieszanie - nie informujesz ze myslales o sortowaniu tylko liczb calkowitych



1. a ktory algorytm?
zalezy od algorytmu i mozliwosci jego zastosowania od O(n), O(nlog(n)), O(n^2) i w gore
2. O(n), ale i tak bedzie w praktyce szybsze niz jakiekolwiek sortowanie, i mniej pamieci zuzyje niz kubelkowe

Takze, twoje wypowiedzi byly niejasne, niepelne i sie czepiasz ze my sie ich czepiamy.


edit: pozatym Counting Sort:
- LOL, rzeczywiscie przydatny algorytm do tego konkretnego problemu.

Jasno napisałem już w pierwszym/drugim poście:



Zazwyczaj pyta się o minimalną złożoność - nie o maksymalną.

TomASS (pierwszy post): Ta sama złożoność obliczeniowa - O(n)
dr_bonzo: Ta sama, czy zartujesz?

TomASS:
1. jaką złożoność ma sortowanie?
2. jaką złożoność ma max()?

Dalej twierdzę, że dla liczb całkowitych mają takie same złożoności.





nawet O(n^n) albo nawet O(!n^!n) i co z tego? Minimalna dla liczb całkowitych to taka sama jak dla max().


Nie mówię o praktyce tylko o złożoności.


Bo nie doczytałeś. Mam całą teorię wyłożyć?

Książkę musiałbym napisać. Dałem linki, powiedziałem jak metody się nazywają - czego chcieć więcej? Później jak krowie na rowie musiałem dać przykłady w różnych językach, aplety itd. aby niektórzy zrozumieli.


Czepiam się, jak ktoś nie doczyta/nie zrozumie i się czepia


I co z tego, jaki to ma wpływ na złożoność - żaden - nadal jest O(n) i jest robione sortowanie w jednej iteracji.



Okej - niech będzie tak jak pisałem O(4n+O(max())+k).

@TomASS w funkcji countSortTomass() korzystasz z max():
$k = max($arrToSort);

no, i tyle w temacie z mojej strony

Napisales mi ze jestes w stanie posortowac jedną iteracją a nie jestes. na dodatek by posortowac uzywasz funkcji, co do której pisales ze jestes w stanie zrobic tak samo szybko jak ona

Podsumowując temat:
do wyliczenia wartosci maksymalnej uzywa sie algorytmu do wyliczenia wartosci maksymalnej a nie sortowania

Się pytam - i co z tego? Tak zgadza się, coś co używa max() musi być wolniejsze niż samo max() - to oczywiste, ale może mieć tą samą złożoność obliczeniową.


i w kategorii ciekawostki to traktuję

oczywiście, że do wartości maksymalnej służy funkcja max(), nigdzie nie twierdziłem inaczej.


Nie pisałem, że tak samo szybko, tylko mają taką samą złożoność (jest różnica pomiędzy szybkością a złożonością)


Jedną iteracją miałem na myśli, bez pętli zagnieżdżonych, Ty zresztą też:

i nie ma pętli w pętli. A jesteś pewien, że w max() nie ma kilku pętli pod sobą (dla różnych argumentów)?

podsumowując:

a do tego (cytat z mojego pierwszego postu) sortowanie liczb całkowitych i max() to:

posortować jedną pętlą raczej się nie da , ale wybrać największą wartość bez problemu , a o tym temat

masz rację: główny temat tak
ja jednak zapoczątkowałem dyskusję na temat:


Komentarz przy max():


czyli coś w tym jest. Nie koniecznie musi być tylko jedna pętla.

tak, zaczales, ale skonczyles tekstem do mnie:



No ale skonczmy juz, bo odchodzimy od tematu

TomASS - pokazałem właśnie w pracy Twoje posty w tym wątku profesorowi co wykłada algorytmy. Jeszcze nigdy nie widziałem by tak głośno się śmiał. W tym co tutaj napisałeś popełniłeś tyle błędów, że rzadko, który student potrafi tak namotać w pojedynczym zadaniu

Bez obrazy - po prostu chciałeś coś udowodnić i Ci się nie udało (sam też często tak mam - ale przynajmniej wtedy można się pośmiać )

Pozdrawiam,
Łukasz

Ta - już biegłeś do profesora - bez urazy - pewnie na Uniwerku? Zapytaj się jego czy czytał Cormen'a - bo to jest właśnie algorytm z jego książki (sam sobie go nie wymyśliłem) i wyraźnie jest napisane O(n).

Dowiedziałem się o tym algorytmie podczas dyskusji z doktorem na laboratorium (wybacz, że nie z profesorem na wykładzie), na temat:

ktoś rzucił, że należy stosować standardowe funkcje STL z algorithm, a nie wymyślać własne, bo one są do tego stworzone, długo nad tym ludzie myśleli i na pewno są najlepsze jakie wymyślono. Zrobiliśmy eksperyment i znaleźliśmy czysty kod funkcji sort(), okazało się, że są dwie zagnieżdżone pętle - złożoność O(n^2). W Cormenie natomiast doczytaliśmy, że sortowanie liczb całkowitych da się w O(n) - napisaliśmy funkcję, policzyliśmy złożoność i okazało się, że tak - O(n) i rzeczywiście nie należy wszędzie, bezmyślnie, stosować gotowych funkcji bo nie zawsze są optymalne dla danego zadania.



Na zdrowie - niczego to nie dowodzi.
Masz jakiś przykład czy puste słowa?


umiesz odpowiedzieć - co chciałem udowodnić?

@nospor:
skoczył to shazarre, mierząc Was jego miarą.

Trzecim... wystarczy policzyc


Zgadza sie, ale nie napisales jeszcze ze myslisz o sortowaniu TYLKO liczb calkowitych.




A ja przeciez nie zaprzeczam, ze kubelkowe ma O(n).





No i jedna iteracja to jedna petla for - w kubelkowym masz ich wiecej niz jedna,
chociaz to nadal ma zlozonosc O(n)





AFAIK to k musi byc stałą, np. algorytm wykonuje zawsze 10 petli for == O( 10 * n ) == O(n)
ale masz zlozonosc/algorytmu pseudowielomianowe gdzie niby tez masz O(B*n) ale B jest np. najwieksza
liczba w zbiorze na ktorym operujesz.
Bo n tez jest skonczona wartoscia, a O( n * n ) to O (n^2) a nie O(n), nie?



Chodzilo mi tylko o to ze problem glowny z topiku jest rozwiazywany przez pierwszy krok tego algorytmu sortowania.
A ze zlozonosc ma nadal O(n) to nie przecze.


@nospor

Ta sama zlozonosc algorytmu to nie to samo co "zrobic tak samo szybko jak ona"
W tej teorii 100 petli for (po wszystkich elementach ktore sortujemy) ma taka sama zlozonosc co jedna - a przeciez wiadomo ze jedna sie wykona szybciej od 100 (powiedzmy puste przebiegi - zeby nie bylo niedomowien)

hihi, ale ja nie czepiam sie zlozonosci, ale tego jego tekstu:

@dr_bonzo
Widzisz jak się rozumiemy
Zgadzam się z Tobą - dzięki za poświęcenie czasu.

Masz rację jest to pseudowielomianowa złożoność - formalisto

P.S.
Z tym nieodpowiadaniem na moje dwa pierwsze pytania to był niezły wybieg

@nospor:
tak jak pisałem - niefortunnie użyłem tutaj zwrotu "jedną pętlą"


konkluzja taka, że nie wszystkie funkcje stworzone przez autorów bibliotek działają najszybciej jak to możliwe.

Czyli może warto napisać samodzielnie funkcję max pod konkretny problem? Może w funkcji max są nadmiarowe elementy dla szczególnych przypadków?

TomASS - nie biegłem a sam przyszedł do pokoju w którym pracuję.



No właśnie - wiesz, że gdzieś dzwonią (bo powiedział Ci o tym prowadzący laboratorium) ale nie wiesz gdzie.



Chyba sam nie wiesz co chciałeś udowodnić

W zasadzie - może i miałbyś rację. Ale rację trzeba umieć też przedstawić i obronić. Tobie się to nie udało, czytając Twoje kolejne posty coraz bardziej zmieniałeś zdanie itp. I właśnie z tego śmiał się profesor.

Bo to, że zawsze są rozwiązania dotyczące konkretnego problemu, które są lepsze od rozwiązań ogólnie stosowanych wie każde dziecko

Z tego co ja tutaj widzę - nie obroniłeś swojej tezy.

Pozdrawiam,
Łukasz

--- edit ---



To jest oczywista oczywistość, że coś pisane pod konkretny problem jeśli jest dobrze napisane, będzie o wiele lepsze od rozwiązań ogólnych. I co do tego to się z Tobą w zupełności zgadzam.

TomASS:
Formalizm, nieformalizm - mi chodzi o precyzje wypowiedzi - myslisz o jednym (sortowaniu liczb calkowitym), mowisz o drugim (ogolnie o sortowaniu) i sie dziwisz ze zle cie rozumiemy (twoje mysli). Wmawiasz nam jeszcze ze od *poczatku* mowiles o sortowaniu liczb calkowitych - tylko zauwaz kiedy zaczalem sie twoich wypowiedzi czepiac, przed pierwszym slowem "calkowite".
edit: Chodzilo mi tez tutaj o precyzje okreslenia wartosci k w O (n * k ) - bo to zmienia postac rzeczy....




Te czy jakie?

=======
edit2:

Bo maja byc najlepsze dla przecietnych problemow. Chyba do sorta nie wlozysz
if ( tablica_za_wiera_tylko_integery_z_dosyc_malego_przedzialu )
{
uzyj_kubelkowatego($tablica)
}
else
{
qsort()
}

zazwyczaj qsort wszystkim wystarcza, jak musisz miec super wydajnosc sortowania intow to sobie to zoptymalizujesz,
wezmiesz np. sortowanie kubelkowe


Precyzja precyzja precyzja wypowiedzi, w matematyce/algorytmach TRZEBA sie precyzyjnie wypowiadac, inaczej zmieniasz sens

Aby zakończyć temat napiszę funkcję do znajdywania max liczby z tablicy, i uwaga... zrobię to JEDNĄ iteracją

[PHP] pobierz, plaintext 
<?php
$max = null;
foreach($array as $value){
  $max = ($value > $max) ? $value : $max;
}
?>
[PHP] pobierz, plaintext 

Krowal to co napisałeś jest oczywiste, ale
rozmowa się toczyła na temat sortowania .

krowal: a co jak mam liczby array( -1, -100, -10, -5 ) ?

Kurde bonzo, zasiałeś ziarno niepewności i musiałem sprawdzić, oczywiście otrzymasz -1 ze swojego zbioru

Edit:
@Spawnm, tak wiem, że o sortowaniu, nawet coś tam napisałem wcześniej, ale ta dyskusja teraz polega na cytowaniu każdego zdania przedmówcy i odbijaniu piłeczki, imo to już nie dyskusja

krowal: chodzilo mi o to ze
-2 > null da ci false, i na koniec $max bedzie NULLem.

Ale, wtf, bo wlasnie to zwraca TRUE, przez co skrypt zadziala prawidlowo, a przyjalem ze NULL zostanie skonwertowany do 0.
A dodatkowo obslgua nulla nie jest konsekwentna jak w SQLu, gdzie kazde porownanie z NULLem daje false.

[PHP] pobierz, plaintext 
<?php
var_dump( -1 < null );
var_dump( -1 > null );
var_dump( -1 + null );
?>
[PHP] pobierz, plaintext 

daje


kocham php...

sorki za zamieszanie

Nooo.. żeby inne języki się nie gniewały to można zrobić tak:

[PHP] pobierz, plaintext 
<?php
foreach($array as $value){
  $max = isset($max) ? ($value > $max) ? $value : $max : $value;
}
?>
[PHP] pobierz, plaintext 

Dla ścisłości: nie zrobisz tego jedną iteracją tylko jedną pętlą. W skrócie można stwierdzić, że iteracja to pojedynczy "przebieg" pętli, a twój kod będzie wykonywał tyle iteracji ile jest elementów w tablicy.

I pozamiatane Faktycznie racja, w szale pisania postów zapomniało się o znaczeniu słów.