Programma C per l'ordinamento delle bolle: Ordinamento delle bolle in C

introduzione

L'ordinamento di un array occupa un posto di immensa importanza nell'informatica. La sua utilità si nota quando è necessario disporre i dati in un ordine specifico. Esistono diversi tipi di algoritmi di ordinamento. L'algoritmo di ordinamento più comune e ampiamente utilizzato è il Bubble Sort.

Ordinamento a bolle in C

La tecnica utilizzata per l'ordinamento in Bubble sort è semplice e di facile comprensione. Tutto ciò che fa è confrontare l'elemento corrente con l'elemento successivo e scambiarlo se è maggiore o minore come dettato dalla condizione. L'algoritmo è molto preciso. Ogni volta che un elemento viene confrontato con altri elementi finché non viene trovata la sua posizione, viene chiamato passaggio.

Questo algoritmo è paragonabile alle bolle nell'acqua poiché filtra la parte superiore delle bolle simili a array. Tra tutti gli algoritmi utilizzati per l'ordinamento, Bubble sort è il più semplice e il più lento con una complessità temporale di O(n^2). Tuttavia, l'algoritmo può essere ottimizzato mediante l'uso di una variabile flag che esce dal ciclo al termine dello scambio. Il caso migliore per l'ordinamento a bolle può essere O(n) quando l'array è ordinato.

Ad esempio, prendiamo una matrice non ordinata di cinque numeri come indicato di seguito

13, 32,26, 34,9

L'ordinamento a bolle inizierà considerando i primi due elementi e li confronterà per verificare quale è maggiore. In questo caso, 32 è maggiore di 13. Quindi questa porzione è già ordinata. Successivamente, confrontiamo 32 con 26. Quindi troviamo che 32 è maggiore di 26, quindi devono essere scambiati. Il nuovo array apparirà come

13, 26, 32,34,9

Successivamente, confrontiamo 32 e 34. Sappiamo che sono già ordinati. Passiamo quindi alle ultime due variabili 34 e 9. Poiché 34 è maggiore di 9, devono essere scambiate.

Scambiamo i valori e arriviamo alla fine dell'array dopo la prima iterazione. Ora l'array apparirà come

13, 26. 32,9,34

Dopo la seconda iterazione, l'array apparirà come

13, 26, 9,32,34

Dopo la terza iterazione, l'array diventerà

13,9,26,32,34

Dopo la quarta iterazione, l'array sarà completamente ordinato

9, 13,26,32,34

Da leggere: Idee di progetto in C

L'algoritmo

Qui assumiamo che l'array abbia n elementi. Inoltre, assumiamo che la funzione di scambio dei valori stia scambiando tutti i valori per creare i numeri dell'array in ordine.

avviare BubbleSort (array)

per tutti gli elementi della lista

se array[i]> array[i+1]

valori di scambio(array[i], array[i+1] )

finisci se

finire per

matrice di ritorno

fine Ordinamento a bolle

Leggi: Ordinamento nella struttura dei dati: categorie e tipi

Pseudocodice

È evidente nell'algoritmo di cui sopra che esiste un confronto tra ciascuna coppia dell'elemento dell'array fino a quando l'intero array non viene ordinato in ordine crescente. Potrebbe causare alcuni problemi di complessità, come il risultato dell'algoritmo quando l'array è già ordinato in ordine crescente. Per risolvere il problema, utilizzeremo una variabile flag, che ci consente di vedere se ci sono stati scambi. Se non sono più necessari scambi, usciremo dal ciclo interno.

Lo pseudocodice per l'algoritmo BubbleSort può essere scritto come segue

procedura BubbleSort (array: elementi nell'array)

itera= array.count;

per k=0 per iterare-1 fare:

flag= falso

per l=0 per iterare-1 fare:

se (array[l]> array[l+1]) allora

valori di scambio(array[l], array [l+1])

bandiera=vero

finisci se

finire per

Se (non scambiato), allora

Rottura

Finisci se

Fine per

Matrice di ritorno della procedura di fine

Proviamo un programma di esempio di bubble sort in C :

# include<stdio.h>

principale vuoto

{

int array [10], i, j, num

per (i=0; i<=9; i++)

{

scanf("%d", &array[i])

}

for(i=0;i<=9;i++)

{

for(j=0;j<=9-i;j++)

{

if(array[j]>array[j+1])

{

num= matrice[j];

matrice[j]=matrice[j+1];

matrice[j+1]=num;

}

}

}

printf("L'array ordinato è /n");

for(i=0;i<=9;i++)

{

printf(“%d ”,&array[i])

}

}

Come mostrato nell'esempio, questo algoritmo di ordinamento a bolle accetta 10 numeri dall'utente e li memorizza nell'array. Nella parte successiva, ci sono due cicli for. Il ciclo esterno viene eseguito per il valore I, pari a zero a minore di uguale a nove. La funzione del ciclo esterno è quella di prendersi cura di tutti gli elementi del valore che devono essere confrontati con altri elementi.

C'è un altro anello all'interno del ciclo esterno. Inizia da j=0 e prosegue finché non è minore o uguale a otto. All'interno, c'è un'istruzione if condizionale che confronta e controlla se array[j] è maggiore di array [j+1]. Se la condizione è soddisfatta, i valori di array[j] e array [j+1] vengono scambiati tra loro.

A questo scopo viene utilizzata una variabile con il nome di num. Prima array[j] viene assegnato a num, quindi array[j+1] viene assegnato a array[j] e infine num viene assegnato a array[j+1]. Questo processo continuerà fino a quando tutti gli elementi nell'array non saranno ordinati in ordine crescente. Successivamente, viene stampato l'array ordinato.

Implementazione ottimizzata di Bubble Sort

Abbiamo un algoritmo ottimizzato per l'ordinamento delle bolle per migliorare i risultati. L'uso di una variabile flag fa l'ottimizzazione. La variabile flag manterrà 1 se c'è uno scambio altrimenti uscirà dal ciclo. Di seguito è riportato il programma di ordinamento delle bolle ottimizzato in C.

#include<stdio.h>

principale vuoto

{

int array [10], i, j, num, flag=0;

per (i=0; i<=9; i++)

{

scanf("%d", &array[i])

}

for(i=0;i<=9;i++)

{

for(j=0;j<=9-i;j++)

{

if(array[j]>array[j+1])

{

num= matrice[j];

matrice[j]=matrice[j+1];

matrice[j+1]=num;

bandiera=1;

}

se (! bandiera)

{

rottura;

}

}

}

printf("L'array ordinato è /n");

for(i=0;i<=9;i++)

{

printf(“%d ”,&array[i])

}

}

Il programma specificato viene eseguito in modo simile al normale programma di ordinamento a bolle. L'unico cambiamento è l'uso della variabile flag. Inizialmente, il flag è impostato su 0. Tuttavia, se si verifica uno scambio, il flag diventa 1. Ciò implica che l'array richiede ancora un altro controllo. D'altra parte, se il flag non è 1, implicando che lo scambio non è avvenuto, usciamo dal ciclo interno, supponendo che l'array sia già ordinato. Una volta eseguito, otterremo lo stesso risultato del normale ordinamento a bolle.

Complessità temporale

La complessità temporale del caso migliore per l'ordinamento a bolle è O(n). Succede quando l'array è già ordinato. Il caso peggiore è O(n*n) quando l'array non è stato ordinato.

Leggi: I 12 migliori programmi di pattern in Java che dovresti controllare oggi

Cosa succede dopo?

Se sei interessato a saperne di più su Java, lo sviluppo di software full-stack, dai un'occhiata al Diploma PG di upGrad e IIIT-B in Sviluppo software full-stack, progettato per i professionisti che lavorano e offre oltre 500 ore di formazione rigorosa, oltre 9 progetti e incarichi, status di Alumni IIIT-B, progetti pratici pratici e assistenza sul lavoro con le migliori aziende.