Valik Sorteerimine Java Programm näitega
James Hartman
⚡ Nutikas kokkuvõte
Valiku sortimine Java skannib korduvalt massiivi sorteerimata osa, leiab väikseima allesjäänud väärtuse ja asetab selle õigesse kohta, lõpetades töö maksimaalselt n-1 vahetusega, olenemata sisendjärjekorrast.
Kuidas valiku sortimine töötab?
Valiku sortimine rakendab lihtsat sortimisalgoritmi järgmiselt:
- Algoritm otsib korduvalt madalaimat elementi.
- Vahetage praegune element madalaima väärtusega elemendiga
- Iga valiku sortimise iteratsiooni/käiguga vahetatakse elemente.
Seega kohtleb iga läbimine massiivi kahe piirkonnana: vasakult kasvav sorteeritud plokk ja paremalt kahanev sortimata plokk. Algoritm käib läbi sorteerimata ploki, jätab meelde väikseima kohatud väärtuse indeksi ja vahetab selle väärtuse esimese sorteerimata positsiooniga.
Kuna iga käigu kohta toimub ainult üks vahetus, järjestatakse n elemendist koosnev massiiv maksimaalselt n-1 vahetuse järel. See omadus eristab seda rutiini teistest algajate taseme rutiinidest. Java sorteerimisalgoritmid, mis liigutavad andmeid palju sagedamini.
. tracAllolev e järgib näidismassiivi {860, 8, 200, 9} täpselt nii, nagu järgmises jaotises olev programm selle käitusajal välja prindib.
| Sooritama | Trükitud võrdlused | Väikseim leitud väärtus | Massiiv pärast vahetust |
|---|---|---|---|
| Avaleht | - | - | 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 |
Kaks detaili selles trace-l tasub peatuda. Esiteks, 3. käik teatab ikkagi vahetusest, isegi kui järjekord ei muutu, sest väikseim allesjäänud väärtus asub juba praeguses indeksis ja programm vahetab elemendi iseendaga. Teiseks, võrdluste arv väheneb igal käigul ühe võrra (kolm, siis kaks, siis üks), mis ongi lehel allpool olevate keerukusarvude taga olev muster.
Java Programm valiku sortimise rakendamiseks
Allolev klass kannab nime SelectionSortAlgo ja asub paketis com.guru99. Meetod main() deklareerib näidismassiivi, prindib selle, annab selle sortimiseks funktsioonile selection() ja prindib uuesti. Abimeetod printArray() kirjutab kõik elemendid ühele reale, mis loob loetava möödamineku-läbimise logi.
Funktsiooni selection() sees tähistab välimine tsükkel sorteeritud ja sorteerimata piirkondade vahelist piiri, muutuja index hoiab seni nähtud väikseima väärtuse positsiooni ja iga tsükli lõpus olevad kolm omistamist teostavad vahetuse.
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(); } }
Väljund:
Klassi kompileerimine ja käivitamine loob alloleva konsooli logi, kus iga käik sisaldab ühte väljundplokki.
------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
Selle näite esmakordsel käivitamisel tekivad algajatele kaks probleemi. Kuna fail deklareerib package com.guru99;, peab allikas asuma sobivas keskkonnas com/guru99 kataloogis, vastasel juhul teatab kompilaator paketi või klassi nime mittevastavusest. Seejärel tuleb klass käivitada selle täielikult kvalifitseeritud nimega, java com.guru99.SelectionSortAlgo, sest tavaline java SelectionSortAlgo tekitab NoClassDefFoundError vea.
Tsükli piirid on teine levinud lõks. Välimine tsükkel peatub array.length - 1 ja sisemine ring algab i + 1Kummagi piiri muutmine tekitab täiendava tühja käigu või ArrayIndexOutOfBoundsExceptioni.
Valiku sortimise ajaline ja ruumiline keerukus
Programmi sisemine tsükkel jookseb alati massiivi lõpuni, seega teeb algoritm sama arvu võrdlusi, olenemata andmete väljanägemisest. n-elemendilise massiivi puhul on see summa n(n-1)/2, mis neljaelemendilise valimi puhul võrdub kuuega, ja ülaltoodud väljund prindib tõepoolest täpselt kuus võrdlusrida.
| juhtum | Võrdlused | Vahetustehingud | Aja keerukus | Abiruum |
|---|---|---|---|---|
| Parim (massiiv on juba sorteeritud) | n(n-1)/2 | n-1 | O(n²) | O (1) |
| Keskmine (juhuslikus järjekorras) | n(n-1)/2 | n-1 | O(n²) | O (1) |
| Halvim (vastupidiselt sorteeritud) | n(n-1)/2 | n-1 | O(n²) | O (1) |
Sellest ühtlasest arvude reast tulenevad kolm tagajärge:
- Valikuga sortimine ei ole adaptiivne. Sorteeritud sisend maksab täpselt sama palju kui vastupidine sisend, seega puudub selline varajase väljumise otsetee. mulli sorteerimine pakub.
- Algoritmi tugev külg on vahetuste arv. Maksimaalselt toimub n-1 vahetust, mis on palju vähem kui ruutkäiguarv, mida teised lihtsad sortimised suudavad teha.
- Mälukasutus on konstantne. Vaja on ainult tsükli loendureid ja kahte ajutist muutujat index ja smallerNumber, seega on abiruum O(1) ja sortimine toimub kohapeal.
Ruutkasv on praktiline piir. Massiivi suuruse kahekordistamine neljakordistab võrdlustöö, seega sobib valiksortimine õpetamiseks, väikesteks massiivideks ja manustatud koodiks, mitte aga tootmisandmekogumiteks, kus O(n log n) algoritmid on õige valik.
Valikulise sortimise eelised ja puudused
Algoritmi abi ja kahju mõistmine lihtsustab otsustamist, millal on selle poole pöördumine mõistlik.
Eelised
- Loogika on lühike ja loetav, mistõttu on see standardne esimene sorteerimisülesanne koos sisestamise sort.
- See sorteerib kohapeal, seega teist massiivi ei eraldata ja mälukasutus ei kasva sisendiga.
- See teeb massiivi maksimaalselt n-1 kirjutustoimingut, mis on oluline salvestusruumide puhul, kus kirjutamine on aeglane või kulutab andmekandjat.
- Selle tööaeg on täiesti etteaimatav, kuna võrdluste arv sõltub ainult massiivi pikkusest.
Puudused
- Iga juhtum on O(n²), seega algoritm ei skaleeru suurtele kogumitele.
- See ei suuda tuvastada juba sorteeritud massiivi ja seetõttu ei lõpeta see kunagi varem.
- Ülaltoodud klassikaline vorm on ebastabiilne, seega kaks võrdset väärtust võivad lõpuks olla vastupidises järjekorras.
- See võrdleb sagedamini kui sisestussortimine peaaegu järjestatud andmete puhul, kus sisestussortimine läheneb lineaarsele ajale.
Lühidalt, vali valikupõhine sortimine, kui massiiv on väike ja iga kirjutamine on kulukas, ning väldi seda juhul, kui andmestik on suur või juba peaaegu sorteeritud.
Valiku sortimine vs Bubble-sortimine vs sisestussortimine
Kõik kolm algoritmi on ruutpõhised, kohapealsed võrdlussorteerimised, kuid käituvad erinevalt, kui sisendi kuju muutub.
| Kriteerium | Valiku sortimine | Bubble-sorteerimine | Sisestuse sortimine |
|---|---|---|---|
| Parim võimalik aeg | O(n²) | O (n) | O (n) |
| Keskmine ja halvimal juhul aeg | O(n²) | O(n²) | O(n²) |
| Vahetused või halvimal juhul nihutamine | n-1 vahetustehingud | n(n-1)/2 vahetust | Kuni n(n-1)/2 vahetust |
| Stabiilne | Ei | Jah | Jah |
| Kohanduv sorteeritud sisendi suhtes | Ei | Jah | Jah |
| Abiruum | O (1) | O (1) | O (1) |
| Tüüpiline kasutamine | Vaja läheb kõige vähem kirjutusi | Sorteeritud andmete õpetamine ja märgistamine | Väikesed või peaaegu sorteeritud massiivid |
Tabel selgitab levinud intervjuuvastust. Valiksortimine on edukas vahetuste arvu poolest, mullsortimine juba järjestatud sisendi tuvastamise poolest ja sisestussortimine on praktikas neist kolmest tavaliselt kiireim, kuna reaalsed andmed on sageli osaliselt sorteeritud. Ükski neist ei konkureeri liitmissortimise ega kiirsortimisega, kui massiiv kasvab üle mõnekümne elemendi.
