Sissejuhatus Java kiirsorteerimise algoritmidesse

Kiire sortimine javas, tuntud ka kui partitsioonide vahetamise sort, on sortimisalgoritm jagamise ja vallutamise vahel. Kiire sorteerimine on hea näide algoritmist, mis kasutab CPU vahemälu kõige paremini ära, kuna see on jagatud ja vallutab olemuse. Quicksorti algoritm on üks enimkasutatavaid sortimisalgoritme, eriti suurte loendite sortimiseks ja enamik programmeerimiskeeli on selle rakendanud. Quicksorti algoritmis jagatakse algsed andmed kaheks osaks, mis sorteeritakse eraldi ja seejärel liidetakse, et saada sorteeritud andmed.

Mõelgem sellele, et massiiv (8, 6, 3, 4, 9, 2, 1, 7) tuleb sortida kiirkorraldusega.

Kiire sortimise algoritmide juurutamise sammud

1. Valige massiivist element, mida nimetatakse pöördepunktiks. Üldiselt valitakse pöördepunktiks keskmine element. Võtame pöördepunktiks 4.

2. Järjestage massiiv kaheks osaks nii, et vähem kui pöördealused elemendid asetseksid enne pöördepunkti ja teljest suuremad elemendid ilmuksid pärast pöördepunkti. Järgitakse järgmisi samme:

  • Valige vasakpoolseim element, st 8, kuna pöördepunkt on 4 ja 8 on suurem kui 4, 8 tuleb liikuda 4-st paremale. Parempoolsel küljel lahkume 7, kuna see on suurem kui 4, ja valige 1 vahetamiseks 8-ga saab massiivi vahetamise järel väärtuseks 1, 6, 3, 4, 9, 2, 8, 7
  • Valige järgmine vasak element, st 6, kuna pöördepunkt on 4 ja 6 on suurem kui 4, 6 tuleb liikuda 4-st paremale, paremal küljel jätame 7, 8, kuna need on suuremad kui 4, ja valige 2 saab 6-ga vahetamiseks, pärast massiivi vahetamist saab: 1, 2, 3, 4, 9, 6, 8, 7
  • Kuna kõik pöördepunktist vasakul olevad elemendid on vähem kui pöördtelg ja kõik pöördest paremal asuvad elemendid on pöördepunktist suuremad, siis tehakse 4-ga pöördus.

3. Rekursiivselt rakendage 1. ja 2. sammu vasaku alammassiivi (massiivi, mille elemente on vähem kui pöördepunkti) ja parema alammassiivi (massiivi, mille elemente on rohkem kui pöördepunkti) jaoks. Kui massiiv sisaldab ainult ühte või null elementi, loetakse massiivi assortii.

Programm kiire sortimisalgoritmide rakendamiseks

Siin on Java-programm täisarvude massiivi sortimiseks kiire sortimisalgoritmi abil.

Kood:

import java.lang.*;
import java.util.*;
public class Main (
private int array();
private int length;
public void sort(int() inputArrayArr) (
if (inputArrayArr == null || inputArrayArr.length == 0) (
return;
)
this.array = inputArrayArr;
length = inputArrayArr.length;
performQuickSort(0, length - 1);
)
private void performQuickSort(int lowerIndex, int higherIndex) (
int i = lowerIndex;
int j = higherIndex;
// calculate pivot number
// middle element taken as pivot
int pivot = array(lowerIndex+(higherIndex-lowerIndex)/2);
// Divide into two subarrays
while (i <= j) (
/**
* In each iteration, find an element from left side of the pivot which
* is greater than the pivot value, and also find an element
* From right side of the pivot which is less than the pivot value. Once the search
* is complete, we exchange both elements.
*/
while (array(i) < pivot) (
i++;
)
while (array(j) > pivot) (
j--;
)
if (i <= j) (
swapNumbers(i, j);
//move index to next position on both sides
i++;
j--;
)
)
// call performQuickSort() method recursively
if (lowerIndex < j)
performQuickSort(lowerIndex, j);
if (i < higherIndex)
performQuickSort(i, higherIndex);
)
private void swapNumbers(int i, int j) (
int temp = array(i);
array(i) = array(j);
array(j) = temp;
)
public static void main(String args())(
Main quickSort = new Main();
int() inputArray = (8, 6, 3, 4, 9, 2, 1, 7);
quickSort.sort(inputArray);
System.out.println("Sorted Array " + Arrays.toString(inputArray));
)
)

Väljund:

Kiire sortimise algoritmide eelised

Kiire sortimise algoritmi eelised on järgmised:

  • Suurepärane referentskoht: Viitekoht on protsessori võimalus pääseda korduvalt ja sama aja mälupesa juurde lühikese aja jooksul. Kiire sorteerimine javas pakub suurepärast viiteasukohta, kuna vahemälu on väga väike arv, mis tänapäevastes arhitektuurides on jõudluse jaoks kriitilise tähtsusega.
  • Kiire sortimine on paralleeliseeritav: kui massiivi väiksemateks piirkondadeks jaotamise algsed sammud on lõpule viidud, saab kõiki üksikuid alamkihte paralleelselt sortida. Sel põhjusel toimib kiire sortimine paremini.

Kiire sortimise keerukuse analüüs

Quicksort on kiire ja saba-rekursiivne algoritm, mis töötab jagamise ja vallutamise põhimõttel. Siin on selle keerukusanalüüs parimal, keskmisel ja halvimal juhul:

  • Parim juhtumi keerukus: kui massiiv või loend sisaldab n elementi, siis on esimesel käivitamisel vaja O (n). Nüüd võtab ülejäänud kahe alamkihi sortimine 2 * O (n / 2). See järeldab paremal juhul O (n logn) keerukust.
  • Juhtumite keskmine keerukus: kiirsortimise keskmine juhtum on O (n log n).
  • Halvim juhtumi keerukus: esimese või viimase valimine põhjustaks halvimal juhul peaaegu sorteeritud või peaaegu vastupidiselt sorteeritud andmete toimivuse. Kiire sorteerimine halvimal juhul täidab O (n 2).

Jaavas, massiivid. Sort () meetod kasutab massiivi sorteerimiseks kiiret sortimisalgoritmi.

Soovitatavad artiklid

See on Java Java kiire sortimise algoritmide juhend. Siin arutatakse javas koos programmiga kiire sortimisalgoritmi rakendamise eeliseid ja keerukusanalüüsi. Lisateabe saamiseks võite vaadata ka järgmisi artikleid -

  1. Sisestus Sorteeri Java
  2. Java-rakenduse silmus
  3. JComponent Java-s
  4. Ruudud Java-s
  5. Vahetamine PHP-s
  6. Sorteerimine C #
  7. Sorteerimine Pythonis
  8. C ++ algoritm | C ++ algoritmi näited

Kategooria:

Tarkvaraarendus