Šajā apmācībā mēs ieviesīsim atlases kārtošanas algoritmu programmā Python. Tas ir diezgan vienkāršs algoritms, izmantojot mazāku apmaiņu.
java virkņu savienošana
Šajā algoritmā mēs atlasām mazāko elementu no nešķirota masīva katrā piegājienā un apmainām ar nešķirotā masīva sākumu. Šis process turpināsies, līdz visi elementi ir novietoti pareizajā vietā. Tas ir vienkāršs un vietā salīdzināšanas šķirošanas algoritms.
Atlases kārtošanas darbība
Tālāk ir norādītas darbības, lai izskaidrotu atlases kārtošanas darbību Python.
Paņemsim nešķirotu masīvu, lai lietotu atlases kārtošanas algoritmu.
[30, 10, 12, 8, 15, 1]
1. darbība: Iegūstiet masīva garumu.
garums = len(masīvs) → 6
2. darbība: Pirmkārt, mēs iestatām pirmo elementu kā minimālo elementu.
3. darbība: Tagad salīdziniet minimumu ar otro elementu. Ja otrais elements ir mazāks par pirmo, mēs to piešķiram kā minimumu.
Atkal mēs salīdzinām otro elementu ar trešo un, ja trešais elements ir mazāks par otro, piešķiriet to kā minimumu. Šis process turpinās, līdz atrodam pēdējo elementu.
4. darbība: Pēc katras iterācijas minimālais elements tiek apmainīts nešķirotā masīva priekšā.
5. darbība: Otro līdz trešo darbību atkārto, līdz iegūstam sakārtoto masīvu.
Atlases kārtošanas algoritms
Atlases kārtošanas algoritms ir šāds.
Algoritms
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'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> Paskaidrojums -
Sapratīsim iepriekš minēto kodu -
- Pirmkārt, mēs definējam Selection_sort() funkcija, kas izmanto masīvu kā argumentu.
- Funkcijā mēs iegūstam masīva garumu, kas tika izmantots, lai noteiktu vērtību salīdzināšanas piegājienu skaitu.
- Kā redzam, mēs izmantojam divas cilpas - ārējo un iekšējo cilpu. Ārējā cilpa izmanto saraksta vērtību atkārtošanai. Šī cilpa atkārtosies no 0 līdz (garums-1). Tātad pirmā iterācija tiks veikta (5-1) vai 4 reizes. Katrā iterācijā mainīgajam tiek piešķirta mainīgā i vērtība
- Iekšējā cilpa izmanto, lai salīdzinātu katra labās puses elementa vērtību ar citu vērtību, kas atrodas vistālāk kreisajā elementā. Tātad otrā cilpa sāk savu iterāciju no i+1. Tas atlasīs tikai nešķiroto vērtību.
- Atrodiet minimālo elementu nešķirotajā sarakstā un atjauniniet minIndex pozīciju.
- Novietojiet vērtību masīva sākumā.
- Kad iterācija ir pabeigta, sakārtotais masīvs tiek atgriezts.
- Visbeidzot mēs izveidojam nešķirotu masīvu un pārejam uz Selection_sort() Tas izdrukā sakārtoto masīvu.
Atlases kārtošanas laika sarežģītība
Laika sarežģītība ir būtiska, lai noteiktu, cik daudz laika algoritmam nepieciešams, lai to sakārtotu. Atlases kārtojumā ir divas cilpas. Ārējā cilpa darbojas n reizes (n ir kopējais elementu skaits).
pārvērst virkni par enum
Iekšējā cilpa arī tiek izpildīta n reizes. Tas salīdzina pārējo vērtību ar ārējās cilpas vērtību. Tātad ir n*n izpildes reizes. Tādējādi sapludināšanas kārtošanas algoritma laika sarežģītība ir O (n2).
Laika sarežģītību var iedalīt trīs kategorijās.