streamalism.org

1. Bemutatkozás

Ebben az oktatóanyagban megtesszük megtanulja a Kiválasztás rendezése, nézze meg a Java-ban való megvalósítását és elemezze a teljesítményét.

2. Algoritmus áttekintése

Válogatás rendezése -val kezdődik az elem az 1. pozícióban egy nem rendezett tömböt, és a következő elemeken keresztül átkutat keresse meg a legkisebb elemet. Miután megtalálta, a legkisebb elemet kicserélik az 1. pozícióban lévő elemre.

Ezután az algoritmus továbbhalad a 2. pozícióban lévő elemre, és a következő elemeken átkutatva megtalálja a 2. legkisebb elem indexét. Miután megtalálta, a második legkisebb elemet felcseréljük a 2. pozícióban lévő elemmel.

Ez a folyamat addig tart, amíg el nem érjük a tömb n-1. Elemét, amely az n-1. Legkisebb elemet az n-1. Pozícióba helyezi. Az utolsó elem automatikusan a helyére esik, az n-1. Iterációban, ezáltal rendezi a tömböt.

Találunk a legnagyobb elem a legkisebb elem helyett a tömb csökkenő sorrendbe rendezéséhez.

Lássunk egy példát egy nem rendezett tömbre, és rendezzük növekvő sorrendbe, hogy vizuálisan megértsük az algoritmust.

2.1. Egy példa

Vegye figyelembe a következő rendezetlen tömböt:

int [] arr = {5, 4, 1, 6, 2}

1. iteráció

Figyelembe véve az algoritmus fenti működését, az elemet az 1. pozícióban kezdjük - 5 -, és az összes következő elemet átvizsgáljuk, hogy megtaláljuk a legkisebb elemet - 1. Ezután kicseréljük a legkisebb elemet az 1. pozícióban lévő elemgel.

A módosított tömb nows a következőképpen néz ki:

{ 1 , 4 , 5 , 6 , 2 }

Összehasonlítás: 4

2. iteráció

A második iterációban továbblépünk a 2. elemre - 4 -, és átvizsgáljuk a következő elemeket, hogy megtaláljuk a második legkisebb elemet - 2. Ezután kicseréljük a második legkisebb elemet úgy, hogy az elem a 2. helyzetben van.

A módosított tömb most így néz ki:

{ 1 , 2 , 5 , 6 , 4 }

Összehasonlítás: 3

Hasonlóan folytatva a következő iterációkat hajtjuk végre:

3. iteráció

{ 1 , 2 , 4 , 6 , 5 }

Összes összehasonlítás: 2

4. iteráció

{ 1 , 2 , 4 , 5 , 6 }

Összes összehasonlítás: 1

3.Végrehajtás

Vezessük be a Selection Sort-ot pár használatával mert hurkok:

public static void sortAscending (final int [] arr) {for (int i = 0; i <arr.length - 1; i ++) {int minElementIndex = i; mert (int j = i + 1; j arr [j]) {minElementIndex = j; }} if (minElementIndex! = i) {int temp = arr [i]; arr [i] = arr [minElementIndex]; arr [minElementIndex] = hőmérséklet; }}}

Természetesen ennek megfordításához valami hasonlót tehetnénk:

public static void sortDescending (final int [] arr) {for (int i = 0; i <arr.length - 1; i ++) {int maxElementIndex = i; for (int j = i + 1; j <arr.length; j ++) {if (arr [maxElementIndex] <arr [j]) {maxElementIndex = j; }} if (maxElementIndex! = i) {int temp = arr [i]; arr [i] = arr [maxElementIndex]; arr [maxElementIndex] = hőmérséklet; }}}

És egy kicsit több könyökzsírral ezeket kombinálhatnánk Összehasonlítós.

4. Teljesítmény áttekintés

4.1. Idő

A korábban látott példában a legkisebb elem kiválasztásához összesen: (n-1) összehasonlítások majd kicserélte az 1. pozícióba. Hasonlóképpen, a következő legkisebb elem kiválasztása szükséges összes (n-2) összehasonlítások, majd csere a 2. pozícióban stb.

Így a 0 indexből kiindulva teljesítünk n-1, n-2, n-3, n-4…. 1 összehasonlítások. Az utolsó elem a korábbi iterációk és cserék miatt automatikusan a helyére kerül.

Matematikailag a az első összege n-1 természetes számok megmondja, hány összehasonlításra van szükségünk egy tömb méretének rendezéséhez n a Selection Sort használatával.

Az összeg összegének képlete n természetes számok az n (n + 1) / 2.

Esetünkben az első összegére van szükség n-1 természetes számok. Ezért kicseréljük n val vel n-1 a fenti képletben:

(n-1) (n-1 + 1) / 2 = (n-1) n / 2 = (n ^ 2-n) / 2

Mint n ^ 2 jól láthatóan növekszik n növekszik, figyelembe vesszük a n mint teljesítmény benchmark, így ennek az algoritmusnak van egy időbeli összetettsége O (n ^ 2).

4.2. Tér

A kiegészítő tér bonyolultsága szempontjából a Selection Sort egy további változót igényel, hogy ideiglenesen megtartsa az értéket a cseréhez. Ezért a Selection Sort's a tér bonyolultsága az O (1).

5. Következtetés

A Selection Sort egy nagyon egyszerű rendezési algoritmus a megértéshez és megvalósításhoz. Sajnálatos módon, másodfokú időbeli összetettsége drága válogatási technikává teszi. Továbbá, mivel az algoritmusnak át kell olvasnia az egyes elemeket, a legjobb, átlagos és a legrosszabb idő összetettsége megegyezik.

Más rendezési technikák, például az Insertion Sort és a Shell Sort szintén másodfokú legrosszabb időbeli összetettséggel bírnak, de jobb és átlagos esetben jobban teljesítenek.

Nézze meg a GitHubon a Selection Sort over teljes kódját.