Сортиране чрез пряка селекция: Разлика между версии
Изтрито е съдържание Добавено е съдържание
м Робот Добавяне {{без източници}} |
Ted Masters (беседа | приноси) м Грешки в статичния код: Липсващ затварящ таг; форматиране: 3 интервала (ползвайки Advisor) |
||
Ред 11:
== Пример стъпка по стъпка ==
Нека имаме масив със следните елементи: 64,25,12,22,11 и искаме да го сортираме във възходящ ред като използваме метода на пряката селекция. На всяка стъпка елементите, които са удебелени биват разменяни.
<br />Първо преминаване:<br />'''64''' '''25''' 12 22 11 <math>\to</math> '''25''' '''64''' 12 22 11 <br />'''25''' 64 '''12''' 22 11 <math>\to</math> '''12''' 64 '''25''' 22 11 <br />12 64 25 22 11 <math>\to</math> 12 64 25 22 11 <br />'''12''' 64 25 22 '''11''' <math>\to</math> '''11''' 64 25 22 '''12''' <br />След първото преминаване най-малкият елемент на масива се намира на първа позиция.
Ред 20:
== Анализ ==
Методът на пряката селекция не е труден да се анализира в сравнение с други сортиращи алгоритми. За да намерим най-малкият елемент се изисква да сканираме всички n на брой елементи (това отнема ''n'' – 1 сравнения) и след това да го разменим с първата позиция. За да намерим следващият най-малък елемент се изисква да сканираме оставащите ''n'' – 1 елементи и така нататък. Общият брой сравнения е равен на
(''n'' − 1) + (''n'' − 2) + ... + 2 + 1 = ''n''(''n'' − 1) / 2 = Θ(''n''<sup>2</sup>)
според формулата за сбор на аритметична прогресия. Всяко от тези
== Сравнение с други алгоритми за сортиране ==
Ред 106:
== Пример на C++ за сортиране на числа по метода на прекия избор ==
using namespace std;
Ред 129:
}</pre>
[[Категория:Алгоритми]]
| |||