ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ СРЕДНЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯРабота на тему: «методы сортировки массивов»
Работу сдали: студенты группы 9ПО-31 Денисов В.С.
Санкт-Петербург 2013г.
Задача: Отсортировать массив целых чисел методом «Пузырек» и «Вставка». Подсчитать трудоемкость методов. Алгоритм программы: Пузырек
Вставка
Код программы: <?php $const=10; echo'<table border="1" align="center"> <tr> <td>Исходный массив</td> <td>'; for($i=0;$i<$const;$i++) { $x[$i]=rand(-10,10); $y[$i]=$x[$i]; echo $x[$i].' '; } echo '</td> <td>время</td> <td>итерации</td> <td>трудоемкость (T/itertion)</td> </tr><tr> <td>метод вставки</td> <td>'; $starttime=microtime(); for($j=0;$j<$const-1;$j++) for($i=0;$i<$const-1;$i++) if($x[$i]>$x[$i+1]) { $x[$i]=$x[$i]+$x[$i+1]; $x[$i+1]=$x[$i]-$x[$i+1]; $x[$i]=$x[$i]-$x[$i+1]; } $endtime=microtime(); $iter=$i+$j; for($i=0;$i<$const;$i++) echo $x[$i].' '; echo '</td><td>'; $time=$endtime-$starttime; printf("%.6f<br>",$time); echo '</td> <td>'.$iter.'</td> <td>'; printf("%.6f",$time/$iter); echo '</td> </tr><tr> <td>метод вставки</td> <td>'; $starttime2=microtime(); for($i=0;$i<$const;$i++) { $x=$y[$i]; for($j=$i-1;$j>=0 && $y[$j]>$x;$j--) $y[$j+1]=$y[$j]; $y[$j+1]=$x; } $endtime2=microtime(); $iter=$i+$j; for($i=0;$i<$const;$i++) echo $y[$i].' '; echo '</td> <td>'; $time2=$endtime2-$starttime2; printf("<br>%.6f",$time2); echo '</td> <td>'.$iter.'</td> <td>'; printf("%.6f",$time2/$iter); echo '</td> </tr> </table>';?> Протокол работы программы: Array=10
Array=100
|
