KIJELÖLÉS RENDEZÉSE - DS OKTATÓANYAG

Ebben a cikkben a kijelölési rendezési algoritmust tárgyaljuk. A kiválasztási rendezés munkamenete is egyszerű. Ez a cikk nagyon hasznos és érdekes lesz a hallgatók számára, mivel a vizsgáik során kiválasztási kérdésként szembesülhetnek. Ezért fontos a téma megvitatása.

A kiválasztási rendezésnél a tömb rendezetlen elemei közül a legkisebb érték kerül kiválasztásra minden lépésben, és a megfelelő pozícióba kerül a tömbbe. Ez a legegyszerűbb algoritmus is. Ez egy helyben használható összehasonlító rendezési algoritmus. Ebben az algoritmusban a tömb két részre van osztva, először a rendezett rész, a másik pedig a rendezetlen rész. Kezdetben a tömb rendezett része üres, a rendezetlen rész pedig az adott tömb. A szortírozott rész balra, míg a nem rendezett rész jobbra kerül.

A kijelölési rendezésben az első legkisebb elem kerül kiválasztásra a rendezetlen tömbből, és az első helyre kerül. Ezután a második legkisebb elemet kiválasztjuk és a második pozícióba helyezzük. A folyamat addig folytatódik, amíg a tömb teljesen meg nem rendeződik.

A kiválasztási rendezés átlagos és legrosszabb összetettsége az Tovább²) , ahol n az elemek száma. Emiatt nem alkalmas nagy adathalmazokra.

A kijelölés rendezése általában akkor használatos, ha -

Egy kis tömböt kell rendezni
A csere költsége nem számít
Minden elem ellenőrzése kötelező

Most pedig lássuk a kiválasztási rendezés algoritmusát.

Algoritmus

 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

Kiválasztási rendezési algoritmus működése

Most lássuk a Kijelölés rendezési algoritmus működését.

A Kijelölés rendezési algoritmus működésének megértéséhez vegyünk egy rendezetlen tömböt. Egy példán keresztül könnyebb lesz megérteni a kijelölés rendezést.

Legyen a tömb elemei -

Most a rendezett tömb első pozíciójához a teljes tömböt szekvenciálisan kell vizsgálni.

Jelenleg, 12 az első pozícióban van tárolva, a teljes tömbben való keresés után azt találjuk, hogy 8 a legkisebb érték.

teáskanál vs evőkanál

Tehát cserélje fel a 12-t 8-cal. Az első iteráció után a 8 megjelenik a rendezett tömb első pozíciójában.

A második pozícióhoz, ahol jelenleg a 29 van tárolva, ismét egymás után szkenneljük a rendezetlen tömb többi elemét. A szkennelés után azt találjuk, hogy a 12 a második legalacsonyabb elem a tömbben, amelynek a második pozícióban kell megjelennie.

Most cserélje fel a 29-et 12-re. A második iteráció után a 12 megjelenik a rendezett tömb második pozíciójában. Tehát két iteráció után a két legkisebb érték rendezve kerül az elejére.

Ugyanezt a folyamatot alkalmazzuk a tömb többi elemére is. Most a teljes rendezési folyamat képi ábrázolását mutatjuk be.

Most a tömb teljesen rendezve van.

A kijelölés rendezési összetettsége

Most lássuk a kiválasztási rendezés időbeli összetettségét legjobb, átlagos és legrosszabb esetben. Látni fogjuk a kijelölési rendezés térbeli összetettségét is.

1. Időbonyolultság

Ügy	Idő összetettsége
Legjobb eset	Tovább²)
Átlagos eset	Tovább²)
Legrosszabb esetben	Tovább²)

Tovább²)

2. A tér összetettsége

A tér összetettsége	O(1)
Stabil	IGEN

A szelekciós rendezés térkomplexitása O(1). Ez azért van így, mert a kijelölési rendezésnél egy extra változóra van szükség a cseréhez.

Kiválasztási rendezés megvalósítása

Most lássuk a kiválasztási programokat különböző programozási nyelveken.

Program: Írjon programot a kiválasztási rendezés megvalósítására C nyelven.

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

Kimenet:

Program: Írjon programot a kijelölési rendezés megvalósítására Java nyelven.

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

Kimenet:

A fenti kód végrehajtása után a kimenet a következő lesz:

Szóval ennyi a cikkről. Reméljük, hogy a cikk hasznos és informatív lesz az Ön számára.

Ez a cikk nem csak az algoritmusra korlátozódott. Megbeszéltük a kijelölés rendezési összetettségét, működését és megvalósítását a különböző programozási nyelveken is.