Introduksjon til hurtig sorteringsalgoritmer i Java

Rask sortering i java, også kjent som partisjon-byttesortering, er en splitt og erobre sorteringsalgoritme. Rask sortering er et godt eksempel på en algoritme som gjør best mulig bruk av CPU-cacher på grunn av splittelse og erobrer natur. Quicksort-algoritmen er en av de mest brukte sorteringsalgoritmene, spesielt for å sortere de store listene, og de fleste programmeringsspråk har implementert den. I Quicksort-algoritmen er de opprinnelige dataene delt inn i to deler som blir individuelt sortert og deretter slått sammen for å produsere sorterte data.

La oss vurdere at matrisen (8, 6, 3, 4, 9, 2, 1, 7) må sorteres ved hjelp av Quick Sort.

Trinn for å implementere hurtigsorteringsalgoritmer

1. Velg et element som heter pivot fra matrisen. Generelt er det midtre elementet valgt som pivot. La oss ta 4 som sentralt.

2. Omorganiser matrisen i to deler slik at elementer mindre enn pivoten kommer før pivoten og elementer større enn pivoten vises etter pivotten. Følgende trinn følges:

  • Velg elementet til venstre, dvs. 8, siden 4 er pivoten og 8 er mer enn 4, må 8 flyttes til høyre for 4. På høyre side forlater vi 7 siden det er større enn 4 og velg 1 for å bytte med 8 derav etter bytte av array blir: 1, 6, 3, 4, 9, 2, 8, 7
  • Velg neste venstre element, dvs. 6, Siden 4 er pivoten og 6 er mer enn 4, må 6 flyttes til høyre for 4. På høyre side forlater vi 7, 8 siden de er større enn 4 og plukker 2 for å bytte med 6 derav etter bytte av array blir: 1, 2, 3, 4, 9, 6, 8, 7
  • Nå siden alle elementene til venstre for pivoten er mindre enn pivoten og alle elementene til høyre for pivoten er større enn pivoten, er vi ferdige med 4 som pivot.

3. Bruk trinn 1 og 2 rekursivt for den venstre undergruppen (matrise med elementer mindre enn pivoten) og for den høyre undergruppen (matrisen med elementer mer enn pivotten). Hvis matrisen bare inneholder ett eller null elementer, anses matrisen som assortert.

Program for å implementere hurtigsorteringsalgoritmer

Her er et java-program for å sortere en rekke heltall ved hjelp av en hurtigsorteringsalgoritme.

Kode:

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

Produksjon:

Fordeler med hurtigsorteringsalgoritmer

Følgende er fordelene med hurtigsorteringsalgoritmen:

  • Utmerket referanselokalitet: Referanselokaliteten er en prosessors evne til å få tilgang til samme minneplass repeterende over en kort periode. Rask sortering i java gir utmerket referanselokalitet på grunn av det svært få antallet cache-feil, som på moderne arkitekturer er avgjørende for ytelse.
  • Rask sortering er parallell: Når det første trinnet med å dele opp en gruppe i mindre regioner er fullført, kan alle de individuelle delområdene sorteres uavhengig parallelt. Av denne grunn gir rask sortering bedre.

Kompleksitetsanalyse av hurtig sortering

Quicksort er en rask og halerekursiv algoritme som fungerer etter skillet og erobre-prinsippet. Her er dens kompleksitetsanalyse i beste, gjennomsnittlige og verste tilfelle:

  • Beste sakskompleksitet: Hvis en matrise eller en liste inneholder n elementer, vil den første kjøringen trenge O (n). Nå tar sortering av de resterende to delområdene 2 * O (n / 2). Dette konkluderer i beste fall med kompleksiteten til O (n logn).
  • Gjennomsnittlig sakskompleksitet: Gjennomsnittlig tilfelle av hurtigsortering er O (n log n).
  • Worst Case Complexity: Hvis du velger først eller sist, vil det føre til dårligste resultater for nesten sorterte eller nesten omvendt sorterte data. Rask sortering utfører O (n 2) i verste fall.

I Java, Arrays. Sortering () -metoden bruker en hurtigsorteringsalgoritme for å sortere en matrise.

Anbefalte artikler

Dette er en guide til hurtig sorteringsalgoritmer i Java. Her diskuterer vi trinnene for å implementere, fordeler og kompleksitetsanalyse av en hurtig sorteringsalgoritme i java sammen med program. Du kan også se på følgende artikler for å lære mer -

  1. Innsettingssortering i Java
  2. gjør-mens-loop i Java
  3. JComponent i Java
  4. Firkanter i Java
  5. Bytt i PHP
  6. Sorterer i C #
  7. Sorterer i Python
  8. C ++ algoritme | Eksempler på C ++ algoritme

Kategori:

Programvare utvikling