Bevezetés a Java gyors rendezési algoritmusaiba

A gyors rendezés a java-ban, partíciócserélő rendezésként is ismert, egy osztó és hódító rendezési algoritmus. A gyors rendezés jó példa egy olyan algoritmusra, amely a felosztás és a hódító jellege miatt a CPU gyorsítótárakat használja a legjobban. A Quicksort algoritmus az egyik leggyakrabban használt rendezési algoritmus, különösen a nagy listák rendezéséhez, és a legtöbb programozási nyelv megvalósította. A Quicksort algoritmusban az eredeti adatokat két részre osztják, amelyeket külön-külön osztályoznak, majd egyesítenek, hogy rendezett adatokat állítsanak elő.

Tegyük figyelembe, hogy a (8, 6, 3, 4, 9, 2, 1, 7) tömböt a Gyors rendezés segítségével kell rendezni.

A gyors rendezési algoritmusok végrehajtásának lépései

1. Válasszon egy pivot nevű elemet a tömbből. Általában a középső elemet választják meg a csuklót. Vegyük a 4-et fordítóként.

2. Helyezze el a tömböt két részre úgy, hogy a forgóeszköznél kevesebb elem kerüljön el a forgócsavarra, és a forgóeszköznél nagyobb elemek jelenjenek meg a forgóeszköz után. A következő lépéseket követjük:

  • Válasszuk ki a bal szélső elemet, azaz 8-at, mivel 4 a forgócsavar és 8 nagyobb, mint 4, a 8-at jobbra kell mozgatni 4-től. Jobb oldalon hagyjuk a 7-et, mivel ez nagyobb, mint 4, és válasszuk az 1-et az átváltáshoz. 8-val tehát a csere után a tömb így lesz: 1, 6, 3, 4, 9, 2, 8, 7
  • Válasszuk ki a következő bal elemet, azaz 6-at, mivel 4 a forgócsavar és 6 nagyobb, mint 4, a 6-at jobbra kell mozgatni 4-től. Jobb oldalon hagyjuk a 7, 8-at, mivel ezek nagyobb, mint 4, és válasszuk A 2-es szám a 6-os cseréhez, tehát a tömb cseréje után 1, 2, 3, 4, 9, 6, 8, 7 lesz
  • Mivel az összes forgótest bal oldalán lévő elem kevesebb, mint a forgókar, és az összes forgó elem jobb oldalán nagyobb, mint a forgó elem, ezért a 4-rel végezzük el a forgatást.

3. Rekurzív módon hajtsa végre az 1. és a 2. lépést a bal al-tömbre (tömb, ahol az elemek kevesebb, mint a pivot) és a jobb oldali tömbre (tömb, ahol az elemek több, mint a pivot). Ha a tömb csak egy vagy nulla elemet tartalmaz, akkor a tömb válogatottnak tekinthető.

Program gyors rendezési algoritmusok végrehajtására

Itt van egy java program, amelynek segítségével egész számot rendezhetünk gyors rendezési algoritmus segítségével.

Kód:

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

Kimenet:

A gyors rendezési algoritmusok előnyei

A gyors rendezési algoritmus előnyei a következők:

  • Kiváló referencia-helyszín: A referencia-helység a processzor azon képessége, hogy rövid idő alatt ismételten hozzáférjen ugyanahhoz a memóriahelyhez. A gyors java szerinti rendezés kiváló referenciahelyet biztosít a gyorsítótár hiánya miatt, ami a modern architektúrákban kritikus a teljesítmény szempontjából.
  • A Gyors rendezés párhuzamosítható: Miután befejezte a tömb kisebb régiókba osztásának első lépését, az egyes al-alcsoportok egymástól függetlenül sorolhatók párhuzamosan. Ezért a gyors rendezés jobban teljesít.

A gyors rendezés komplexitása

A Quicksort gyors és farok-rekurzív algoritmus, amely az osztás és meghódítás elvén működik. Itt van a komplexitása elemzése a legjobb, az átlagos és a legrosszabb esetben:

  • A legjobb eset komplexitása: Ha egy tömb vagy lista n elemet tartalmaz, akkor az első futtatáshoz O (n) -re lesz szükség. Most a fennmaradó két al-minta rendezése 2 * O (n / 2) -t vesz igénybe. Ez a legjobb esetben zárja le az O (n logn) összetettségét.
  • Az esetek átlagos komplexitása: A gyorsmenü átlagos száma O (n log n).
  • A legrosszabb eset komplexitása: Az első vagy az utolsó kiválasztása a legrosszabb esetek teljesítményét okozza majdnem rendezett vagy csaknem fordítottan rendezett adatok esetén. A gyors rendezés a legrosszabb esetben O (n 2) teljesítményt hajt végre.

Java-ban, Arrays. A Sort () módszer egy gyors rendezési algoritmust használ egy tömb rendezéséhez.

Ajánlott cikkek

Ez egy útmutató a Java gyors rendezési algoritmusaihoz. Itt tárgyaljuk a gyors válogatási algoritmus Java alkalmazásban megvalósításának lépéseit, előnyeit és komplexitásának elemzését a programmal együtt. A következő cikkeket is megnézheti további információkért -

  1. Beszúrás Rendezés Java-ban
  2. megszakítási hurok a Java-ban
  3. JComponent Java-ban
  4. Négyzetek a Java-ban
  5. Csere a PHP-ben
  6. Rendezés C # -ben
  7. Rendezés Pythonban
  8. C ++ algoritmus | Példák a C ++ algoritmusra

Kategória: