|
|
| Строка 14: |
Строка 14: |
| | == Раскрытие вопроса == | | == Раскрытие вопроса == |
| | | | |
| − | <p>Cортировка массивов — одно из наиболее важных действий над массивами в системах сбора и поиска информации, т. к. в отсортированных массивах найти нужную информацию можно гораздо быстрее по сравнению с несортированными.
| + | <table border="1"> |
| − | Cуществует множество различных алгоритмов сортировки, которые значительно отличаются друг от друга по скорости работы.</p>
| + | [[Изображение:2u43s.gif]] |
| − | | + | |
| − | <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> | | <tr> |
| − | <td>N</td>
| + | <td>N</td> |
| | <td>Обменная сортировка</td> | | <td>Обменная сортировка</td> |
| | <td>Сортировка выбором</td> | | <td>Сортировка выбором</td> |
| Строка 75: |
Строка 64: |
| | </tr> | | </tr> |
| | | | |
| − | </table> | + | </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]] | | [[Категория: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>
| |
