Ordinamento a bolle è il più semplice algoritmo di ordinamento funziona scambiando ripetutamente gli elementi adiacenti se sono nell'ordine sbagliato. Questo algoritmo non è adatto a set di dati di grandi dimensioni poiché la sua complessità temporale media e nel caso peggiore è piuttosto elevata.
Algoritmo di ordinamento a bolle
Pratica consigliata per l'ordinamento delle bolle Provalo!Nell'algoritmo Bubble Sort,
- attraversare da sinistra e confrontare gli elementi adiacenti e quello più alto viene posizionato sul lato destro.
- In questo modo, l'elemento più grande viene spostato inizialmente all'estremità più a destra.
- Questo processo viene quindi continuato per trovare il secondo più grande e posizionarlo e così via fino a quando i dati non vengono ordinati.
Come funziona il Bubble Sort?
Cerchiamo di comprendere il funzionamento del bubble sort con l'aiuto della seguente illustrazione:
Ingresso: arr[] = {6, 0, 3, 5}
metodo che esegue l'override in JavaPrimo passaggio:
L'elemento più grande viene posizionato nella posizione corretta, ovvero alla fine dell'array.
Algoritmo Bubble Sort: posizionamento dell'elemento più grande nella posizione corretta
Secondo passaggio:
Posiziona il secondo elemento più grande nella posizione corretta
Algoritmo Bubble Sort: posizionamento del secondo elemento più grande nella posizione corretta
Terzo passaggio:
Posiziona i due elementi rimanenti nelle posizioni corrette.
assolutamente unicoAlgoritmo Bubble Sort: posizionamento degli elementi rimanenti nelle posizioni corrette
- N. totale di passaggi: n-1
- N. totale di confronti: n*(n-1)/2
Implementazione di Bubble Sort
Di seguito è riportata l'implementazione del bubble sort. Può essere ottimizzato arrestando l'algoritmo se il ciclo interno non ha causato alcuno scambio.
C++ // Optimized implementation of Bubble sort #include using namespace std; // An optimized version of Bubble Sort void bubbleSort(int arr[], int n) { int i, j; bool swapped; for (i = 0; i < n - 1; i++) { swapped = false; for (j = 0; j < n - i - 1; j++) { if (arr[j]>arr[j + 1]) { scambia(arr[j], arr[j + 1]); scambiato = vero; } } // Se non sono stati scambiati due elementi // dal ciclo interno, allora break if (swapped == false) break; } } // Funzione per stampare un array void printArray(int arr[], int size) { int i; per (i = 0; i< size; i++) cout << ' ' << arr[i]; } // Driver program to test above functions int main() { int arr[] = { 64, 34, 25, 12, 22, 11, 90 }; int N = sizeof(arr) / sizeof(arr[0]); bubbleSort(arr, N); cout << 'Sorted array:
'; printArray(arr, N); return 0; } // This code is contributed by shivanisinghss2110> C // Optimized implementation of Bubble sort #include #include void swap(int* xp, int* yp) { int temp = *xp; *xp = *yp; *yp = temp; } // An optimized version of Bubble Sort void bubbleSort(int arr[], int n) { int i, j; bool swapped; for (i = 0; i < n - 1; i++) { swapped = false; for (j = 0; j < n - i - 1; j++) { if (arr[j]>arr[j + 1]) { scambia(&arr[j], &arr[j + 1]); scambiato = vero; } } // Se non sono stati scambiati due elementi nel ciclo interno, // allora break if (swapped == false) break; } } // Funzione per stampare un array void printArray(int arr[], int size) { int i; per (i = 0; i< size; i++) printf('%d ', arr[i]); } // Driver program to test above functions int main() { int arr[] = { 64, 34, 25, 12, 22, 11, 90 }; int n = sizeof(arr) / sizeof(arr[0]); bubbleSort(arr, n); printf('Sorted array:
'); printArray(arr, n); return 0; }> Giava // Optimized java implementation of Bubble sort import java.io.*; class GFG { // An optimized version of Bubble Sort static void bubbleSort(int arr[], int n) { int i, j, temp; boolean swapped; for (i = 0; i < n - 1; i++) { swapped = false; for (j = 0; j < n - i - 1; j++) { if (arr[j]>arr[j + 1]) { // Scambia arr[j] e arr[j+1] temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temperatura; scambiato = vero; } } // Se non sono stati scambiati due elementi // dal ciclo interno, allora break if (swapped == false) break; } } // Funzione per stampare un array static void printArray(int arr[], int size) { int i; per (i = 0; i< size; i++) System.out.print(arr[i] + ' '); System.out.println(); } // Driver program public static void main(String args[]) { int arr[] = { 64, 34, 25, 12, 22, 11, 90 }; int n = arr.length; bubbleSort(arr, n); System.out.println('Sorted array: '); printArray(arr, n); } } // This code is contributed // by Nikita Tiwari.> Python3 # Optimized Python program for implementation of Bubble Sort def bubbleSort(arr): n = len(arr) # Traverse through all array elements for i in range(n): swapped = False # Last i elements are already in place for j in range(0, n-i-1): # Traverse the array from 0 to n-i-1 # Swap if the element found is greater # than the next element if arr[j]>arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] swapped = True if (scambiato == False): break # Codice driver da testare sopra if __name__ == '__main__': arr = [64, 34, 25, 12, 22, 11, 90] bubbleSort(arr) print('Array ordinato:') for i in range(len(arr)): print('%d' % arr[i], end=' ') # Questo codice è stato modificato da Suraj krushna Yadav> C# // Optimized C# implementation of Bubble sort using System; class GFG { // An optimized version of Bubble Sort static void bubbleSort(int[] arr, int n) { int i, j, temp; bool swapped; for (i = 0; i < n - 1; i++) { swapped = false; for (j = 0; j < n - i - 1; j++) { if (arr[j]>arr[j + 1]) { // Scambia arr[j] e arr[j+1] temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temperatura; scambiato = vero; } } // Se non sono stati scambiati due elementi // dal ciclo interno, allora break if (swapped == false) break; } } // Funzione per stampare un array static void printArray(int[] arr, int size) { int i; per (i = 0; i< size; i++) Console.Write(arr[i] + ' '); Console.WriteLine(); } // Driver method public static void Main() { int[] arr = { 64, 34, 25, 12, 22, 11, 90 }; int n = arr.Length; bubbleSort(arr, n); Console.WriteLine('Sorted array:'); printArray(arr, n); } } // This code is contributed by Sam007> Javascript // Optimized javaScript implementation // of Bubble sort // An optimized version of Bubble Sort function bubbleSort(arr, n) { var i, j, temp; var swapped; for (i = 0; i < n - 1; i++) { swapped = false; for (j = 0; j < n - i - 1; j++) { if (arr[j]>arr[j + 1]) { // Scambia arr[j] e arr[j+1] temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temperatura; scambiato = vero; } } // SE non sono stati scambiati due elementi // dal ciclo interno, allora break if (swapped == false) break; } } // Funzione per stampare un array function printArray(arr, size) { var i; per (i = 0; i< size; i++) console.log(arr[i] + ' '); } // Driver program var arr = [ 64, 34, 25, 12, 22, 11, 90 ]; var n = arr.length; bubbleSort(arr, n); console.log('Sorted array: '); printArray(arr, n); // This code is contributed shivanisinghss2110> PHP // PHP Optimized implementation // of Bubble sort // An optimized version of Bubble Sort function bubbleSort(&$arr) { $n = sizeof($arr); // Traverse through all array elements for($i = 0; $i < $n; $i++) { $swapped = False; // Last i elements are already // in place for ($j = 0; $j < $n - $i - 1; $j++) { // Traverse the array from 0 to // n-i-1. Swap if the element // found is greater than the // next element if ($arr[$j]>$arr[$j+1]) { $t = $arr[$j]; $arr[$j] = $arr[$j+1]; $arr[$j+1] = $t; $ scambiato = Vero; } } // Se non sono stati scambiati due elementi // dal ciclo interno, allora break if ($swapped == False) break; } } // Codice driver $arr = array(64, 34, 25, 12, 22, 11, 90); $len = dimensionedi($arr); bubbleSort($arr); echo 'Array ordinato:
'; for($i = 0; $i< $len; $i++) echo $arr[$i].' '; // This code is contributed by ChitraNayal. ?>> Produzione
Sorted array: 11 12 22 25 34 64 90>
Analisi della complessità del Bubble Sort :
Complessità temporale: SU2)
Spazio ausiliario: O(1)
Vantaggi del Bubble Sort:
- Il Bubble sort è facile da capire e implementare.
- Non richiede alcuno spazio di memoria aggiuntivo.
- È un algoritmo di ordinamento stabile, il che significa che gli elementi con lo stesso valore chiave mantengono il loro ordine relativo nell'output ordinato.
Svantaggi del Bubble Sort:
- Il Bubble sort ha una complessità temporale pari a O(N2) che lo rende molto lento per set di dati di grandi dimensioni.
- Bubble sort è un algoritmo di ordinamento basato sul confronto, il che significa che richiede un operatore di confronto per determinare l'ordine relativo degli elementi nel set di dati di input. Può limitare l'efficienza dell'algoritmo in alcuni casi.
Alcune domande frequenti relative al Bubble Sort:
Qual è il caso limite per il Bubble sort?
L'ordinamento a bolle richiede un tempo minimo (ordine di n) quando gli elementi sono già ordinati. Quindi è meglio verificare in anticipo se l'array è già ordinato o meno, per evitare O(N2) complessità temporale.
L'ordinamento avviene sul posto in Bubble sort?
Sì, Bubble sort esegue lo scambio di coppie adiacenti senza l'uso di alcuna struttura dati importante. Quindi l'algoritmo Bubble Sort è un algoritmo sul posto.
L'algoritmo Bubble Sort è stabile?
Sì, l'algoritmo di bubble sort è stabile.
Dove viene utilizzato l'algoritmo Bubble Sort?
Grazie alla sua semplicità, il bubble sort viene spesso utilizzato per introdurre il concetto di algoritmo di ordinamento. Nella computer grafica, è popolare per la sua capacità di rilevare un piccolo errore (come uno scambio di soli due elementi) in array quasi ordinati e risolverlo solo con complessità lineare (2n).
Esempio: viene utilizzato in un algoritmo di riempimento poligonale, in cui le linee di delimitazione vengono ordinate in base alla loro coordinata x su una linea di scansione specifica (una linea parallela all'asse x) e con l'incremento y il loro ordine cambia (due elementi vengono scambiati) solo alle intersezioni di due linee.
log4j
Articoli Correlati:
- Bubble sort ricorsivo
- Pratica di codifica per l'ordinamento
- Quiz sull'ordinamento delle bolle
- Analisi della complessità del Bubble Sort