Algoritmusok rendezése Java-ban Különböző típusú rendezési algoritmusok a Java-ban

• Bevezetés a Java algoritmusok rendezésébe

Bevezetés a Java algoritmusok rendezésébe

Az információk bizonyos sorrendbe történő rendezése, gyakran tömbszerű keretek között, az az, hogy azokat rendezzük. Használhat különféle sorrendi követelményeket, népszerűek a számok osztályozása a legkisebbtől a legnagyobbig vagy fordítva, vagy lexikográfiai sorrend. Különböző algoritmusokat fedünk le, a hatástalan, de intuitív alternatíváktól kezdve a hatékony algoritmusokig, amelyeket hatékonyan telepítünk a Java-ban és más nyelveken, ha érdekli a rendezés működése.

Különböző rendezési algoritmusok a java-ban

Különböző rendezési algoritmusok léteznek, és nem mindegyik egyformán hatékony. Annak érdekében, hogy összehasonlítsuk őket, és megtudjuk, melyik teljesít a legjobban, elemezzük az idő összetettségét.

1. Beszúrás Rendezés
2. Bubble Sort
3. Kiválasztás Rendezés
4. Merge Sort
5. kupacrendezés

1. Beszúrás rendezése

A beszúrási sorrend mögött meghúzódó ötlet megosztja a tartományt a válogatott és válogatás nélküli alcsoportokra. Az osztályozott rész az 1. időtartam kezdetén áll, és megegyezik a tömb első (bal oldali) alkotóelemével. A tömbön áthaladunk, és a tömb osztályozott részét minden egyes iteráció során egy összetevővel kibővítjük. Bővítéskor a friss elemet a rendezett al-tömbbe helyezzük. Ezt úgy hajtjuk végre, hogy az elemeket jobbra toljuk, amíg meg nem találjuk, hogy az első összetevőt nem kell megváltoztatnunk. Ha a vastag rész növekvő sorrendben van rendezve, például a következő tömbben, akkor ez történik:

1. 3 5 7 8 4 2 1 9 6: Fontolja meg a 4-et, és ehhez kell beilleszteni. 8 és 4 óta váltunk
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

Kód:

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+" ");
)
)
)

Kimenet:

Ezt a módszert követve az egyik elem kiterjesztette a rendezett részt, négy elem helyett öt van. Minden iteráció ezt megteszi, és a teljes tömb a végére lesz rendezve.

Megjegyzés: Ennek oka az, hogy a teljes besorolt ​​listát egyenként kell átvinni minden iterációban, azaz O (n). Az egyes táblázatok mindegyik alkotóelemére ezt meg kell tennünk, ami azt jelenti, hogy O (n 2) korlátozott.2.

2. Bubble Sort

Ha a buborék nincs a kívánt sorrendben, akkor a szomszédos alkatrészek cseréjével működik. Ezt addig ismételjük, amíg az összes elem a tömb elejétől nem lesz rendben. Tudjuk, hogy ha a teljes iterációt csere nélkül hajtjuk végre, akkor az összes elem a szomszédos elemekkel összehasonlítva a kívánt sorrendben volt, és kiterjesztve a teljes tömböt. A Bubble Sort algoritmus oka az, hogy a számok, például „felbukkannak” a „földbe”. Ha egy adott összeg után újra megismétli a példányt (4 egy jó példány), akkor észreveszi, hogy a szám lassan jobbra mozog.

A buborék rendezésének lépései a következők:

1. 4 2 1 5 3: Itt az első két szám nincs megfelelő sorrendben, ezért mind a számokat el kell rendeznünk.
2. 2 4 1 5 3: Ezt követően a következő számpár szintén nincs megfelelő sorrendben. Tehát a válogatás megismétlődik.
3. 2 1 4 5 3: Ez a kettő a megfelelő sorrendben van, 4 <5, tehát nincs szükség kicserélésre.
4. 2 1 4 5 3 : Meg kell cserélnünk a megfelelő rendelést.
5. 2 1 4 3 5: Íme a kapott tömb egy iteráció után.
6. Ezt a folyamatot meg kell ismételnünk mindaddig, amíg a számok rendben vannak.

Kód:

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) + " ");
)
)
)

Kimenet:

Megjegyzés: Lehetséges, hogy végtelen hurokba került, ha a (i)> = a (i + 1) -et használtam, mert ez a kapcsolat továbbra is érvényes az egyenértékű komponensekkel, és így mindig cserélje őket egyik elemről a másikra.

3. Kiválasztás Rendezés

A Kijelölés rendezése a tömböt osztályozási tömbre osztja, amely nincs rendezve. Ezúttal azonban a szortírozási al-tömb úgy kerül kialakításra, hogy a rendezett tömb végére beillesztjük a válogatott alcsoport többlet elemét, cserélve:

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

Kód:

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+" ");
)
)
)

Kimenet:

Megjegyzés: A tömb méretének legalább O (n) kell lennie, mivel az összes komponenst ellenőrizni kell. A tömb minden elemére meg kell találni a minimumot, és az egész folyamatot O (n 2) korlátozni kell.

4. Rendezés egyesítése

A Merge Sort a rekurziót használja a split és conquest módszer kérdésének hatékonyabb javításához, mint a korábban leírt algoritmusok.

Ez a fa megmutatja, hogyan működnek a rekurzív hívások. A lefelé mutató nyíllal jelölt tömbök azok a tömbök, amelyekre funkciókat hívunk, miközben felfelé mutató nyíl tömböket biztosítunk. Ezután kövesse a nyílot a fa széléhez, majd térjen vissza és egyesüljön. Megvan a 3 5 3 1 tartomány, tehát felosztjuk 3 5 4 és 2 1-re. Osztjuk őket részükre, hogy osztályozzuk őket. Megkezdjük a fúziót és a válogatást, amint megyünk, amikor az aljára jutunk.

Kód:

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));
)
)

Ebben a programban arra kértük a felhasználót, hogy írja be az inputot. A kimenet a felhasználó bemenete alapján rendezett sorrendben lesz.

Kimenet:

5. Halomfajta

Először ismernie kell azt a keretet, amelyen a Heapsort működik - a halomot -, hogy megértse, miért működik. Kifejezetten egy bináris halomról fogunk beszélni, de ezt általánosíthatjuk más halom konstrukciókra is. A halom egy fa, amely teljesíti a halom tulajdonságát, azaz hogy minden gyermeke kapcsolatban áll minden csomóponttal. A halomnak szintén majdnem késznek kell lennie. A csaknem teljes d mélységű binárisnak d-1 részfája van, ugyanazzal a gyökérrel, és minden csomópontnak van egy teljes, bal alfája, balra csökkenő.

Más szavakkal: egy alacsonyabb és alacsonyabb számot (min-halom), vagy nagyobbat és nagyobbot (max-halom) kapsz, amikor a fa alatt mozog. Itt van egy max-halom példány:

1. 6 1 8 3 5 2 4 : Itt mindkét gyermek száma kisebb, mint a szülő, tehát nem kell semmit megváltoztatnunk.
2. 6 1 8 3 5 2 4: Itt, 5> 1, ki kell cserélnünk őket. 5-re kell heapitálnunk.
3. 6 5 8 3 1 2 4: Mindkét gyermek száma kisebb, minden változatlan marad.
4. 6 5 8 3 1 2 4: Itt a 8> 6, ezért ki kellene cserélnünk őket.
5. 8 5 6 3 1 2 4: Az iteráció után megkapjuk ezt az eredményt.

A folyamat újbóli megismétlése után a következő eredményeket kapjuk:

• 8 5 6 3 1 2 4

1. 4 5 6 3 1 2 8 : Csere
2. 6 5 4 3 1 2 8 : Heapify
3. 2 5 4 3 1 6 8 : Csere
4. 5 2 4 2 1 6 8 : Heapify
5. 1 2 4 2 5 6 8 : Csere

Kód:

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);
)
)

Kimenet:

Megnézheti a grafikon pontról szintjére, balról jobbra. Itt értük el, hogy ha a tömbben a k-os komponens van, annak gyermekeinek pozíciója 2 \ * k + 1 és 2 \ * k + 2 (feltételezve, hogy az indexálás 0-tól kezdődik). Ezt Ön felügyelheti. A szülő helyzete mindig (k-1) / 2 a k-os komponensnél. Bármilyen tartományt könnyen „felhalmozhat”, mert ezt tudja. Ellenőrizze, hogy az egyik gyermeke alacsonyabb-e, mint az egyes alkatrészek. Ha igen, párosítson egy szülőt, és ismételje meg ezt a lépést a szülővel.

Megjegyzés: Mivel a hurkok iterálása a teljes tömbön heapSortot eredményez (nyilvánvalóan O (N)), ez létrehozza a Heapsort O általános bonyolultságát (nlog n). A Heapsort helyszíni típusú, ami azt jelenti, hogy O ( 1) több hely, mint a Merge Sort, de van néhány hátránya, például nehéz párhuzamok.

Következtetés - Algoritmusok rendezése Java-ban

A szortírozás nagyon elterjedt eljárás adatkészletekkel, akár további elemzés céljából, akár gyorsabb keresés révén, a rendezett információra támaszkodó hatékonyabb algoritmusokkal, az információk szűrésével stb. A rendezést több nyelv támogatja, és az interfészek gyakran eltakarják a programozó által végzett tevékenységeket.

Ajánlott cikkek

Ez az útmutató az Algoritmusok rendezése a Java-ban. Itt tárgyaljuk a Java szerinti rendezés különféle típusait és algoritmusaikat. Megnézheti más javasolt cikkeinket -

1. Egyesítési rendezési algoritmusok a Java-ban
2. JComboBox Java
3. StringBuffer Java-ban
4. JTextField Java
5. Halom Rendezés Pythonban
6. Gyors rendezési algoritmusok a Java-ban
7. Teljes útmutató a C # szerinti rendezéshez, példákkal
8. Algoritmusok rendezése a JavaScript-ben
9. Útmutató a C ++ algoritmus példáira
10. Teljes útmutató az algoritmusok rendezéséhez Pythonban