Hagok: /* Авторы и участники проекта */

2011-12-13T14:38:10Z

Авторы и участники проекта

Hagok: Новая: == Название проекта == Упорядочивание информации в одномерных массивах == Авторы и участники проекта...

2011-12-13T14:37:51Z

Новая: == Название проекта == Упорядочивание информации в одномерных массивах == Авторы и участники проекта...

Новая страница

== Название проекта ==

Упорядочивание информации в одномерных массивах

== Авторы и участники проекта ==

Семенов Алексей

== Тема исследования группы ==

Скорость сортировки данных

== Проблемный вопрос (вопрос для исследования) ==

Для чего существуют различные алгоритмы сортировки информации?

== Раскрытие вопроса ==

<p>Cортировка массивов — одно из наиболее важных действий над массивами в системах сбора и поиска информации, т. к. в отсортированных массивах найти нужную информацию можно гораздо быстрее по сравнению с несортированными.
Cуществует множество различных алгоритмов сортировки, которые значительно отличаются друг от друга по скорости работы.</p>

<p>"Быстрые" способы сортировки массивов могут дать колоссальный выигрыш на больших массивах, содержащих тысячи элементов, однако для небольших массивов можно использовать самые простые способы сортировки.</p>

<p>Сравним алгоритмы сортировок, испытав их на массивах, содержащих 4000, 8000, 10000, 15000 и 20000 целых чисел, соответственно. Время выполнения измерено в тиках (1/60 доля секунды). Среди всех алгоритмов порядка O(n2) время сортировки вставками отражает тот факт, что на i-ом проходе требуется лишь i/2 сравнений. Этот алгоритм явно превосходит все прочие сортировки порядка O(n2). Заметьте, что самую худшую общую производительность демонстрирует сортировка методом пузырька. Результаты испытаний показаны в таблице 1.</p>

<p>Для иллюстрации эффективности алгоритмов сортировки в экстремальных случаях используются массивы из 20000 элементов, отсортированных по возрастанию и по убыванию. При сортировке методом пузырька и сортировке вставками выполняется только один проход массива, упорядоченного по возрастанию, в то время как сортировка посредством выбора зависит только от размера списка и производит 19999 проходов. Упорядоченность данных по убыванию является наихудшим случаем для пузырьковой, обменной и сортировки вставками, зато сортировка выбором выполняется, как обычно.</p>

<p>Таблица 1</p>

<table border="1">

<tr>
<td>N</td>
<td>Обменная сортировка</td>
<td>Сортировка выбором</td>
<td>Пузырьковая сортировка</td>
<td>Сортировка вставками</td>
</tr>

<tr>
<td>4 000</td>
<td>12.23</td>
<td>17.30</td>
<td>15.78</td>
<td>5.67</td>
</tr>

<tr>
<td>8 000</td>
<td>49.95</td>
<td>29.43</td>
<td>64.03</td>
<td>23.15</td>
</tr>

<tr>
<td>10 000</td>
<td>77.47</td>
<td>46.02</td>
<td>99.10</td>
<td>35.43</td>
</tr>

<tr>
<td>15 000</td>
<td>173.97</td>
<td>103.00</td>
<td>223.28</td>
<td>80.23</td>
</tr>

<tr>
<td>20 000</td>
<td>313.33</td>
<td>185.05</td>
<td>399.47</td>
<td>143.67</td>
</tr>

</table>

<br>

<table border="1">

<tr>
<td>N</td>
<td>Обменная сортировка</td>
<td>Сортировка выбором</td>
<td>Пузырьковая сортировка</td>
<td>Сортировка вставками</td>
</tr>

<tr>
<td>8 000 (упорядочен по возраст.)</td>
<td>185.27</td>
<td>185.78</td>
<td>0.03</td>
<td>0.05</td>
</tr>

<tr>
<td>8 000 (упорядочен по убыв.)</td>
<td>526.17</td>
<td>199.00</td>
<td>584.67</td>
<td>286.92</td>
</tr>

</table>

<p>В общем случае “Быстрая сортировка” является самым быстрым алгоритмом. Благодаря своей эффективности, равной O(n log2n), он явно превосходит любой алгоритм порядка O(n2). Судя по результатам испытаний, приведенных в следующей таблице, он также быстрее любой из сортировок порядка O(n log2n), рассмотренных нами в прошлом номере. Обратите внимание, что эффективность «быстрой» сортировки составляет O(n log2n) даже в экстремальных случаях. Зато сортировка посредством поискового дерева становится в этих случаях O(n2) сложной, так как формируемое дерево является вырожденным.</p>

<table border="1">

<tr>
<td width = "60">N</td>
<td>Турнирная сортировка</td>
<td>Сортировка посредством дерева </td>
<td>Пирамидальная сортировка</td>
<td>"Быстрая" сортировка</td>
</tr>

<tr>
<td>4 000</td>
<td>0.28</td>
<td>0.32</td>
<td>0.13</td>
<td>0.07</td>
</tr>

<tr>
<td>8 000</td>
<td>0.63</td>
<td>0.68</td>
<td>0.28</td>
<td>0.17</td>
</tr>

[[Категория:ТГУ]]
[[Категория:TEO2]]

<tr>
<td>10 000</td>
<td>0.90</td>
<td>0.92</td>
<td>0.35</td>
<td>0.22</td>
</tr>

<tr>
<td>15 000</td>
<td>1.30</td>
<td>1.40</td>
<td>0.58</td>
<td>0.33</td>
</tr>

<tr>
<td>20 000</td>
<td>1.95</td>
<td>1.88</td>
<td>0.77</td>
<td>0.47</td>
</tr>

</table>

<br>

<table border="1">

<tr>
<td>8 000 (упорядочен по возрастанию)</td>
<td>1.77</td>
<td>262.27</td>
<td>0.75</td>
<td>0.23</td>
</tr>

<tr>
<td>8 000 (упорядочен по убыванию)</td>
<td>1.65</td>
<td>275.70</td>
<td>0.80</td>
<td>0.28</td>
</tr>

</table>

<p>Из всего выше сказанного, можно сделать вывод, что для каждой ситуации, должна применяться наиболее эффективная сортировка, так как это дает выигрыш в скорости, особенно при использовании в больших массивах информации.</p>

@@ Строка 1: / Строка 1: @@
 == Название проекта ==
@@ Строка 7: / Строка 5: @@
 == Авторы и участники проекта ==
- Семенов Алексей
+Артур Акопджанян
 == Тема исследования группы ==

Вики-страница ученика - История изменений

Hagok: /* Авторы и участники проекта */

Hagok: Новая: == Название проекта == Упорядочивание информации в одномерных массивах == Авторы и участники проекта...