https://wiki.atp-fivt.org/index.php?action=history&feed=atom&title=Quicksort 2026-10-16T14:55:38Z История изменений этой страницы в вики MediaWiki 1.43.3 https://wiki.atp-fivt.org/index.php?title=Quicksort&diff=390&oldid=prev 2020-05-07T14:58:12Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="ru"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Предыдущая версия</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Версия от 14:58, 7 мая 2020</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1">Строка 1:</td> <td colspan="2" class="diff-lineno">Строка 1:</td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Быстрая сортировка</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>(std sort)</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">== </ins>Быстрая сортировка(std sort) <ins style="font-weight: bold; text-decoration: none;">==</ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> </table>

Algocourselecturenotes https://wiki.atp-fivt.org/index.php?title=Quicksort&diff=389&oldid=prev 2020-05-07T14:49:34Z

<p>Новая страница: «Быстрая сортировка (std sort) p p p p (pivot) &lt;p&lt;p&lt;p&lt;p p &gt;p&gt;p&gt;p…»</p> <p><b>Новая страница</b></p><div>Быстрая сортировка<br /> (std sort)<br /> <br /> <br /> p<br /> <br /> p<br /> p<br /> <br /> p (pivot)<br /> &lt;p&lt;p&lt;p&lt;p p &gt;p&gt;p&gt;p<br /> <br /> <br /> <br /> Пусть выбран p. Как построить разбиение?<br /> Метод 1. (С доп. памятью)<br /> - исх. массив а<br /> C - результат<br /> i<br /> p<br /> <br /> <br /> <br /> а) for (i = 1…n)<br /> Стабильная.<br /> if (a &lt; i) &lt; p)<br /> c.push_back(a(i))<br /> б) for (i = 1…n)<br /> ai = p<br /> в) for (i = 1…n)<br /> ai &gt; p<br /> pppp<br /> <br /> r<br /> r<br /> l<br /> l<br /> c <br /> <br /> <br /> for (I = 1…n)<br /> Не стабильная.<br /> if (a(i) &lt; p): c (l) = a (i), ++ l<br /> if (a(i) &gt; p): c (r) = a (i), -- r<br /> <br /> Метод 2.<br /> i = 1, i = n<br /> while (i &lt; j): <br /> while (i &lt; j &amp;&amp; a(i) p) ++i;<br /> while (i &lt; j &amp;&amp; a(j) p) -- j;<br /> if (i &lt; j) <br /> swap (a(i), a(j)), ++i, -- j;<br /> swap (a(micl), a(j));<br /> нач. позиция p (в исх. массиве)<br /> i и j находят разделение p и p<br /> <br /> 1) Произвольный детерм. выбор ( mid = 1 / micl = n / …)<br /> В худшем случае может работать <br /> <br /> 2) Выбор случайного p.<br /> Теорема (б/д). В среднем quick sort со случайным выбором p работает за</div>

Algocourselecturenotes