ATLASE KĀRTOT - DS APMĀCĪBA

Šajā rakstā mēs apspriedīsim atlases kārtošanas algoritmu. Arī atlases kārtošanas darba procedūra ir vienkārša. Šis raksts būs ļoti noderīgs un interesants studentiem, jo viņi eksāmenos var saskarties ar atlases veidu. Tāpēc ir svarīgi apspriest tēmu.

Atlases kārtošanā mazākā vērtība starp nešķirotajiem masīva elementiem tiek atlasīta katrā piegājienā un ievietota tai atbilstošajā masīvā. Tas ir arī vienkāršākais algoritms. Tas ir uz vietas veikts salīdzināšanas šķirošanas algoritms. Šajā algoritmā masīvs ir sadalīts divās daļās, pirmā ir sakārtotā daļa, bet vēl viena ir nešķirotā daļa. Sākotnēji sakārtotā masīva daļa ir tukša, bet nešķirotā daļa ir dotais masīvs. Sašķiroto daļu novieto pa kreisi, bet nešķiroto daļu novieto pa labi.

Atlases kārtošanā pirmais mazākais elements tiek atlasīts no nešķirotā masīva un novietots pirmajā pozīcijā. Pēc tam tiek atlasīts otrs mazākais elements un novietots otrajā pozīcijā. Process turpinās, līdz masīvs ir pilnībā sakārtots.

Atlases šķirošanas vidējā un sliktākā gadījuma sarežģītība ir O(n²) , kur n ir vienumu skaits. Šī iemesla dēļ tas nav piemērots lielām datu kopām.

Atlases kārtošana parasti tiek izmantota, ja -

Neliels masīvs ir jāsakārto
Maiņas maksai nav nozīmes
Ir obligāti jāpārbauda visi elementi

Tagad apskatīsim atlases kārtošanas algoritmu.

Algoritms

 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

Atlases kārtošanas algoritma darbība

Tagad apskatīsim atlases kārtošanas algoritma darbību.

Lai saprastu atlases kārtošanas algoritma darbību, ņemsim nešķirotu masīvu. Atlases kārtošanu būs vieglāk saprast, izmantojot piemēru.

Lai masīva elementi ir -

Tagad, lai iegūtu pirmo pozīciju sakārtotajā masīvā, viss masīvs ir jāskenē secīgi.

Tagadnē, 12 tiek saglabāts pirmajā pozīcijā, pēc visa masīva meklēšanas tiek konstatēts, ka 8 ir mazākā vērtība.

klase vs objekts java

Tātad, samainiet 12 ar 8. Pēc pirmās iterācijas 8 parādīsies sakārtotā masīva pirmajā pozīcijā.

Otrajā pozīcijā, kur pašlaik tiek glabāti 29, mēs atkal secīgi skenējam pārējos nešķirotā masīva vienumus. Pēc skenēšanas mēs atklājam, ka 12 ir otrs zemākais elements masīvā, kam vajadzētu parādīties otrajā pozīcijā.

Tagad samainiet 29 ar 12. Pēc otrās iterācijas 12 parādīsies sakārtotā masīva otrajā pozīcijā. Tātad pēc divām iterācijām divas mazākās vērtības tiek sakārtotas sākumā.

Tas pats process tiek piemērots pārējiem masīva elementiem. Tagad mēs rādām visa šķirošanas procesa attēlu.

Tagad masīvs ir pilnībā sakārtots.

Atlases kārtošanas sarežģītība

Tagad apskatīsim atlases kārtošanas laika sarežģītību labākajā gadījumā, vidējā gadījumā un sliktākajā gadījumā. Mēs redzēsim arī atlases kārtošanas telpas sarežģītību.

1. Laika sarežģītība

Lieta	Laika sarežģītība
Labākais gadījums	O(n²)
Vidējais gadījums	O(n²)
Sliktākajā gadījumā	O(n²)

O(n²)

2. Telpas sarežģītība

Kosmosa sarežģītība	O(1)
Stabils	JĀ

Atlases kārtošanas telpas sarežģītība ir O(1). Tas ir tāpēc, ka atlases kārtošanā ir nepieciešams papildu mainīgais apmaiņai.

Atlases šķirošanas ieviešana

Tagad apskatīsim atlases programmu šķirošanu dažādās programmēšanas valodās.

Programma: Uzrakstiet programmu atlases kārtošanas ieviešanai C valodā.

 #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;>

Izvade:

Programma: Uzrakstiet programmu, lai ieviestu atlases kārtošanu 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;>

Izvade:

Pēc iepriekš minētā koda izpildes izvade būs -

Tātad, tas viss par rakstu. Cerams, ka raksts jums būs noderīgs un informatīvs.

Šis raksts neaprobežojās tikai ar algoritmu. Mēs esam apsprieduši arī atlases kārtošanas sarežģītību, darbību un ieviešanu dažādās programmēšanas valodās.

TechCodeview

Atlases kārtošanas algoritms