Algoritmide sortimine Java - Java-tüüpi sorteerimisalgoritmide erinevad tüübid

• Sissejuhatus Java algoritmide sortimisse

Sissejuhatus Java algoritmide sortimisse

Teabe sortimine kindlas järjekorras, sageli massiivilaadses raamistikus, on selle korraldamine. Võite kasutada erinevaid järjekorranõudeid, populaarsed on numbrite sorteerimine väikseimast suurima või vastupidi või leksikograafiliselt stringi sortimine. Kui olete huvitatud sorteerimisest, käsitleme erinevaid algoritme alates ebaefektiivsetest, kuid intuitiivsetest alternatiividest kuni tõhusate algoritmideni, mida rakendatakse Java ja teistes keeltes.

Erinevad sortimisalgoritmid javas

Sorteerimise algoritme on erinevaid ja mitte kõik neist pole võrdselt tõhusad. Nende võrdlemiseks ja kõige paremate tulemuste saamiseks analüüsime nende aja keerukust.

1. Sisestuse sortimine
2. Mullide sortimine
3. Valiku sortimine
4. Ühenda sortimine
5. Heapsort

1. Sisestuse sortimine

Lisamise sortimise idee jagab vahemiku sorteeritud ja sortimata alamreaalideks. Klassifitseeritud osa on kestuse 1 alguses ja sobib massiivi esimese (vasakpoolse) komponendiga. Liigume läbi massiivi ja laiendame massiivi klassifitseeritud osa ühe iteratsiooni ajal ühe komponendi võrra. Laienemisel paigutame värske elemendi sorteeritud alammassiivi. Teeme seda, liigutades kõiki elemente paremale, kuni leiame, et me ei pea esimest komponenti muutma. Kui paks osa sorteeritakse kasvavas järjekorras, näiteks järgmises massiivis, toimub see:

1. 3 5 7 8 4 2 1 9 6: Mõelge 4-le ja seda on vaja sisestada. Oleme nihkunud alates 8> 4
2. 2. 3 5 7 x 8 2 1 9 6
3. 3 5 x 7 8 2 1 9 6
4. 3 x 5 7 8 2 1 9 6
5. 3 4 5 7 8 2 1 9 6

Kood:

public class InsertionSortEx (
public static void insertionSort(int() arr) (
for (int x = 1; x < arr.length; x++) (
int current = arr(x);
int y = x - 1;
while(y >= 0 && current < arr(y)) (
arr(y+1) = arr(y);
y--;
)
arr(y+1) = current;
)
)
public static void main(String a())(
int() arr1 = (3, 5, 7, 8, 4, 2, 1, 9, 6);
System.out.println("Before Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
System.out.println();
insertionSort(arr1);//sorting array using insertion sort
System.out.println("After Insertion Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
)
)

Väljund:

Seda meetodit järgides laiendas üks komponent sorteeritud osa, nüüd on meil nelja elemendi asemel viis. Iga iteratsioon teeb seda ja kogu massiiv sorteeritakse lõpuks.

Märkus. Põhjus on see, et me peame kogu itereerimisel kogu salastatud loendi ükshaaval üle kandma, st O (n). Iga tabeli iga komponendi puhul peame seda tegema, mis tähendab, et see on O (n 2) piiratud.2.

2. Mullide sortimine

Kui mull ei ole vajalikus järjekorras, töötab see naaberkomponentide asendamise teel. Seda korratakse, kuni kõik komponendid on massiivi algusest peale korras. Me teame, et kui me suudame kogu iteratsiooni teha ilma vahetustehinguteta, olid kõik üksused nende külgnevate elementidega võrreldes soovitavas järjekorras ja laiemalt kogu massiiv. Mullide sortimise algoritmi põhjuseks on see, et numbrid nagu "mullid üles" maapinnale. Kui pärast konkreetset summat käiate uuesti esinemisjuhu läbi (4 on hea näide), märkate, et arv aeglaselt liigub paremale.

Mullide sortimise sammud on järgmised:

1. 4 2 1 5 3: Siin pole kaks esimest numbrit õiges järjekorras, seega peame mõlemad numbrid järjestama.
2. 2 4 1 5 3: Pärast seda pole järgmine numbripaar ka õiges järjekorras. Nii et sortimine toimub uuesti.
3. 2 1 4 5 3: Need kaks on õiges järjekorras, 4 <5, seega pole neid vaja vahetada.
4. 2 1 4 5 3 : Jälle peame vahetama korraliku korra vastu.
5. 2 1 4 3 5: siin on massiiv pärast ühte iteratsiooni.
6. Peame seda protseduuri uuesti kordama, kuni numbrid on õiges järjekorras.

Kood:

public class BubbleSortExample (
public static void bubbleSort(int() arr) (
int n = arr.length;
int tmp = 0;
for(int x=0; x < n; x++)(
for(int y=1; y < (nx); y++)(
if(arr(y-1) > arr(y))(
//swap elements
tmp = arr(y-1);
arr(y-1) = arr(y);
arr(y) = tmp;
)
)
)
)
public static void main(String() args) (
int arr() =(4, 2, 1, 5, 3);
System.out.println("Array Before Bubble Sort");
for(int x=0; x < arr.length; x++)(
System.out.print(arr(x) + " ");
)
System.out.println();
bubbleSort(arr);
System.out.println("Array After Bubble Sort");
for(int x=0; x < arr.length; x++)(
System.out.print(arr(x) + " ");
)
)
)

Väljund:

Märkus: see oleks võinud lõppeda lõpmatu ahelaga, kui ma kasutaksin a (i)> = a (i + 1), kuna see ühendus kehtib endiselt samaväärsete komponentidega ja vahetab need alati ühe elemendi vahel teise.

3. Valiku sortimine

Valik Sort jagab massiivi klasside massiivi, mida ei sorteerita. Seekord moodustatakse sorteerimisalarühm siis, kui sorteeritud massiivi lõppu sisestatakse sortimata alammassiivi minimaalne element, vahetades:

1. 3 5 1 2 4
2. 1 5 3 2 4
3. 1 2 3 5 4
4. 1 2 3 5 4
5. 1 2 3 4 5
6. 1 2 3 4 5

Kood:

public class SelectionSortEx (
public static void selectionSort(int() arr)(
for (int x = 0; x < arr.length - 1; x++)
(
int indx = x;
for (int y = x + 1; y < arr.length; y++)(
if (arr(y) < arr(indx))(
indx = y;
)
)
int smallNumber = arr(indx);
arr(indx) = arr(x);
arr(x) = smallNumber;
)
)
public static void main(String a())(
int() arr1 = (3, 5, 1, 2, 4);
System.out.println("Before Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
System.out.println();
selectionSort(arr1);
System.out.println("After Selection Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
)
)

Väljund:

Märkus . Massiivi suuruse jaoks on minimaalne O (n), kuna kõiki komponente tuleb kontrollida. Massiivi iga elemendi jaoks peame leidma minimaalse ja muutma kogu protsessi O (n 2) piiratuks.

4. Ühenda sortimine

Merge Sort kasutab rekursiooni, et fikseerida jagamise ja vallutamise meetodi küsimus tõhusamalt kui varem kirjeldatud algoritmid.

See puu näitab, kuidas rekursiivsed kõned toimivad. Allanoolega tähistatud massiivid on massiivid, mille jaoks me kutsume funktsiooni, samal ajal kui ülespoole nooli massiive ühendame. Siis järgite noolt puu servani ja naasete ja ühendate. Meil on vahemik 3 5 3 1, seega jaotame selle osadeks 3 5 4 ja 2 1. Jagame need sorteerimiseks nende osadeks. Alustame nende sulatamist ja sorteerimist, kui põhja jõuame.

Kood:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class MergeSort (
static void merge(int() array, int lowval, int midval, int highval)(
int x, y, k;
int() c= new int(highval-lowval+1);
k = 0;
x=lowval;
y=midval+1;
while(x<=midval && y<=highval)(
if(array(x)<=array(y))(
c(k++) = array(x++);
)
else(
c(k++) = array(y++);
)
)
while(x<=midval)(
c(k++) = array(x++);
)
while(y<=highval)(
c(k++) = array(y++);
)
k=0;
for(x = lowval; x<=highval; x++)(
array(x) = c(k++);
)
)
static void mergeSort(int() array, int lowval, int highval)(
if(highval-lowval+1>1)(
int midval = (lowval+highval)/2;
mergeSort(array, lowval, midval);
mergeSort(array, midval+1, highval);
merge(array, lowval, midval, highval);
)
)
public static void main(String() args) (
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
int size;
System.out.println("Enter the array");
try (
size = Integer.parseInt(r.readLine());
) catch (Exception e) (
System.out.println("Please Enter valid Input");
return;
)
int() array = new int(size);
System.out.println("Enter array elements");
int x;
for (x = 0; x < array.length; x++) (
try (
array(x) = Integer.parseInt(r.readLine());
) catch (Exception e) (
System.out.println("An error Occurred");
)
)
System.out.println("After Sorting");
System.out.println(Arrays.toString(array));
mergeSort(array, 0, array.length-1);
System.out.println("Before Merge Sorting");
System.out.println(Arrays.toString(array));
)
)

Selles programmis oleme palunud kasutajal sisestada sisend. Väljund järjestatud järjekorras põhineb kasutaja sisendil.

Väljund:

5. Hunniku sorteerimine

Kõigepealt peate teadma, millises raamistikus Heapsort töötab - kuhjaga - et mõista, miks see töötab. Räägime konkreetselt binaarsest hunnikust, kuid võite selle üldistada ka teistele hunnikute konstruktsioonidele. Hunnik on puu, mis täidab hunniku omadusi, st et kõigil selle lastel on suhted iga sõlmega. Ka hunnik peab olema peaaegu valmis. Peaaegu täielikul d-sügavusega binaaril on sama juurega alammenüü d-1 ja igal sõlmel on täielik vasak vasak osa, vasakule laskuv.

Teisisõnu, puu alt liikudes saate madalama ja madalama arvu (min-hunnik) või suurema ja suurema (max-hunniku) arvu. Siin on maksimaalne hunnik:

1. 6 1 8 3 5 2 4 : Siin on mõlema laste arv väiksem kui vanemal, seega ei pea me midagi muutma.
2. 6 1 8 3 5 2 4: siin, 5> 1, peame need vahetama. Peame 5 kohta heapifi.
3. 6 5 8 3 1 2 4: Mõlemad lastenumbrid on väiksemad, kõik jäävad samaks.
4. 6 5 8 3 1 2 4: siin 8> 6, seega peaksime neid vahetama.
5. 8 5 6 3 1 2 4: Pärast iteratsiooni saame selle tulemuse.

Pärast selle protsessi uuesti kordamist saame järgmised tulemused:

• 8 5 6 3 1 2 4

1. 4 5 6 3 1 2 8 : Vahetus
2. 6 5 4 3 1 2 8 : tehke kõrini
3. 2 5 4 3 1 6 8 : Vahetus
4. 5 2 4 2 1 6 8 : tehke kõrini
5. 1 2 4 2 5 6 8 : Vahetus

Kood:

public class HeapSort
(
public void sort(int arr())
(
int n = arr.length;
for (int x = n / 2 - 1; x >= 0; x--)
heapify(arr, n, x);
for (int x=n-1; x>=0; x--)
int tmp = arr(0);
arr(0) = arr(x);
arr(x) = tmp;
heapify(arr, x, 0);
)
)
void heapify(int arr(), int n, int x)
(
int largest = x;
int L = 2*x + 1;
int r = 2*x + 2;
if (L arr(largest))
largest = L;
if (r arr(largest))
largest = r;
if (largest != x)
(
int swap = arr(x);
arr(x) = arr(largest);
arr(largest) = swap;
heapify(arr, n, largest);
)
)
static void printArray(int arr())
(
int n = arr.length;
for (int x=0; x System.out.print(arr(x)+" ");
System.out.println();
)
public static void main(String args())
(
int arr() = (6, 1, 8, 3, 5, 2, 4);
int n = arr.length;
System.out.println("Before Sorting:");
printArray(arr);
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("After Heap Sorting:");
printArray(arr);
)
) public class HeapSort
(
public void sort(int arr())
(
int n = arr.length;
for (int x = n / 2 - 1; x >= 0; x--)
heapify(arr, n, x);
for (int x=n-1; x>=0; x--)
int tmp = arr(0);
arr(0) = arr(x);
arr(x) = tmp;
heapify(arr, x, 0);
)
)
void heapify(int arr(), int n, int x)
(
int largest = x;
int L = 2*x + 1;
int r = 2*x + 2;
if (L arr(largest))
largest = L;
if (r arr(largest))
largest = r;
if (largest != x)
(
int swap = arr(x);
arr(x) = arr(largest);
arr(largest) = swap;
heapify(arr, n, largest);
)
)
static void printArray(int arr())
(
int n = arr.length;
for (int x=0; x System.out.print(arr(x)+" ");
System.out.println();
)
public static void main(String args())
(
int arr() = (6, 1, 8, 3, 5, 2, 4);
int n = arr.length;
System.out.println("Before Sorting:");
printArray(arr);
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("After Heap Sorting:");
printArray(arr);
)
)

Väljund:

Saate seda vaadata graafiku punktist teise, vasakult paremale. Siin saavutasime selle, et kui massiivis on k-komponent, on selle laste positsioon 2 \ * k + 1 ja 2 \ * k + 2 (eeldusel, et indekseerimine algab 0-st). Seda saate teie ise jälgida. V-i positsioon on k-komponendi korral alati (k-1) / 2. Saate hõlpsasti mis tahes vahemikku "hunniku üles tõsta", sest teate seda. Kontrollige, kas üks selle lastest on madalam kui iga komponendi oma. Kui jah, siis paarista üks vanem ja korda seda sammu vanemaga rekursiivselt.

Märkus: kuna silmuste kordamine kogu massiivi korral muudab heapSorti (ilmselt O (N)), tekitaks see Heapsort O üldise keerukuse (nlog n). Heapsortil on kohapealne tüüp, mis tähendab, et see nõuab O ( 1) rohkem ruumi kui Merge Sort, kuid sellel on mõned puudused, näiteks rasked paralleelid.

Järeldus - algoritmide sortimine Java-s

Sorteerimine on väga levinud protseduur andmekogumitega, olgu selleks siis edasine analüüs, kiirendatud otsing kiirendatud sorteeritud teabele tuginevate tõhusamate algoritmidega, teabe filtreerimine jne. Sorteerimist toetavad mitmed keeled ja sageli varjavad liidesed seda, mida programmeerija teeb.

Soovitatavad artiklid

See on juhend Java algoritmide sortimiseks. Siin käsitleme Java-s eri tüüpi sorteerimist koos nende algoritmidega. Võite vaadata ka meie teisi soovitatud artikleid -

1. Ühenda sortimisalgoritmid Java-s
2. JComboBox Java-s
3. StringBuffer Java-s
4. JTextField Java
5. Hunnik sorteerimine Pythonis
6. Kiire sortimise algoritmid Java-s
7. Täielik juhend C # -s sortimise kohta koos näidetega
8. Algoritmide sortimine JavaScriptis
9. C ++ algoritmi näidete juhend
10. Täielik juhend algoritmide sortimise kohta Pythonis