Come implementare QuickSort in Java?



Questo articolo ti presenterà un altro algoritmo di ordinamento Divide And Conquer che è QuickSort in Java e seguirà una dimostrazione.

QuickSort è un algoritmo divide et impera. Nel paradigma di progettazione dell'algoritmo Divide & Conquer, dividiamo i problemi in sotto-problemi in modo ricorsivo, quindi risolviamo i sotto-problemi e infine combiniamo le soluzioni per trovare il risultato finale. In questo articolo ci concentreremo su QuickSort In

I seguenti suggerimenti saranno trattati in questo articolo,





Cominciamo!

Una cosa da tenere a mente quando si dividono i problemi in sotto-problemi è che la struttura dei sotto-problemi non cambia a partire dal problema originale.
L'algoritmo di Divide & Conquer ha 3 passaggi:



  • Dividi: spezza il problema in sottoproblemi
  • Conquistare: risolvere ricorsivamente i sottoproblemi
  • Combina: Combina le soluzioni per ottenere il risultato finale

Immagine- Ordinamento rapido in Java- Edureka

Esistono vari algoritmi basati sul paradigma divide et impera. Ordinamento rapido e ordinamento unisci sono tra questi.

Sebbene la complessità temporale nel caso peggiore di QuickSort sia O (n2) che è più di molti altri algoritmi di ordinamento come Merge Sort e Heap Sort, QuickSort è più veloce nella pratica, perché il suo ciclo interno può essere implementato in modo efficiente sulla maggior parte delle dati del mondo reale.



tableau che unisce due origini dati

Parliamo dell'implementazione dell'algoritmo di ordinamento rapido. Gli algoritmi Quicksort prendono un elemento pivot e partizionano l'array attorno all'elemento pivot. Esistono numerose varianti di Quicksot che dipendono da come scegli l'elemento pivot. Esistono diversi modi per scegliere l'elemento pivot:

  • Scegliere il primo elemento
  • Scegli l'ultimo elemento
  • Scegliere un elemento casuale
  • Picking elemento mediano

La prossima cosa importante da capire è la funzione partition () nell'algoritmo di ordinamento rapido. Funzione di partizione per prendere un elemento pivot, posizionarlo nella posizione giusta, spostare tutti gli elementi più piccoli dell'elemento pivot alla sua sinistra e tutti gli elementi maggiori alla sua destra. Quicksort richiede tempo lineare per farlo.
Quindi l'array viene diviso in due parti dall'elemento pivot (cioè elementi minori di pivot ed elementi maggiori di pivot) ed entrambi gli array vengono ordinati ricorsivamente utilizzando l'algoritmo Quicksort.

Ora che abbiamo capito il funzionamento dell'algoritmo QuickSort. Vediamo come implementare l'algoritmo Quicksort in Java.

QuickSort Funzione:

/ * La funzione Quicksort richiede che l'array sia ordinato con l'indice più basso e più alto * /

void sort (int arr [], int lowIndex, int highIndex) {// Fino a lowIndex = highIndex if (lowIndex

Ora diamo un'occhiata al codice di partizionamento per capire come funziona.

sovraccarico di funzioni c ++

Partizione Codice

Nel codice di partizionamento, sceglieremo l'ultimo elemento come elemento pivot. Attraversiamo l'array completo (cioè usando la variabile j nel nostro caso). Teniamo traccia dell'ultimo elemento più piccolo dell'array (cioè usando la variabile i nel nostro caso). Se troviamo un elemento più piccolo del pivot, spostiamo scambia l'elemento corrente a [j] con arr [i], altrimenti continuiamo a traversare.

int partition (int arr [], int lowIndex, int highIndex) {// Rendere l'ultimo elemento come pivot int pivot = arr [highIndex] // Usare i per tenere traccia degli elementi più piccoli da pivot int i = (lowIndex-1) for (int j = lowIndex j

Ora che hai compreso Quicksort e la funzione di partizione, diamo una rapida occhiata al codice completo

QuickSort Codice Java

class QuickSort {// Metodo partizione int partition (int arr [], int lowIndex, int highIndex) {int pivot = arr [highIndex] int i = (lowIndex-1) for (int j = lowIndex j

// Metodo di ordinamento

void sort (int arr [], int lowIndex, int highIndex) {if (lowIndex

// Metodo per stampare array

static void printArray (int arr []) {int n = arr.length for (int i = 0 i

// Metodo principale

public static void main (String args []) {int arr [] = {101, 37, 68, 29, 11, 5} int n = arr.length QuickSort ob = new QuickSort () ob.sort (arr, 0, n-1) System.out.println ('array ordinato') printArray (arr)}}

Produzione:

Output- Ordinamento rapido in Java- Edureka

Ora dopo aver eseguito il programma Java di cui sopra, avresti capito come funziona QuickSort e come implementarlo in Java.Così siamo giunti alla fine di questo articolo su 'Quicksort in Java'. Se desideri saperne di più,controlla il da Edureka, una società di apprendimento online affidabile. Il corso di formazione e certificazione Java J2EE e SOA di Edureka è progettato per formarti sia sui concetti di base che avanzati su Java insieme a vari framework Java come Hibernate e Spring.

Hai domande per noi? Per favore, menzionalo nella sezione commenti di questo blog e ti risponderemo il prima possibile.