Сортиране чрез пряка селекция: Разлика между версии
Изтрито е съдържание Добавено е съдържание
Ред 10:
== Пример стъпка по стъпка ==
Нека имаме масив със следните елементи: 64,25,12,22,11 и искаме да го сортираме във възходящ ред като използваме метода на пряката селекция. На всяка стъпка елементите, които са удебелени биват разменяни.
Първо преминаване <br />▼
<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 />След първото преминаване най-малкият елемент на масива се намира на първа позиция.
11 '''64''' '''25''' 22 12 <math>\to</math> 11 '''25''' '''64''' 22 12 <br />11 '''25''' 64 '''22''' 12 <math>\to</math> 11 '''22''' 64 '''25''' 12 <br />11 '''22''' 64 25 '''12''' <math>\to</math> 11 '''12''' 64 25 '''22''' <br />Трето преминаване:<br />11 12 '''64''' '''25''' 22 <math>\to</math> 11 12 '''25''' '''64''' 22 <br />11 12 '''25''' 64 '''22''' <math>\to</math> 11 12 '''22''' 64 '''25''' <br />Четвърто преминаване:<br />11 12 22 '''64''' '''25''' <math>\to</math> 11 12 22 '''25''' '''64''' <br />
== Анализ ==
Методът на пряката селекция не е труден да се анализира в сравнение с други сортиращи алгоритми. За да намерим най-малкият елемент се изисква да сканираме всички n на брой елементи (това отнема ''n'' – 1 сравнения) и след това да го разменим с първата позиция. За да намерим следващият най-малък елемент се изисква да сканираме оставащите ''n'' – 1 елементи и така нататък
(''n'' − 1) + (''n'' − 2) + ... + 2 + 1 = ''n''(''n'' − 1) / 2 = Θ(''n''<sup>2</sup>)
според формулата за сбор на аритметична прогресия. Всяко от тези ''n'' – 1 преминавания по масива изисква една размяна на елементи (последният елемент е вече на правилното място).
== Сравнение с други алгоритми за сортиране ==
Методът на прекия избор почти винаги е по-бърз от метода на мехурчето и метода на гнома. Сортирането чрез вмъкване и чрез пряка селекция си приличат по това, че след ''k''-тата итерация първите k елемента на масива са подредени във възходящ ред. Предимството на метода на вмъкването е, че проверява толкова елемента, колкото му е нужно, за да сложи (''k'' + 1)-ия елемент на мястото му, докато методът на пряката селекция трябва да провери всички останали елементи, за да намери (''k'' + 1)-ия елемент.
Сортирането чрез вмъкване прави средно два пъти по-малко сравнения от метода на прекия избор. Недостатък на последния метод е, че работи едно и също време независимо от подредбата на входния масив, дори когато той е предварително сортиран. Сортирането чрез вмъкване е по-адаптивно: то работи бързо, когато масивът е сортиран или почти сортиран.
Върху големи масиви методът на пряката селекция е доста по-бавен от сортирането чрез сливане и други бързи сортировки. Обаче сортирането чрез пряк избор и чрез вмъкване са по-бързи, когато работят върху малки масиви (до десет-двайсет елемента). Затова тези два метода се използват като дъно на някои рекурсивни сортировки, например бързото сортиране (quick sort).
== Варианти ==
Двупосочен вариант на метода на пряката селекция, наричан още
Сортирането чрез пряк избор е устойчива сортировка: при внимателно реализиране то не разменя елементи с равни ключове.
== Пример ==
Line 71 ⟶ 48:
| bgcolor="lightblue" |31||34||12||22|| bgcolor="pink" |11
|}
|| Най-малкият елемент е 11. Разменят се
|-
|
Line 77 ⟶ 54:
| |11|| bgcolor="lightblue" |34|| bgcolor="pink" |12||22||31
|}
|| Най-малкият оставащ елемент
|-
|
Line 83 ⟶ 60:
| |11||12|| bgcolor="lightblue" |34|| bgcolor="pink" |22||31
|}
|| Вече имаме една част от списъка, която е сортирана.
|-
|
Line 89 ⟶ 66:
| |11||12||22|| bgcolor="lightblue" |34|| bgcolor="pink" |31
|}
|| Разменят се
|-
|
Line 98 ⟶ 75:
|}
== Пример на C# за сортиране на
<pre>
using System;
Line 127 ⟶ 104:
</pre>
== Пример на C++ за сортиране на
<code><pre>#include <iostream>
using namespace std;
Line 151 ⟶ 128:
}</pre>
[[Категория:Алгоритми]]
| |||