ИЗБОР СОРТИРАНЕ

В тази статия ще обсъдим алгоритъма за сортиране на селекция. Работната процедура за сортиране на селекция също е проста. Тази статия ще бъде много полезна и интересна за студентите, тъй като може да се сблъскат с подбор като въпрос на своите изпити. Така че е важно да обсъдим темата.

При сортиране при избор най-малката стойност сред несортираните елементи на масива се избира при всяко преминаване и се вмъква на подходящата позиция в масива. Това е и най-простият алгоритъм. Това е алгоритъм за сортиране на сравнение на място. В този алгоритъм масивът е разделен на две части, първата е сортираната част, а другата е несортираната част. Първоначално сортираната част от масива е празна, а несортираната част е дадения масив. Сортираната част се поставя отляво, докато несортираната част се поставя отдясно.

При сортиране по избор първият най-малък елемент се избира от несортирания масив и се поставя на първа позиция. След това се избира вторият най-малък елемент и се поставя на втора позиция. Процесът продължава, докато масивът бъде изцяло сортиран.

Средната и най-лошата сложност на сортирането на селекцията е На²) , където н е броят на елементите. Поради това не е подходящ за големи набори от данни.

Сортирането при избор обикновено се използва, когато -

Трябва да се сортира малък масив
Разходите за размяна нямат значение
Задължителна е проверката на всички елементи

Сега нека видим алгоритъма за сортиране на селекцията.

Алгоритъм

 SELECTION SORT(arr, n) Step 1: Repeat Steps 2 and 3 for i = 0 to n-1 Step 2: CALL SMALLEST(arr, i, n, pos) Step 3: SWAP arr[i] with arr[pos] [END OF LOOP] Step 4: EXIT SMALLEST (arr, i, n, pos) Step 1: [INITIALIZE] SET SMALL = arr[i] Step 2: [INITIALIZE] SET pos = i Step 3: Repeat for j = i+1 to n if (SMALL &gt; arr[j]) SET SMALL = arr[j] SET pos = j [END OF if] [END OF LOOP] Step 4: RETURN pos

Работа на алгоритъма за сортиране на селекция

Сега нека видим работата на алгоритъма за сортиране на селекция.

За да разберем работата на алгоритъма за сортиране на селекция, нека вземем несортиран масив. Ще бъде по-лесно да разберете сортирането на селекция чрез пример.

Нека елементите на масива са -

Сега, за първата позиция в сортирания масив, целият масив трябва да бъде сканиран последователно.

В момента, 12 се съхранява на първа позиция, след търсене в целия масив се установява, че 8 е най-малката стойност.

10 мл е колко

И така, разменете 12 с 8. След първата итерация 8 ще се появи на първата позиция в сортирания масив.

За втората позиция, където 29 се съхранява в момента, ние отново последователно сканираме останалите елементи от несортирания масив. След сканиране откриваме, че 12 е вторият най-нисък елемент в масива, който трябва да се появи на втора позиция.

Сега разменете 29 с 12. След втората итерация 12 ще се появи на втората позиция в сортирания масив. И така, след две итерации, двете най-малки стойности се поставят в началото по сортиран начин.

Същият процес се прилага към останалите елементи на масива. Сега показваме картинно представяне на целия процес на сортиране.

Сега масивът е напълно сортиран.

Сложност на сортиране на селекцията

Сега нека видим времевата сложност на сортирането на селекцията в най-добрия случай, средния случай и в най-лошия случай. Ще видим и пространствената сложност на сортирането на селекцията.

1. Времева сложност

Случай	Времева сложност
Най-добър случай	На²)
Среден случай	На²)
Най-лошия случай	На²)

На²)

2. Космическа сложност

Космическа сложност	О(1)
Стабилен	ДА

Пространствената сложност на сортирането при избор е O(1). Това е така, защото при сортиране на селекцията е необходима допълнителна променлива за размяна.

Внедряване на сортиране на селекция

Сега нека видим програмите за сортиране на избор в различни езици за програмиране.

програма: Напишете програма за реализиране на сортиране при избор на език C.

 #include void selection(int arr[], int n) { int i, j, small; for (i = 0; i <n-1; 17 i++) one by move boundary of unsorted subarray { small="i;" minimum element in array for (j="i+1;" j < n; j++) if (arr[j] arr[small]) swap the with first int temp="arr[small];" arr[small]="arr[i];" arr[i]="temp;" } void printarr(int a[], n) * function to print i; (i="0;" i printf('%d ', a[i]); main() a[]="{" 12, 31, 25, 8, 32, }; n="sizeof(a)" sizeof(a[0]); printf('before sorting elements are - 
'); printarr(a, n); selection(a, printf('
after return 0; pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-7.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in C++ language.</p> <pre> #include using namespace std; void selection(int arr[], int n) { int i, j, small; for (i = 0; i <n-1; 15 i++) one by move boundary of unsorted subarray { small="i;" minimum element in array for (j="i+1;" j < n; j++) if (arr[j] arr[small]) swap the with first int temp="arr[small];" arr[small]="arr[i];" arr[i]="temp;" } void printarr(int a[], n) * function to print i; (i="0;" i cout<< a[i] <<' '; main() a[]="{" 80, 10, 29, 11, 8, 30, }; n="sizeof(a)" sizeof(a[0]); 'before sorting elements are - '<<endl; printarr(a, n); selection(a, '
after return 0; pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-8.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in C# language.</p> <pre> using System; class Selection { static void selection(int[] arr) { int i, j, small; int n = arr.Length; for (i = 0; i <n-1; i++) one by move boundary of unsorted subarray { small="i;" minimum element in array for (j="i+1;" j < n; j++) if (arr[j] arr[small]) swap the with first int temp="arr[small];" arr[small]="arr[i];" arr[i]="temp;" } static void printarr(int[] a) * function to print i; n="a.Length;" (i="0;" i console.write(a[i] + ' '); main() int[] a="{" 85, 50, 29, 18, 7, 30, 3}; console.write('before sorting elements are - printarr(a); selection(a); console.write('
after pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-9.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in python.</p> <pre> def selection(a): # Function to implement selection sort for i in range(len(a)): # Traverse through all array elements small = i # minimum element in unsorted array for j in range(i+1, len(a)): if a[small] &gt; a[j]: small = j # Swap the found minimum element with # the first element a[i], a[small] = a[small], a[i] def printArr(a): # function to print the array for i in range(len(a)): print (a[i], end = &apos; &apos;) a = [69, 14, 1, 50, 59] print(&apos;Before sorting array elements are - &apos;) printArr(a) selection(a) print(&apos;
After sorting array elements are - &apos;) selection(a) printArr(a) </pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-10.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in Java.</p> <pre> public class Selection { void selection(int a[]) /* function to sort an array with selection sort */ { int i, j, small; int n = a.length; for (i = 0; i <n-1; 21 i++) { small="i;" minimum element in unsorted array for (j="i+1;" j < n; j++) if (a[j] a[small]) swap the with first int temp="a[small];" a[small]="a[i];" a[i]="temp;" } void printarr(int a[]) * function to print i; n="a.length;" (i="0;" i system.out.print(a[i] + ' '); public static main(string[] args) a[]="{" 91, 49, 4, 19, 10, }; selection i1="new" selection(); system.out.println('
before sorting elements are - i1.printarr(a); i1.selection(a); system.out.println('
after system.out.println(); pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-11.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in PHP.</p> <pre> <?php function selection(&$a, $n) /* function to sort an array with selection sort */ { for ($i = 0; $i < $n; $i++) { $small = $i; //minimum element in unsorted array for ($j = $i+1; $j < $n; $j++) if ($a[$j] < $a[$small]) $small = $j; // Swap the minimum element with the first element $temp = $a[$small]; $a[$small] = $a[$i]; $a[$i] = $temp; } } function printArray($a, $n) { for($i = 0; $i < $n; $i++) { print_r($a[$i]); echo ' '; } } $a = array( 90, 48, 3, 18, 9, 20 ); $n = count($a); echo 'Before sorting array elements are - <br>&apos;; printArray($a, $n); selection($a, $n); echo &apos; <br> After sorting array elements are - <br>&apos;; printArray($a, $n); ?&gt; </pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-12.webp" alt="selection Sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the Selection sort complexity, working, and implementation in different programming languages.</p> <hr></n-1;></pre></n-1;></pre></n-1;></pre></n-1;>

Изход:

програма: Напишете програма за реализиране на сортиране на селекция в Java.

 public class Selection { void selection(int a[]) /* function to sort an array with selection sort */ { int i, j, small; int n = a.length; for (i = 0; i <n-1; 21 i++) { small="i;" minimum element in unsorted array for (j="i+1;" j < n; j++) if (a[j] a[small]) swap the with first int temp="a[small];" a[small]="a[i];" a[i]="temp;" } void printarr(int a[]) * function to print i; n="a.length;" (i="0;" i system.out.print(a[i] + \' \'); public static main(string[] args) a[]="{" 91, 49, 4, 19, 10, }; selection i1="new" selection(); system.out.println(\'
before sorting elements are - i1.printarr(a); i1.selection(a); system.out.println(\'
after system.out.println(); pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-11.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in PHP.</p> <pre> <?php function selection(&$a, $n) /* function to sort an array with selection sort */ { for ($i = 0; $i < $n; $i++) { $small = $i; //minimum element in unsorted array for ($j = $i+1; $j < $n; $j++) if ($a[$j] < $a[$small]) $small = $j; // Swap the minimum element with the first element $temp = $a[$small]; $a[$small] = $a[$i]; $a[$i] = $temp; } } function printArray($a, $n) { for($i = 0; $i < $n; $i++) { print_r($a[$i]); echo \' \'; } } $a = array( 90, 48, 3, 18, 9, 20 ); $n = count($a); echo \'Before sorting array elements are - <br>&apos;; printArray($a, $n); selection($a, $n); echo &apos; <br> After sorting array elements are - <br>&apos;; printArray($a, $n); ?&gt; </pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-12.webp" alt="selection Sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the Selection sort complexity, working, and implementation in different programming languages.</p> <hr></n-1;>

Изход:

След изпълнението на горния код, изходът ще бъде -

И така, това е всичко за статията. Надяваме се, че статията ще ви бъде полезна и информативна.

Тази статия не беше ограничена само до алгоритъма. Ние също така обсъдихме сложността на сортирането на Selection, работата и изпълнението в различни езици за програмиране.

TechCodeview

Алгоритъм за сортиране на селекция