Tag: Bubble Sort B, B Bubble Sort, 2D Array Bubble Sort
Bubble sort
E l'algoritmo è molto semplice. Esaminiamo l'array di numeri e controlliamo l'ordine (il numero successivo deve essere maggiore e uguale al precedente), non appena ci imbattiamo in una violazione dell'ordine, scambiamo immediatamente gli elementi, raggiungiamo la fine dell'array, quindi ricominciamo da capo.
Ordiniamo l'array (1, 5, 2, 7, 6, 3)
Esaminiamo l'array, controlliamo il primo numero e il secondo, vanno in ordine crescente. Poi c'è una violazione dell'ordine, scambiamo questi elementi
1, 2, 5, 7, 6, 3
Continuiamo a camminare lungo l'array, 7 è più di 5, ma 6 è meno, quindi ci scambiamo i posti
1, 2, 5, 6, 7, 3
3 fuori servizio, scambia i posti con 7
1, 2, 5, 6, 3, 7
Torna all'inizio dell'array e fai lo stesso
1, 2, 5, 3, 6, 7
1, 2, 3, 5, 6, 7
Dicono che questo sia simile all '"emergenza" di elementi "più leggeri", come le bolle, motivo per cui l'algoritmo ha preso il nome. void bubbleSort (int * a, size_t size) (size_t i, j; int tmp; for (i \u003d 1; i< size; i++) { for (j = 1; j < size; j++) { if (a[j] > a) (tmp \u003d a [j]; a [j] \u003d a; a \u003d tmp;))))
Questo algoritmo richiederà sempre (n-1) 2 passaggi, indipendentemente dall'input. Anche se l'array è ordinato, verrà comunque attraversato (n-1) 2 volte. Inoltre, i dati già ordinati verranno nuovamente controllati.
Supponiamo di dover ordinare l'array 1, 2, 4, 3
1 2 4 3
1 2 4 3
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
Dopo che gli elementi a e a sono stati scambiati, non è più necessario passare attraverso questa sezione dell'array. Prendiamo in considerazione questo e ripetiamo l'algoritmo
Void bubbleSort2 (int * a, size_t size) (size_t i, j; int tmp; for (i \u003d 1; i< size; i++) { for (j = i; j > 0; j--) (if (a [j]< a) { tmp = a[j]; a[j] = a; a = tmp; } } } }
Un'altra implementazione
Void bubbleSort2b (int * a, size_t size) (size_t i, j; int tmp; for (i \u003d 1; i< size; i++) { for (j = 1; j <= size-i; j++) { if (a[j] < a) { tmp = a[j]; a[j] = a; a = tmp; } } } }
In questo caso, ci sarà la metà del numero di passaggi, ma rimane ancora il problema di ordinare un array già ordinato: è necessario che la funzione esamini l'array ordinato una volta. Per fare ciò, introduciamo una variabile flag: verrà omessa (flag \u003d 0) se l'array è ordinato. Non appena ci imbattiamo in un guasto, il flag verrà sollevato (flag \u003d 1) e inizieremo a ordinare l'array come al solito.
Void bubbleSort3 (int * a, size_t size) (size_t i; int tmp; char flag; do (flag \u003d 0; for (i \u003d 1; i< size; i++) { if (a[i] < a) { tmp = a[i]; a[i] = a; a = tmp; flag = 1; } } } while (flag); }
In questo caso, anche la complessità è dell'ordine di n 2, ma nel caso di un array ordinato, ci sarà un solo passaggio.
Ora miglioriamo l'algoritmo. Scriviamo una funzione generale per ordinare un array di tipo void. Poiché il tipo di variabile non è noto, sarà necessario trasferire ulteriormente la dimensione di un elemento dell'array e la funzione di confronto.
Int intSort (const void * a, const void * b) (return * ((int *) a)\u003e * ((int *) b);) void bubbleSort3g (void * a, size_t item, size_t size, int (* cmp) (const void *, const void *)) (size_t i; void * tmp \u003d NULL; char flag; tmp \u003d malloc (item); do (flag \u003d 0; for (i \u003d 1; i< size; i++) { if (cmp(((char*)a + i*item), ((char*)a + (i-1)*item))) { memcpy(tmp, ((char*)a + i*item), item); memcpy(((char*)a + i*item), ((char*)a + (i-1)*item), item); memcpy(((char*)a + (i-1)*item), tmp, item); flag = 1; } } } while (flag); free(tmp); }
La funzione sembra brutta: spesso viene calcolato l'indirizzo dell'elemento corrente e precedente. Selezioniamo variabili separate per questo.
Void bubbleSort3gi (void * a, size_t item, size_t size, int (* cmp) (const void *, const void *)) (size_t i; void * tmp \u003d NULL; void * prev, * cur; char flag; tmp \u003d malloc (elemento); do (flag \u003d 0; i \u003d 1; prev \u003d (char *) a; cur \u003d (char *) prev + item; while (i< size) { if (cmp(cur, prev)) { memcpy(tmp, prev, item); memcpy(prev, cur, item); memcpy(cur, tmp, item); flag = 1; } i++; prev = (char*)prev + item; cur = (char*)cur + item; } } while (flag); free(tmp); }
Ora, usando queste funzioni, puoi ordinare array di qualsiasi tipo, ad esempio
Void main () (int a \u003d (1, 0, 9, 8, 7, 6, 2, 3, 4, 5); int i; bubbleSort3gi (a, sizeof (int), 10, intSort); for (i \u003d 0; i< 10; i++) { printf("%d ", a[i]); } _getch(); }
Ordinamento di un array multidimensionale
Ordinare un array multidimensionale statico è essenzialmente uguale all'ordinamento di un array unidimensionale. È possibile sfruttare la proprietà che gli array statici unidimensionali e multidimensionali hanno la stessa rappresentazione della memoria.
Void main () (int a \u003d (1, 9, 2, 8, 3, 7, 4, 6, 5); int i, j; bubbleSort3gi (a, sizeof (int), 9, intSort); for (i \u003d 0; i< 3; i++) {
for (j = 0; j < 3; j++) {
printf("%d ", a[i][j]);
}
}
}
Сортировка динамически созданного двумерного массива может быть произведена двумя способами. Во-первых, можно по определённому алгоритму находить индекс i-го и j-го элемента по порядковому номеру k от 0 до n * m.
#include
In secondo luogo, è possibile prima spostare la matrice in unidimensionale, ordinare la matrice unidimensionale e quindi spostarla di nuovo in bidimensionale.
Void bubbleSort3gi2d (void ** a, size_t item, size_t m, size_t n, int (* cmp) (const void *, const void *)) (size_t size \u003d m * n, sub_size \u003d n * item; size_t i, j , k; void * arr \u003d malloc (size * item); char * p1d \u003d (char *) arr; char * p2d \u003d (char *) a; // Copia matrice bidimensionale di tipo void a unidimensionale per (i \u003d 0; i< m; i++) { memcpy(p1d + i*sub_size, *((void**)(p2d + i*item)), sub_size); } bubbleSort3gi(arr, item, size, cmp); //Копируем одномерный массив обратно в двумерный for (i = 0; i < m; i++) { memcpy(*((void**)(p2d + i*item)), p1d + i*sub_size, sub_size); } }
Se sei confuso su questa funzione, usane una digitata. Chiama, dall'esempio precedente
Bubble Sort è l'algoritmo di ordinamento più semplice utilizzato esclusivamente per scopi didattici. Applicazione pratica questo algoritmo non lo è, poiché non è efficiente, soprattutto se è necessario ordinare l'array grande taglia... Uno dei vantaggi del Bubble Sort è la semplicità dell'implementazione dell'algoritmo.
L'algoritmo di ordinamento delle bolle è ridotto alla ripetizione di passaggi attraverso gli elementi della matrice da ordinare. Il ciclo interno itera sugli elementi dell'array. Per ogni passaggio, vengono confrontati due elementi adiacenti e, se l'ordine non è corretto, gli elementi vengono scambiati. Il ciclo esterno verrà eseguito fino a quando l'array non sarà ordinato. Pertanto, il ciclo esterno controlla il numero di operazioni del ciclo interno.Quando non vengono eseguite permutazioni durante il passaggio successivo attraverso gli elementi dell'array, l'array sarà considerato ordinato. Per comprendere bene l'algoritmo, ordiniamo l'array utilizzando il metodo delle bolle, ad esempio, di 7 numeri (vedi Tabella 1).
matrice originale: 3 3 7 1 2 5 0
| Numero di iterazione | Elementi della matrice | Permutazioni | ||||||
|---|---|---|---|---|---|---|---|---|
| rif. Vettore | 3 | 3 | 7 | 1 | 2 | 5 | 0 | |
| 0 | 3 | 3 | falso | |||||
| 1 | 3 | 7 | falso | |||||
| 2 | 1 | 7 | 7\u003e 1, vero | |||||
| 3 | 2 | 7 | 7\u003e 2, vero | |||||
| 4 | 5 | 7 | 7\u003e 5, vero | |||||
| 5 | 0 | 7 | 7\u003e 0, vero | |||||
| tech. Vettore | 3 | 3 | 1 | 2 | 5 | 0 | 7 | |
| 0 | 3 | 3 | falso | |||||
| 1 | 1 | 3 | 3\u003e 1, vero | |||||
| 2 | 2 | 3 | 3\u003e 2, vero | |||||
| 3 | 0 | 3 | 3\u003e 0, vero | |||||
| 4 | 3 | 5 | falso | |||||
| 5 | 5 | 7 | falso | |||||
| tech. Vettore | 3 | 1 | 2 | 0 | 3 | 5 | 7 | |
| 0 | 1 | 3 | 3\u003e 1, vero | |||||
| 1 | 2 | 3 | 3\u003e 2, vero | |||||
| 2 | 0 | 3 | 3\u003e 0, vero | |||||
| 3 | 3 | 3 | falso | |||||
| 4 | 3 | 5 | falso | |||||
| 5 | 5 | 7 | falso | |||||
| tech. Vettore | 1 | 2 | 0 | 3 | 3 | 5 | 7 | |
| 1 | 2 | falso | ||||||
| 0 | 2 | 2\u003e 0, vero | ||||||
| 2 | 3 | falso | ||||||
| 3 | 3 | falso | ||||||
| 3 | 5 | falso | ||||||
| 5 | 7 | falso | ||||||
| tech. Vettore | 1 | 0 | 2 | 3 | 3 | 5 | 7 | |
| 0 | 1 | 1\u003e 0, vero | ||||||
| 1 | 2 | falso | ||||||
| 2 | 3 | falso | ||||||
| 3 | 3 | falso | ||||||
| 3 | 5 | falso | ||||||
| 5 | 7 | falso | ||||||
| matrice finale | 0 | 1 | 2 | 3 | 3 | 5 | 7 | |
| Fine dello smistamento | ||||||||
Per ordinare l'array, sono stati necessari cinque inizi del ciclo interno, per. Dopo aver iniziato, il ciclo for ha funzionato 6 volte, poiché ci sono 7 elementi nell'array, quindi iterazioni (ripetizioni) per loop dovrebbe essere uno in meno. Ad ogni iterazione, vengono confrontati due elementi di array adiacenti. Se l'elemento corrente dell'array è maggiore di quello successivo, li scambiamo. Pertanto, finché la matrice non viene ordinata, verrà eseguito il ciclo interno e verrà eseguita l'operazione di confronto. Nota che per ogni esecuzione completa del ciclo for, almeno un elemento dell'array trova il suo posto. Nel peggiore dei casi, inizia il ciclo interno n-2, dove n è il numero di elementi dell'array. Ciò suggerisce che il Bubble sort è estremamente inefficiente per array di grandi dimensioni.
Sviluppiamo un programma in cui devi prima inserire la dimensione di un array unidimensionale, dopodiché l'array viene riempito con numeri casuali e ordinato con il metodo delle bolle.
// bu_sort.cpp: definisce il punto di ingresso per l'applicazione console. #include "stdafx.h" #include
Il risultato del programma è mostrato nella Figura 1.
Tutti sanno perfettamente che il metodo più veloce della classe dei tipi di scambio è il cosiddetto ordinamento veloce... Scrivono dissertazioni al riguardo, ad esso sono dedicati molti articoli su Habré, sulla base vengono inventati complessi algoritmi ibridi. Ma oggi non ne parliamo ordinamento veloce, ma su un altro metodo di scambio: il buon vecchio bubble sort e suoi miglioramenti, modifiche, mutazioni e varietà.
Lo scarico pratico di questi metodi non è così caldo e molti utenti habrap hanno affrontato tutto questo in prima classe. L'articolo, quindi, è rivolto a coloro che si sono appena interessati alla teoria degli algoritmi e stanno muovendo i primi passi in questa direzione.
immagine: bolle
Oggi parleremo del più semplice smistamento scambi.
Se qualcuno è interessato, dirò che ci sono altre classi - ordinamento di selezione, ordina per inserti, unisci ordinamento, ordinamento di distribuzione, tipi ibridi e ordinamenti paralleli... A proposito, ce ne sono di più ordinamento esoterico... Questi sono vari falsi, fondamentalmente irrealizzabili, fumetti e altri pseudo-algoritmi, sui quali scriverò un paio di articoli nell'hub dell'umorismo IT qualche volta.
Ma questo non ha nulla a che fare con la conferenza di oggi, ora siamo interessati solo al semplice smistamento per scambi. Esistono anche molti smistamenti di scambio (ne conosco più di una dozzina), quindi prenderemo in considerazione il cosiddetto bubble sort e alcuni altri strettamente legati ad esso.
Ti avverto in anticipo che quasi tutti i metodi di cui sopra sono molto lenti e non ci sarà un'analisi approfondita della loro complessità temporale. Alcuni sono più veloci, altri più lenti, ma grosso modo, possiamo dirlo in media O(n 2). Inoltre, non vedo motivo per ingombrare l'articolo con le implementazioni in alcun linguaggio di programmazione. Gli interessati possono trovare facilmente esempi di codice su Rosetta, Wikipedia o altrove.
Ma torniamo allo scambio di smistamento. L'ordinamento si verifica come risultato di più iterazioni sequenziali sull'array e del confronto tra coppie di elementi. Se gli elementi confrontati non sono ordinati l'uno rispetto all'altro, li scambiamo. L'unica domanda è come bypassare esattamente l'array e in base a quale principio scegliere le coppie per il confronto.
Cominciamo non con un bubble sort di riferimento, ma con un algoritmo chiamato ...
Smistamento sciocco
L'ordinamento è davvero stupido. Attraversiamo l'array da sinistra a destra e confrontiamo i vicini lungo il percorso. Se ci imbattiamo in una coppia di elementi mutuamente non ordinati, li scambiamo e torniamo al punto di partenza, cioè all'inizio. Esaminiamo nuovamente l'array, controlliamo l'array, se incontriamo di nuovo la coppia "sbagliata" di elementi vicini, quindi cambiamo i posti e ricominciamo da capo. Continuiamo finché l'array non viene gradualmente risolto."Quindi ogni sciocco sa come ordinare" - dici e avrai assolutamente ragione. Ecco perché l'ordinamento è chiamato "stupido". In questa lezione, miglioreremo e modificheremo costantemente questo metodo. Ora ha una difficoltà temporanea O(n 3), dopo aver effettuato una correzione, abbiamo già portato a O(n 2), poi accelereremo un po 'di più, poi di più e alla fine arriveremo O(n log n) - e non sarà affatto "Ordinamento rapido"!
Facciamo un singolo miglioramento al tipo stupido. Dopo aver trovato due elementi non ordinati adiacenti durante la passeggiata e averli scambiati, non torneremo all'inizio della matrice, ma continueremo a camminare con calma fino alla fine.
In questo caso, davanti a noi non è altro che il noto ...
Bubble sort
O smistamento per scambi semplici... Classico immortale del genere. Il principio di azione è semplice: passiamo attraverso l'array dall'inizio alla fine, scambiando simultaneamente le posizioni degli elementi adiacenti non ordinati. Come risultato del primo passaggio, l'elemento massimo "apparirà" all'ultimo posto. Ora esaminiamo nuovamente la parte non ordinata dell'array (dal primo elemento al penultimo) e cambiamo i vicini non ordinati lungo il percorso. Il secondo elemento più grande sarà al penultimo posto. Continuando con lo stesso spirito, ignoreremo la parte non ordinata sempre in diminuzione della matrice, spingendo i massimi trovati fino alla fine.Se non solo spingiamo gli alti fino alla fine, ma spostiamo anche i minimi all'inizio, allora otteniamo ...
Smistamento shaker
Lei è ordinamento casuale, lei smistamento cocktail... Il processo inizia come in una "bolla": spremiamo il massimo negli stessi cortili. Dopodiché, ci rivolgiamo a 180 0 e andiamo nella direzione opposta, mentre rotoliamo già all'inizio, non il massimo, ma il minimo. Dopo aver ordinato il primo e l'ultimo elemento dell'array, eseguiamo di nuovo i salti mortali. Dopo essere andati avanti e indietro più volte, finiamo nel mezzo della lista.Lo shaker sort funziona un po 'più velocemente del bubble sort, poiché sia \u200b\u200bi massimi che i minimi migrano alternativamente lungo l'array nelle direzioni richieste. I miglioramenti, come si suol dire, sono evidenti.
Come puoi vedere, se diventi creativo con il processo di enumerazione, è più veloce spingere gli elementi pesanti (leggeri) alle estremità dell'array. Pertanto, gli artigiani hanno suggerito un'altra "road map" non standard per aggirare l'elenco.
Ordinamento dispari
Questa volta, non ci affretteremo avanti e indietro nella matrice, ma torneremo di nuovo all'idea di un attraversamento sistematico da sinistra a destra, ma faremo solo un passo più ampio. Al primo passaggio, gli elementi con una chiave dispari vengono confrontati con i vicini in posti pari (confronta il 1 ° con il 2 °, poi il 3 ° con il 4 °, il 5 ° con il 6 ° e così via). Quindi, al contrario, confrontiamo / cambiamo gli elementi "pari" con quelli "dispari". Poi di nuovo "pari-dispari", poi di nuovo "pari-dispari". Il processo si interrompe quando dopo due passaggi consecutivi nell'array ("pari-dispari" e "pari-dispari") non si è verificato alcuno scambio. Quindi l'hanno risolto.In una normale "bolla", durante ogni passaggio, spremiamo sistematicamente il massimo corrente alla fine dell'array. Se salti gli indici pari e dispari, tutti gli elementi dell'array più o meno grandi vengono simultaneamente spinti a destra di una posizione in una corsa. Risulta più veloce.
Analizziamo quest'ultimo ridotto* per Sortuvannya Bulbashkoy** - Combinazioni Sortuvannya***. Questo metodo ordina molto rapidamente, O(n 2) È la sua peggiore complessità. In media nel tempo, abbiamo O(n log n), e anche il migliore, non ci crederai O(n). Cioè, un degno concorrente di qualsiasi "quicksorts" e questo, intendiamoci, senza l'uso della ricorsione. Tuttavia, ho promesso che oggi non approfondiremo le velocità di crociera, lasciamo che sia tranquillo e andremo direttamente all'algoritmo.
Le tartarughe sono da incolpare di tutto
Un po 'di storia. Nel 1980, Wlodzimierz Dobosievich spiegò perché lo smistamento delle bolle e i suoi derivati \u200b\u200bfunzionano così lentamente. È tutto a causa delle tartarughe... Le tartarughe sono piccoli oggetti alla fine della lista. Come avrai notato, i tipi di bolle sono rivolti ai "conigli" (da non confondere con i "conigli" di Babushkin) - elementi grandi in cima alla lista. Si muovono molto rapidamente verso il traguardo. Ma i lenti rettili strisciano verso l'inizio con riluttanza. Puoi personalizzare le "tortillas" usando spazzole per capelli.immagine: tartaruga colpevole
Ordinamento con un pettine
Nella "bolla", "shaker" e "pari-dispari", durante l'iterazione sull'array, vengono confrontati gli elementi adiacenti. L'idea principale del "pettine" è quella di prendere inizialmente una distanza sufficientemente grande tra gli elementi confrontati e, quando la matrice è ordinata, restringere questa distanza al minimo. Quindi, in qualche modo pettiniamo la matrice, levigandola gradualmente in fili sempre più ordinati.È meglio prendere lo scarto iniziale tra gli elementi confrontati non comunque, ma tenendo conto di un valore speciale chiamato fattore di riduzione, il cui valore ottimale è circa 1,247. Innanzitutto, la distanza tra gli elementi è uguale alla dimensione della matrice divisa per fattore di riduzione (il risultato è naturalmente arrotondato al numero intero più vicino). Quindi, dopo aver esaminato l'array con questo passaggio, dividiamo nuovamente il passaggio per fattore di riduzione e ripassare l'elenco. Questo continua finché la differenza tra gli indici non raggiunge uno. In questo caso, l'array viene ordinato con una bolla regolare.
Il valore ottimale è stato stabilito sperimentalmente e teoricamente fattore di riduzione:
Quando questo metodo è stato inventato, poche persone vi hanno prestato attenzione a cavallo degli anni '70 e '80. Un decennio dopo, quando la programmazione cessò di essere il compito degli scienziati e degli ingegneri dell'IBM, e stava già acquisendo un carattere di massa simile a una valanga, il metodo fu riscoperto, studiato e reso popolare nel 1991 da Stephen Lacey e Richard Box.
In realtà è tutto quello che volevo dirti sul Bubble Sort e altri simili.
- Appunti
* ridotto ( ukr.) - miglioramento
** Sortuvannya bulbashkoy ( ukr.) - Bubble Sort
*** Combinatore Sortuvannya ( ukr.) - Ordinamento con un pettine
Metodo a bolle
Ordinamento per scambi semplici, smistamento bolle (ing. bubble sort) è un semplice algoritmo di ordinamento. Questo algoritmo è il più semplice per la comprensione e l'implementazione, ma è efficace solo per piccoli array. Complessità algoritmo: O ( n²).
L'algoritmo è considerato educativo e praticamente non viene utilizzato al di fuori della letteratura educativa; invece, nella pratica viene utilizzato l'ordinamento per inserzione.
Algoritmo
Un esempio di una bolla che ordina un elenco di numeri casuali.
L'algoritmo consiste in passaggi ripetuti attraverso l'array da ordinare. Per ogni passaggio, gli elementi vengono confrontati sequenzialmente a coppie e, se l'ordine nella coppia non è corretto, gli elementi vengono scambiati. I passaggi attraverso l'array vengono ripetuti fino a quando, al passaggio successivo, risulta che gli scambi non sono più necessari, il che significa che l'array è ordinato. Durante il passaggio dell'algoritmo, l'elemento che non è al suo posto "galleggia" nella posizione desiderata come una bolla nell'acqua, da cui il nome dell'algoritmo.
A volte ad ogni passaggio l'array viene visualizzato dall'inizio, quindi dalla fine. Questo si chiama shaker grading.
Esempi di implementazione
Pitone
Def swap (arr, i, j): arr [i], arr [j] \u003d arr [j], arr [i] def bubble_sort (arr): i \u003d len (arr) mentre i\u003e 1: for j in xrange (i - 1): se arr [j]\u003e arr [j + 1]: swap (arr, j, j + 1) i - \u003d 1
VBA
Sub Sort (Mus () As Long) Dim n As Long, i As Long, tmp As Long i \u003d 1 Do While (i< UBound (Mus) ) If Mus(i) > Mus (i + 1) Allora tmp \u003d Mus (i) Mus (i) \u003d Mus (i + 1) Mus (i + 1) \u003d tmp Se i\u003e 1 Allora i \u003d i - 1 Altrimenti i \u003d i + 1 Fine If Altrimenti i \u003d i + 1 End If Loop End Sub
Algoritmo di ordinamento delle bolle Pascal migliorato
P: \u003d True; (C'è una permutazione) K: \u003d 1; (Visualizza numero) While P Do Begin P: \u003d false; For i: \u003d 1 To n-k Do If X [i]\u003e X [i + 1] Then Begin A: \u003d X [i]; X [i]: \u003d X [i + 1]; X [i + 1]: \u003d A; P: \u003d vero; Fine; k: \u003d k + 1; Fine;
PHP
$ size \u003d count ($ arr) -1; for ($ i \u003d $ size; $ i\u003e \u003d 0; $ i -) (for ($ j \u003d 0; $ j<=($i -1 ) ; $j ++) if ($arr [ $j ] >$ arr [$ j +1]) ($ k \u003d $ arr [$ j]; $ arr [$ j] \u003d $ arr [$ j +1]; $ arr [$ j +1] \u003d $ k;))
