Quicksort in QBasic

Quicksort in QBasic è un modo intelligente di mettere in ordine un gruppo di numeri. È come organizzare i libri sulla tua mensola in base alla grandezza da più piccolo a più grande. In QBasic, un programma scrive un codice che fa questo in modo automatico.

Immagina di avere dieci numeri in una lista, un po’ come avere dieci libri in disordine. Quicksort organizza questi numeri in modo crescente, dal più piccolo al più grande. Fa ciò dividendo la lista in gruppi più piccoli e organizzandoli uno alla volta.

Il cuore del programma è la parte chiamata Quicksort. Questa parte del codice divide la lista, organizzando i numeri più piccoli e più grandi rispetto a un numero scelto. Chiamiamo questo numero il “punto centrale” o “pivot”. Poi, ripete lo stesso processo per i gruppi più piccoli fino a quando tutti i numeri sono ordinati.

Il programma principale genera casualmente dieci numeri e li mette nella lista. Prima dell’organizzazione, mostra questi numeri sullo schermo in modo che tu possa vederli. Poi, il Quicksort fa la sua magia, ordinando la lista e mostrandoti i numeri in ordine crescente.

È interessante notare come anche se QBasic non è un linguaggio di programmazione moderno, può ancora fare cose sorprendenti come organizzare liste di numeri in modo rapido ed efficiente. Questo ci insegna che anche con strumenti più vecchi, possiamo risolvere problemi complicati.

DIM SHARED arr(10)

REM Dichiarazione della funzione Partition
FUNCTION Partition(arr(), low, high)
    REM Scegli il pivot
    pivot = arr(high)
    
    REM Indice dell'elemento più piccolo
    i = low - 1
    
    REM Scorri l'array
    FOR j = low TO high - 1
        IF arr(j) <= pivot THEN
            REM Incrementa l'indice dell'elemento più piccolo
            i = i + 1
            
            REM Scambia arr(i) e arr(j)
            SWAP arr(i), arr(j)
        END IF
    NEXT j
    
    REM Scambia arr(i + 1) e il pivot
    SWAP arr(i + 1), arr(high)
    
    REM Restituisci l'indice del pivot
    Partition = i + 1
END FUNCTION

REM Sottoprocedura Quicksort
SUB Quicksort(arr(), low, high)
    IF low < high THEN
        REM Partiziona l'array
        pivotIndex = Partition(arr, low, high)
        
        REM Ordina le due metà
        Quicksort arr(), low, pivotIndex - 1
        Quicksort arr(), pivotIndex + 1, high
    END IF
END SUB

REM Programma principale per testare Quicksort
RANDOMIZE TIMER

REM Riempi l'array con valori casuali
FOR i = 1 TO 10
    arr(i) = INT(RND * 100)
NEXT i

REM Mostra l'array prima dell'ordinamento
PRINT "Array prima di Quicksort:"
FOR i = 1 TO 10
    PRINT arr(i);
NEXT i

REM Chiamare Quicksort per ordinare l'array
Quicksort arr(), 1, 10

REM Mostra l'array dopo l'ordinamento
PRINT
PRINT "Array dopo Quicksort:"
FOR i = 1 TO 10
    PRINT arr(i);
NEXT i