8 : I dati e la loro struttura nella programmazione ( ARRAY , MATRICI , RECORD ) Vers . 8.3 – Febbraio 2024
B ) Algoritmo di ordinamentoBUBBLE-SORT o “ A BOLLE ”
Viene utilizzato nella realtà solo per dati “ poco disordinati ” e consiste nel confrontare a 2 a 2 gli elementi , scambiandoli se necessario ( ossia primo e secondo , secondo e terzo , terzo e quarto , …, penultimo ed ultimo ), facendo risalire ( ecco il concetto di “ bolla ”) verso l ’ alto ( indice più grande ) attraverso questa ripetizione di scambi , gli elementi più grandi in caso di ordinamento crescente o più piccoli in caso di ordinamento decrescente .
Per descrrivere l ’ algoritmo di ordinamento BUBBLE-SORT quindi dovremmo utilizzare anche :
• una variabile booleana che ci indichi che nella scansione non sono avvenuti scambi di valori tra elementi ( chiamiamo questa variabile continua );
• una variabile intera che ci indichi il limite superiore ( ossia l ’ indice dell ’ elemento ) fino al quale fare gli scambi per evitare ripetizioni inefficienti ( chiamiamola sup ) che viene inizializzata la prima volta con la dimensione del vettore e che assumerà valori via via decrescenti , fino a che il vettore non risulterà ordinato ;
• una variabile intera ( chiamiamola k ) che dopo l ’ esecuzione di ogni “ scansione ” indichi la posizione del nuovo estremo superiore da considerare .
TABELLE DEI DATI DATI DI INPUT DEL PROBLEMA PRINCIPALE ( PROCEDURA MAIN )
Nome variabile Tipo dati Tipo Allocazione Valori ammessi Descrizione v
ARRAY [ MAXDIM ] DI INT
STATICA
n INT STATICA
TUTTI
1 ≤ n ≤ MAXDIM ossia ( n ≥ 1 ) AND ( n ≤ MAXDIM )
Vettore o array di interi da acquisire da tastiera
Dimensione effettiva del vettore immesso da tastiera
DATI DI OUTPUT DEL PROBLEMA PRINCIPALE ( PROCEDURA MAIN ) Nome variabile Tipo dati Tipo Allocazione Valori ammessi Descrizione v
ARRAY [ MAXDIM ] DI INT
STATICA TUTTI
Vettore o array di interi da visualizzare a video
DATI DI ELABORAZIONE o DI LAVORO DEL PROBLEMA PRINCIPALE ( PROCEDURA MAIN )
Nome variabile oppure nome costante
Tipo dati Tipo Allocazione Valori ammessi Descrizione
MAXDIM INT STATICA 10 i INT STATICA
1 ≤ i ≤ n + 1 ossia ( i ≥ 1 ) AND ( i ≤ n + 1 )
scambio INT STATICA TUTTI
sup INT STATICA k INT STATICA
1 ≤ sup ≤ n ossia ( sup ≥ 1 ) AND ( sup ≤ n ) 1 ≤ k ≤ n ossia ( k ≥ 1 ) AND ( k ≤ n )
continua BOOL STATICA VERO o FALSO
Massimo numero di elementi gestibile dal vettore monodimensionale Indice per poter accedere agli elementi del vettore v ed effettuare le scansioni Variabile che permette lo scambio di valori del vettore per ciascuna scansione Indice dell ’ ultimo elemento del vettore da considerare per gli scambi Indice dell ’ ultimo elemento del vettore che è stato scambiato ( il nuovo sup ) Variabile che indica se nella scnsione sono avvenuti scambi
Autore : Rio Chierego ( email : riochierego @ libero . it - sito web : www . riochierego . it ) Pag . 17