Ordinamento a bolle di un array monodimensionale: algoritmo, codice del programma in linguaggio C.

Lavorare con le informazioni è il più redditizioi modi per memorizzarlo sono strutture e array. Quest'ultimo può contenere qualsiasi tipo di dati, che è comodo da usare nel programma. Sono spesso utilizzati nel lavoro dei negozi online e nello sviluppo di giochi. Pertanto, i dati contenuti in essi vengono ripetutamente ordinati e scambiati e su di essi vengono eseguite operazioni logiche o matematiche. Un modo per portare ordine nell'array è l'ordinamento delle bolle. Questa pubblicazione studierà il suo codice C e la logica delle permutazioni.

Algoritmo di ordinamento di array

Difficoltà tecniche per il programmatorel'ordinamento a bolle di un array unidimensionale non rappresenta, sebbene sia usato molto raramente a causa della sua bassa efficienza. È più spesso considerato nella fase di addestramento come il più semplice. Tuttavia, è lontano dall'essere il più efficace. Il suo algoritmo consiste nel confrontare alternativamente le cifre e sovrascrivere mutualmente le celle se la condizione è soddisfatta.

Descrizione di ordinamento passo passo

Alla prima iterazione, duenumeri vicini. Se la sinistra è più grande, viene riscritta in posti con quella giusta. Meno 8 e 0 le condizioni non soddisfano. Ecco perché non cambiano in luoghi. Zero e 5 non si adattano. 5 e 3 sono adatti. Tuttavia, a questa iterazione il frame di lettura non cade sui primi cinque, ma si sposta a destra, poiché 5 prima di questo era comparato a zero. Ciò significa che la prossima coppia - 3 e 9 cambia posizione, quindi il lettore è offerto di rivedere tutte le sostituzioni in modo indipendente senza commenti dell'autore e di studiare l'algoritmo dell'ordinamento delle bolle.

Come risultato di tutte le iterazioni, l'array gradualmenteè ordinato, e questo è fondamentalmente il caso: i numeri positivi più grandi si spostano rapidamente a destra, mentre quelli più piccoli e negativi si spostano lentamente a sinistra. Sembra che bolle di gas in un liquido si alzino rapidamente. A causa di questa analogia, l'algoritmo era chiamato bubble sorting.

Stima della complessità computazionale

L'algoritmo di ordinamento ideale dovrebbe essereil più velocemente possibile. Allo stesso tempo, dovrebbe occupare una piccola quantità di CPU e risorse di memoria. E un tale processo come lo smistamento di bolle di un array non può essere il più efficiente dal punto di vista energetico e redditizio. A causa della vasta applicazione, non ha trovato. Se al momento ci sono meno problemi con la memoria, allora le risorse del processore dovrebbero essere preoccupate. Poiché gli array digitali possono essere non solo grandi, ma enormi, il consumo di risorse informatiche sarà imprevedibile.

Se lo smistamento delle bolle è, in linea di principio, veloceaffronta lo stabilimento dell'ordine in una matrice relativamente piccola, quindi in generale possono esserci dei fallimenti a causa dell'eccessivo dispendio di risorse. Ciò significa che la proprietà di universalità inerente all'algoritmo verrà violata. E l'ordinamento di una bolla ha una complessità N-quadrata ed è molto lontano dal logaritmo della complessità N. Inoltre, il rischio di errori nell'elaborazione di un array di grandi dimensioni aumenta le possibilità di perdita dei dati a causa della sovrascrittura delle celle. Molto più redditizio a questo riguardo sarà l'ordinamento per inserimento o l'algoritmo Shell.

Codice del software

Quanto segue è nell'applicazione graficacodice del computer per il linguaggio C consente di eseguire l'ordinamento delle bolle. È reso come una funzione separata di tipo void. Non restituisce alcun valore, ma l'uso dei puntatori scambia gli elementi in base alle condizioni di ordinamento. In questo caso, il codice risolve il problema dell'ordinamento di bolle di un array di numeri interi in ordine ascendente.

Per eseguire questa funzione, l'utente devecreare una matrice che deve essere riempita con i valori desiderati. Questo può essere fatto manualmente, impostando la dimensione e il numero di elementi all'inizio del programma. Quindi puoi riempire l'array con valori costanti. La seconda opzione è quella di creare un programma universale dichiarando un grande array monodimensionale di 100 elementi.

Dichiarazione e inizializzazione di un array

Assegnare una variabile intera e assegnarlaIl valore letto dalla tastiera può limitare il numero di celle che verranno riempite. È inoltre possibile implementare la funzione di immissione di elementi di un array dall'utente dalla tastiera, utilizzando la funzione scanf ("% d", & value). In questo esempio, "% d" è una stringa di modifica che indica al compilatore che un valore intero verrà ricevuto dopo la scansione. Il valore della variabile memorizzerà un valore che è la dimensione di un array intero monodimensionale.

Per usare l'algoritmo di ordinamento, dovrestiper passare nella funzione il nome dell'array e le sue dimensioni. Nella situazione presentata nell'applicazione grafica, la chiamata alla funzione di ordinamento sarà simile a questa: BubleSort (dataArray, sizeDataArray). Ovviamente, alla fine della riga dopo la funzione, dovresti inserire un punto e virgola anziché un punto, come richiesto dalle regole di sintassi del programma. Quindi, dataArray è il nome dell'array da ordinare e sizeDataArray è la sua dimensione.

Passare questi parametri alla funzione BubleSort ()risulterà che invece di usare sizeArray, come puoi vedere nella figura, in un programma reale le operazioni verranno eseguite con sizeDataArray. Ciò significa anche che la funzione BubleSort () utilizzerà un numero intero di dati. Allo stesso modo, vengono chiamate la funzione printArrayFunction () e ArrayIntegerInputFunction (). Il primo è responsabile per la stampa, cioè per l'output sulla console degli elementi. E il secondo è necessario per riempirlo con elementi inseriti dall'utente dalla tastiera.

Questo stile di programmazione, quando isolatole operazioni vengono eseguite sotto forma di funzioni, aumenta significativamente la leggibilità del codice e ne accelera lo sviluppo. In tale programma, la matrice viene compilata separatamente dalla tastiera, stampata e la bolla si ordina da sé. Quest'ultimo può essere utilizzato per organizzare i dati o come funzione secondaria progettata per trovare il minimo e il massimo dell'array.

Ordinamento inserzione

In ordinamento con il metodo di inserimentoconfrontando alternativamente ogni elemento e costruendo una catena di elementi già ordinati in base alla condizione. Di conseguenza, il risultato di ogni confronto successivo è la ricerca di una cella in cui può essere inserito un nuovo valore. Ma l'inserimento di ognuno di essi viene eseguito nella parte già ordinata dell'array.

Tale elaborazione è più veloce e ha meno complessità computazionale. Il codice C è presentato nell'applicazione grafica.

È anche reso sotto forma di una funzione in cuiCome argomenti, il nome dell'array che deve essere ordinato e le dimensioni dell'array vengono trasferite. Qui puoi vedere quanto è lento l'ordinamento delle bolle. Inserisce lavori simili è molto più veloce e ha un codice compatto.