Chiesto:
Risposta:
Ecco un'implementazione dell'algoritmo Quicksort in linguaggio B4X:
Questa implementazione prende in input un array di interi A, l'indice sinistro Left e l'indice destro Right. L'algoritmo Quicksort è implementato come una subroutine ricorsiva.
L'algoritmo seleziona un elemento pivot dall'array (in questo caso l'ultimo elemento dell'array), quindi divide l'array in due parti: gli elementi più piccoli del pivot a sinistra e gli elementi più grandi del pivot a destra. Questo viene fatto utilizzando due indici i e j. L'indice i tiene traccia della posizione dell'ultimo elemento più piccolo del pivot trovato finora. L'indice j scorre attraverso l'array alla ricerca di elementi più piccoli o uguali al pivot. Quando viene trovato un elemento più piccolo o uguale al pivot, viene scambiato con l'elemento corrente indicato da i, che viene poi incrementato di uno.
Dopo aver completato la scansione dell'array, lo scambio finale viene effettuato tra il pivot e l'elemento successivo all'ultimo elemento più piccolo del pivot trovato.
Infine, la funzione Quicksort viene chiamata ricorsivamente per ordinare le due parti dell'array divise dal pivot.
Per utilizzare questa implementazione di Quicksort su un array di interi chiamato myArray, si può chiamare la subroutine come segue:
Questo ordinerà l'intero array in ordine crescente.
Perfetto
scrivi l'algoritmo quicksort in linguaggio B4X
Risposta:
Ecco un'implementazione dell'algoritmo Quicksort in linguaggio B4X:
B4X:
Sub QuickSort(A() As Int, Left As Int, Right As Int)
Dim i, j, pivot, temp As Int
If Left < Right Then
pivot = A(Right)
i = Left - 1
For j = Left To Right - 1
If A(j) <= pivot Then
i = i + 1
temp = A(i)
A(i) = A(j)
A(j) = temp
End If
Next
temp = A(i + 1)
A(i + 1) = A(Right)
A(Right) = temp
QuickSort(A, Left, i)
QuickSort(A, i + 2, Right)
End If
End SubQuesta implementazione prende in input un array di interi A, l'indice sinistro Left e l'indice destro Right. L'algoritmo Quicksort è implementato come una subroutine ricorsiva.
L'algoritmo seleziona un elemento pivot dall'array (in questo caso l'ultimo elemento dell'array), quindi divide l'array in due parti: gli elementi più piccoli del pivot a sinistra e gli elementi più grandi del pivot a destra. Questo viene fatto utilizzando due indici i e j. L'indice i tiene traccia della posizione dell'ultimo elemento più piccolo del pivot trovato finora. L'indice j scorre attraverso l'array alla ricerca di elementi più piccoli o uguali al pivot. Quando viene trovato un elemento più piccolo o uguale al pivot, viene scambiato con l'elemento corrente indicato da i, che viene poi incrementato di uno.
Dopo aver completato la scansione dell'array, lo scambio finale viene effettuato tra il pivot e l'elemento successivo all'ultimo elemento più piccolo del pivot trovato.
Infine, la funzione Quicksort viene chiamata ricorsivamente per ordinare le due parti dell'array divise dal pivot.
Per utilizzare questa implementazione di Quicksort su un array di interi chiamato myArray, si può chiamare la subroutine come segue:
B4X:
QuickSort(myArray(), 0, myArray.Length - 1)Perfetto
).
