Ocena użytkownikóww: ***** / 17
Nadesłany przez _marass_, 10 kwietnia 2011 14:41
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.bubble_1_php.php:
<?php
//Szukalski Marek
//www.algorytm.org
//sortowanie babelkowe
$tabela=array('12','123','1','5','756','234','43','24');
//pamietajmy, że indeks w tabeli rozpoczyna sie od 0
//a konczy na n-1
$n=8; //ilosc elementow w tabeli
for($i=$n;$i>=0;$i--){//petla glowna
for($j=0;$j<$i-1;$j++){//petla wewnetrzna
if($tabela[$j]>$tabela[$j+1]){ //warunek
$tmp=$tabela[$j]; //zamiana
$tabela[$j]=$tabela[$j+1];
$tabela[$j+1]=$tmp;
}
}
}
for($i=0;$i<$n;$i++) echo($tabela[$i].' '); //wypisanie posortowanych wartosci tabeli
?>
Wtedy nie potrzeba 2 for-ów.
Bez niej, jak rozumiem z tekstu artykułu, złożoność będzie stała, O(n^2)?
Czyli nie osiągniemy O(n) dla wejścia już posortowanego?