Valinta Lajittelu Java Ohjelma esimerkin kanssa
James Hartman
⚡ Älykäs yhteenveto
Valinnan lajitteluperuste Java skannaa toistuvasti taulukon lajittelemattoman osan, löytää pienimmän jäljellä olevan arvon ja vaihtaa sen paikoilleen, viimeistellen työn enintään n-1 vaihdolla syöttöjärjestyksestä riippumatta.
Miten valintalajittelu toimii?
Valintalajittelu toteuttaa yksinkertaisen lajittelualgoritmin seuraavasti:
- Algoritmi etsii toistuvasti alinta elementtiä.
- Vaihda nykyinen elementti pienimmän arvon omaavaan elementtiin
- Jokaisella valintalajittelun iteraatiolla/passilla elementtejä vaihdetaan.
Jokainen kierros siis käsittelee ryhmä kahtena alueena: lajiteltu lohko, joka kasvaa vasemmalta, ja lajittelematon lohko, joka kutistuu oikealta. Algoritmi kävelee lajittelemattoman lohkon läpi, muistaa pienimmän kohtaamansa arvon indeksin ja vaihtaa kyseisen arvon ensimmäisen lajittelemattoman sijainnin kanssa.
Koska vain yksi vaihto tapahtuu kerrallaan, n alkion taulukko järjestetään enintään n-1 vaihdon jälkeen. Tämä ominaisuus erottaa tämän rutiinin muista aloittelijatason rutiineista. Java lajittelualgoritmeja, jotka siirtävät dataa paljon useammin.
tracAlla oleva e seuraa esimerkkitaulukkoa {860, 8, 200, 9} täsmälleen samalla tavalla kuin seuraavan osan ohjelma tulostaa sen suorituksen aikana.
| Siirtää | Vertailut tulostettu | Pienin löydetty arvo | Taulukko vaihdon jälkeen |
|---|---|---|---|
| Aloita | - | - | 860 8 200 9 |
| 1 | 860 ja 8, 8 ja 200, 8 ja 9 | 8 | 8 860 200 9 |
| 2 | 860 ja 200, 200 ja 9 | 9 | 8 9 200 860 |
| 3 | 200 ja 860 | 200 | 8 9 200 860 |
Kaksi yksityiskohtaa siinä trace:hen kannattaa pysähtyä. Ensinnäkin kolmas vaihe raportoi edelleen vaihdon, vaikka järjestys ei muutu, koska pienin jäljellä oleva arvo on jo nykyisessä indeksissä ja ohjelma vaihtaa elementin itsensä kanssa. Toiseksi vertailujen määrä laskee yhdellä jokaisella kierroksella (kolme, sitten kaksi, sitten yksi), mikä on sivulla alempana olevien monimutkaisuuslukujen taustalla oleva kaava.
Java Ohjelma valintalajittelun toteuttamiseksi
Alla oleva luokka on nimeltään SelectionSortAlgo ja sijaitsee paketissa com.guru99. main()-metodi määrittelee esimerkkitaulukon, tulostaa sen, antaa sen selection()-metodille lajittelua varten ja tulostaa sen uudelleen. Apumetodi printArray() kirjoittaa kaikki elementit yhdelle riville, joka tuottaa luettavan läpikulkulokin.
Selection()-funktion sisällä ulompi silmukka merkitsee lajiteltujen ja lajittelemattomien alueiden välisen rajan, index-muuttuja säilyttää tähän mennessä nähdyn pienimmän arvon sijaintia ja kunkin kierroksen lopussa olevat kolme sijoitusta suorittavat vaihdon.
package com.guru99; public class SelectionSortAlgo { public static void main(String a[]) { int[] myArray = {860,8,200,9}; System.out.println("------Before Selection Sort-----"); printArray(myArray); selection(myArray);//sorting array using selection sort System.out.println("-----After Selection Sort-----"); printArray(myArray); } public static void selection(int[] array) { for (int i = 0; i < array.length - 1; i++) { System.out.println("Sort Pass Number "+(i+1)); int index = i; for (int j = i + 1; j < array.length; j++) { System.out.println("Comparing "+ array[index] + " and " + array[j]); if (array[j] < array[index]){ System.out.println(array[index] + " is greater than " + array[j] ); index = j; } } int smallerNumber = array[index]; array[index] = array[i]; array[i] = smallerNumber; System.out.println("Swapping Elements: New Array After Swap"); printArray(array); } } static void printArray(int[] array){ for(int i=0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println(); } }
lähtö:
Luokan kääntäminen ja suorittaminen tuottaa alla olevan konsolilokin, jossa on yksi tulostelohko per suorituskerta.
------Before Selection Sort----- 860 8 200 9 Sort Pass Number 1 Comparing 860 and 8 860 is greater than 8 Comparing 8 and 200 Comparing 8 and 9 Swapping Elements: New Array After Swap 8 860 200 9 Sort Pass Number 2 Comparing 860 and 200 860 is greater than 200 Comparing 200 and 9 200 is greater than 9 Swapping Elements: New Array After Swap 8 9 200 860 Sort Pass Number 3 Comparing 200 and 860 Swapping Elements: New Array After Swap 8 9 200 860 -----After Selection Sort----- 8 9 200 860
Aloittelijoille tulee kaksi ongelmaa, kun he suorittavat tämän esimerkin ensimmäistä kertaa. Koska tiedostossa deklaroidaan package com.guru99;, lähteen on sijaittava vastaavassa com/guru99 hakemistossa, muuten kääntäjä ilmoittaa paketin tai luokan nimen ristiriidasta. Luokka on tällöin käynnistettävä sen täydellisellä nimellä, java com.guru99.SelectionSortAlgo, koska tavallinen java SelectionSortAlgo aiheuttaa NoClassDefFoundError-virheen.
Silmukan rajat ovat toinen yleinen ansa. Ulompi silmukka pysähtyy kohtaan array.length - 1 ja sisempi silmukka alkaa kohdasta i + 1Jommankumman rajan muuttaminen tuottaa ylimääräisen tyhjän läpikulun tai ArrayIndexOutOfBoundsException-poikkeuksen.
Valinnan aika- ja paikkakompleksisuus Lajittelu
Ohjelman sisempi silmukka jatkuu aina taulukon loppuun, joten algoritmi suorittaa saman määrän vertailuja riippumatta siitä, miltä data näyttää. N alkion taulukolla tämä summa on n(n-1)/2, mikä neljän alkion otoksella on kuusi, ja yllä oleva tuloste tulostaakin tasan kuusi vertailuriviä.
| tapaus | Vertailut | vaihtosopimukset | Ajan monimutkaisuus | Aputila |
|---|---|---|---|---|
| Paras (taulukko jo lajiteltu) | n(n-1)/2 | n-1 | O(n²) | O (1) |
| Keskiarvo (satunnainen järjestys) | n(n-1)/2 | n-1 | O(n²) | O (1) |
| Huonoin (käänteisessä järjestyksessä) | n(n-1)/2 | n-1 | O(n²) | O (1) |
Yhtenäisestä numerorivistä seuraa kolme seurausta:
- Valintalajittelu ei ole mukautuva. Lajiteltu syöte maksaa täsmälleen yhtä paljon kuin käänteinen syöte, joten ei ole olemassa sellaista oikotietä varhaiseen poistumiseen. kupla tarjoaa.
- Algoritmin vahvuus on sen vaihtojen määrä. Vaihtoja tapahtuu korkeintaan n-1, mikä on paljon vähemmän kuin muiden yksinkertaisten lajittelujen tekemien siirtojen neliöllinen määrä.
- Muistin käyttö on vakio. Tarvitaan vain silmukkalaskurit ja kaksi väliaikaista muuttujaa index ja smallerNumber, joten aputila on O(1) ja lajittelu tapahtuu paikan päällä.
Käytännössä neliöllinen kasvu on raja. Taulukon koon kaksinkertaistaminen noin nelinkertaistaa vertailutyön, joten valintalajittelu sopii opetukseen, pieniin taulukoihin ja sulautettuun koodiin pikemminkin kuin tuotantodatajoukkoihin, joissa O(n log n) -algoritmit ovat oikea valinta.
Valintalajittelun edut ja haitat
Algoritmin ymmärtäminen auttaa ja haittaa helpottaa päätöksentekoa siitä, milloin sen käyttö on järkevää.
edut
- Logiikka on lyhyttä ja helposti luettavaa, minkä vuoksi se on vakiomuotoinen ensimmäinen lajitteluharjoitus rinnakkain lisäyslaji.
- Se lajittelee paikallaan, joten toista taulukkoa ei varata eikä muistin käyttö kasva syötteen mukana.
- Se suorittaa enintään n-1 kirjoituskertaa taulukkoon, millä on merkitystä tallennustilassa, jossa kirjoitukset ovat hitaita tai kuluttavat tallennusvälinettä.
- Sen suoritusaika on täysin ennustettavissa, koska vertailujen määrä riippuu vain taulukon pituudesta.
Haitat
- Jokainen tapaus on O(n²), joten algoritmi ei skaalaudu suuriin kokoelmiin.
- Se ei pysty havaitsemaan jo lajiteltua taulukkoa, joten se ei koskaan pääty loppuun ennenaikaisesti.
- Yllä esitetty klassinen muoto on epävakaa, joten kaksi yhtä suurta arvoa voi päätyä päinvastaiseen järjestykseen.
- Se vertailee useammin kuin lisäyslajittelu lähes järjestetyssä datassa, jossa lisäyslajittelu lähestyy lineaarista aikaa.
Lyhyesti sanottuna, valitse valintalajittelu, kun taulukko on pieni ja jokainen kirjoitus on kallista, ja vältä sitä aina, kun tietojoukko on suuri tai jo lähes lajiteltu.
Valintalajittelu vs. Bubble-lajittelu vs. lisäyslajittelu
Kaikki kolme algoritmia ovat kvadraattisia, paikallaan tapahtuvia vertailuja, mutta ne käyttäytyvät eri tavalla, kun syötteen muoto muuttuu.
| Kriteeri | Valinnan lajittelu | Bubble-lajittelu | Lisäyslajittelu |
|---|---|---|---|
| Parhaan mahdollisen ajankohdan | O(n²) | O (n) | O (n) |
| Keskimääräinen ja pahin mahdollinen aika | O(n²) | O(n²) | O(n²) |
| Vaihdot tai pahimmassa tapauksessa siirrot | n-1 swapit | n(n-1)/2 swapia | Jopa n(n-1)/2 vuoroa |
| Vakaa | Ei | Kyllä | Kyllä |
| Mukautuu lajiteltuun syötteeseen | Ei | Kyllä | Kyllä |
| Aputila | O (1) | O (1) | O (1) |
| Tyypillinen käyttö | Vähiten kirjoituksia tarvitaan | Lajitellun datan opettaminen ja havaitseminen | Pienet tai lähes lajitellut taulukot |
Taulukossa selitetään yleinen haastatteluvastaus. Valintalajittelu voittaa vaihtojen lukumäärän perusteella, kuplalajittelu jo järjestetyn syötteen tunnistamisen perusteella ja lisäyslajittelu on yleensä käytännössä nopein näistä kolmesta, koska todellinen data on usein osittain lajiteltu. Mikään niistä ei kilpaile yhdistämislajittelun tai pikalajittelun kanssa, kun taulukko kasvaa muutaman kymmenen alkion yli.
