TechCodeview

Ebben az oktatóanyagban a kiválasztási rendezési algoritmust fogjuk megvalósítani a Pythonban. Ez egy nagyon egyszerű algoritmus, amely kevesebb cserét használ.

Ebben az algoritmusban minden lépésben kiválasztjuk a legkisebb elemet egy rendezetlen tömbből, és felcseréljük a rendezetlen tömb elejével. Ez a folyamat addig folytatódik, amíg az összes elem a megfelelő helyre nem kerül. Ez egy egyszerű és egy helyben használható összehasonlító rendezési algoritmus.

A kijelölés rendezése

Az alábbiakban bemutatjuk a Pythonban a Kijelölés rendezés működését elmagyarázó lépéseket.

Vegyünk egy rendezetlen tömböt a kiválasztási rendezési algoritmus alkalmazásához.

[30, 10, 12, 8, 15, 1]

1. lépés: Adja meg a tömb hosszát.

hossz = len(tömb) → 6

2. lépés: Először az első elemet állítjuk be minimális elemnek.

3. lépés: Most hasonlítsa össze a minimumot a második elemmel. Ha a második elem kisebb, mint az első, akkor minimumként hozzárendeljük.

Ismét összehasonlítjuk a második elemet a harmadikkal, és ha a harmadik elem kisebb, mint a második, rendelje hozzá minimumként. Ez a folyamat addig tart, amíg meg nem találjuk az utolsó elemet.

4. lépés: Minden iteráció után a minimális elemet felcseréljük a rendezetlen tömb előtt.

5. lépés: A második-harmadik lépést addig ismételjük, amíg meg nem kapjuk a rendezett tömböt.

Kiválasztási rendezési algoritmus

A kiválasztási rendezési algoritmus a következő.

Algoritmus

 selection_sort(array) repeat (0, length - 1) times set the first unsorted element as the minimum for each of the unsorted elements if element <currentminimum set element as new minimum swap with first unsorted position end selection_sort < pre> <h2>Selection Sort Program using Python</h2> <p>The following code snippet shows the selection sort algorithm implementation using Python.</p> <p> <strong>Code -</strong> </p> <pre> def selection_sort(array): length = len(array) for i in range(length-1): minIndex = i for j in range(i+1, length): if array[j] <array[minindex]: minindex="j" array[i], array[minindex]="array[minIndex]," array[i] return array print('the sorted is: ', selection_sort(array)) < pre> <p> <strong>Output:</strong> </p> <pre> The sorted array is: [3, 6, 9, 21, 33] </pre> <p> <strong>Explanation -</strong> </p> <p>Let&apos;s understand the above code -</p> <ul> <li>First, we define the <strong>selection_sort()</strong> function that takes array as an argument.</li> <li>In the function, we get the length of the array which used to determine the number of passes to be made comparing values.</li> <li>As we can see that, we use two loops - outer and inner loop. The outer loop uses to iterate through the values of the list. This loop will iterate to 0 to (length-1). So the first iteration will be perform (5-1) or 4 times. In each iteration, the value of the variable i is assigned to the variable</li> <li>The inner loop uses to compare the each value of right-side element to the other value on the leftmost element. So the second loop starts its iteration from i+1. It will only pick the value that is unsorted.</li> <li>Find the minimum element in the unsorted list and update the minIndex position.</li> <li>Place the value at the beginning of the array.</li> <li>Once the iteration is completed, the sorted array is returned.</li> <li>At last we create an unsorted array and pass to the <strong>selection_sort()</strong> It prints the sorted array.</li> </ul> <h2>Time Complexity of Selection Sort</h2> <p>Time complexity is an essential in term of how much time an algorithm take to sort it. In the selection sort, there are two loops. The outer loop runs for the n times (n is a total number of element).</p> <p>The inner loop is also executed for n times. It compares the rest of the value to outer loop value. So, there is n*n times of execution. Hence the time complexity of merge sort algorithm is O(n<sup>2</sup>).</p> <p>The time complexity can be categorized into three categories.</p> <hr></array[minindex]:></pre></currentminimum>

Magyarázat -

Értsük meg a fenti kódot -

• Először is meghatározzuk a select_sort() függvény, amely a tömböt veszi argumentumként.
• A függvényben megkapjuk annak a tömbnek a hosszát, amely az értékeket összehasonlító lépések számát határozta meg.
• Amint látjuk, két hurkot használunk - külső és belső hurkot. A külső ciklus a lista értékei közötti iterációt használja. Ez a ciklus 0-tól (hossz-1-ig) ismétlődik. Tehát az első iterációt (5-1) vagy 4 alkalommal hajtjuk végre. Minden iterációban az i változó értéke hozzá van rendelve a változóhoz
• A belső hurok a jobb oldali elem egyes értékeinek összehasonlítására szolgál a bal szélső elem másik értékével. Tehát a második ciklus az i+1-től kezdi az iterációt. Csak a rendezetlen értéket választja ki.
• Keresse meg a minimális elemet a rendezetlen listában, és frissítse a minIndex pozíciót.
• Helyezze az értéket a tömb elejére.
• Az iteráció befejezése után a rendezett tömb visszaadásra kerül.
• Végül létrehozunk egy rendezetlen tömböt, és továbblépünk a select_sort() Kiírja a rendezett tömböt.

A kiválasztási rendezés időbeli összetettsége

Az időbonyolultság alapvető fontosságú abból a szempontból, hogy egy algoritmus mennyi időt vesz igénybe annak rendezéséhez. A kiválasztási rendezésben két hurok található. A külső ciklus n-ig fut (n az elemek teljes száma).

A belső ciklus is végrehajtódik n-szer. Összehasonlítja az érték többi részét a külső hurok értékével. Tehát n*n végrehajtási idő van. Ezért az összevonási rendezési algoritmus időbonyolultsága O(n²).

Az idő bonyolultsága három kategóriába sorolható.