Ordinamento nella struttura dei dati: categorie e tipi [con esempi]

La disposizione dei dati in un ordine preferito è chiamata ordinamento nella struttura dei dati. Ordinando i dati, è più facile cercarli rapidamente e facilmente. L'esempio più semplice di ordinamento è un dizionario. Prima dell'era di Internet, quando volevi cercare una parola in un dizionario, lo facevi in ​​ordine alfabetico. Questo lo ha reso facile.

Immagina il panico se dovessi leggere un grande libro con tutte le parole inglesi del mondo in un ordine confuso! È lo stesso panico che un ingegnere subirà se i suoi dati non sono ordinati e strutturati.

Quindi, in breve, lo smistamento ci semplifica la vita. Dai un'occhiata ai nostri corsi di scienza dei dati per conoscere in modo approfondito gli algoritmi di scienza dei dati.

In questo post, ti guideremo attraverso le diverse strutture di dati e algoritmi di ordinamento. Ma prima, capiamo cos'è un algoritmo di ordinamento e l'ordinamento nella struttura dei dati.

Che cos'è un algoritmo di ordinamento?

Un algoritmo di ordinamento è solo una serie di ordini o istruzioni. In questo, un array è un input, su cui l'algoritmo di ordinamento esegue operazioni per fornire un array ordinato.

Molti bambini avrebbero imparato a ordinare le strutture di dati nelle loro classi di informatica. Viene introdotto in una fase iniziale per aiutare i bambini interessati a farsi un'idea di argomenti di informatica più profondi: metodi divide et impera, alberi binari, heap, ecc.

Ecco un esempio di cosa fa l'ordinamento.

Supponiamo di avere un array di stringhe: [h,j,k,i,n,m,o,l]

Ora, l'ordinamento produrrebbe un array di output in ordine alfabetico.

Output: [h,i,j,k,l,m,n,o]

Impariamo di più sull'ordinamento nella struttura dei dati.

Checkout: tipi di albero binario

Categorie di ordinamento

Esistono due diverse categorie nell'ordinamento:

• Ordinamento interno : se i dati di input sono tali da poter essere regolati nella memoria principale in una volta, si parla di ordinamento interno.
• Ordinamento esterno : se i dati di input sono tali da non poter essere regolati nella memoria completamente in una volta, è necessario archiviarli su un disco rigido, un floppy disk o qualsiasi altro dispositivo di archiviazione. Questo è chiamato ordinamento esterno.

Leggi: Idee e argomenti interessanti per progetti sulla struttura dei dati

Tipi di ordinamento nella struttura dei dati

Ecco alcuni dei tipi più comuni di algoritmi di ordinamento.

1. Unisci ordinamento

Questo algoritmo funziona sulla divisione di un array in due metà di dimensioni comparabili. Ciascuna metà viene quindi ordinata e unita nuovamente utilizzando la funzione merge().

Ecco come funziona l'algoritmo:

MergeSort(arr[], l, r)

Se r > l

1. Dividi l'array in due metà uguali individuando il punto centrale:

mezzo m = (l+r)/2

2. Usa la funzione mergeSort per chiamare la prima metà:

Chiama mergeSort(arr, l, m)

3. Chiama mergeOrdina per la seconda metà:

Chiama mergeSort(arr, m+1, r)

4. Utilizzare la funzione merge () per unire le due metà ordinate nei passaggi 2 e 3:

Chiama unione (arr, l, m, r)

Guarda l'immagine qui sotto per avere un quadro chiaro di come funziona.

Fonte

Programma Python per l'implementazione di merge sort

def mergeSort(a):

se len(a) >1:

medio = len(a)//2

A = a[:metà]

B = a[metà:]

mergeSort(A)

mergeSort(B)

io = j = k = 0

mentre i < len(A) e j < len(B):

se A[i] < B[j]:

a[k] = A[i]

io+=1

altro:

a[k] = B[j]

j+=1

k+=1

mentre io < len(A):

a[k] = A[i]

io+=1

k+=1

mentre j < len(R):

a[k] = B[j]

j+=1

k+=1

def printLista(a):

for i in range(len(a)):

print(a[i],end=” “)

Stampa()

if __name__ == '__main__':

a = [12, 11, 13, 5, 6, 7]

unisciOrdina(a)

print("L'array ordinato è: ", end="\n")

printList(a)

Ulteriori informazioni: ricorsione nella struttura dei dati: come funziona, tipi e quando utilizzato

2. Ordinamento per selezione

In questo, all'inizio, l'elemento più piccolo viene inviato alla prima posizione.

Quindi, l'elemento successivo più piccolo viene cercato nell'array rimanente e viene posizionato nella seconda posizione. Questo va avanti finché l'algoritmo non raggiunge l'elemento finale e lo posiziona nella giusta posizione.

Guarda l'immagine qui sotto per capirlo meglio.

Fonte

Programma Python per l'implementazione dell'ordinamento della selezione

importazione sist

X = [6, 25, 10, 28, 11]

per i nell'intervallo(len(X)):

min_idx = i

per j nell'intervallo(i+1, len(X)):

se X[min_idx] > X[j]:

min_idx = j

X[i], X[min_idx] = X[min_idx], X[i]

print ("L'array ordinato è")

per i nell'intervallo(len(X)):

print("%d" %X[i]),

Certificazione avanzata di data science, oltre 250 partner di assunzione, oltre 300 ore di apprendimento, 0% EMI

3. Ordinamento a bolle

È il più facile e semplice di tutti gli algoritmi di ordinamento. Funziona secondo il principio di scambiare ripetutamente gli elementi adiacenti nel caso non siano nell'ordine corretto.

In termini più semplici, se l'input deve essere ordinato in ordine crescente, l'ordinamento a bolle confronterà prima i primi due elementi nell'array. Nel caso in cui il secondo sia più piccolo del primo, scambierà i due e passerà all'elemento successivo e così via.

Esempio :

Ingresso : 637124

Primo passaggio

63 7124 -> 36 7124 : Bubble sort confronta 6 e 3 e li scambia perché 3<6.

3 67 124 -> 3 67 124 : Dal 6<7, nessuno scambio

36 71 24 -> 36 17 24 : scambiato 7 e 1, come 7>1

361 72 4 -> 361 27 4 : scambiato 2 e 7, come 2<7

3612 74 -> 3612 47 : scambiato 4 e 7, come 4<7

Secondo passaggio

36 1247 -> 36 1247

3 61 274 -> 3 16 274

31 62 74 -> 31 26 74

312 67 4 -> 312 67 4

3126 74 -> 3126 47

Terzo passaggio

31 2647 -> 13 2647

1 32 647 -> 1 23 647

12 36 47 -> 12 36 47

123 64 7 -> 123 46 7

1234 67 -> 1234 67

Come puoi vedere, otteniamo il risultato dell'ordine crescente dopo tre passaggi.

Programma Python per l'implementazione dell'ordinamento a bolle

def bubbleSort(a):

n = len(a)

per i nell'intervallo(n):

per j in range(0, ni-1):

se a[j] > a[j+1] :

a[j], a[j+1] = a[j+1], a[j]

a = [64, 34, 25, 12, 22, 11, 90]

bollaOrdina(a)

print ("L'array ordinato è:")

for i in range(len(a)):

stampa ("%d" %a[i]),

Leggi anche: Frame di dati in Python: tutorial approfondito su Python

Conclusione

Ciò racchiude l'ordinamento nella struttura dei dati e gli algoritmi di ordinamento più comuni. Puoi scegliere uno qualsiasi dei diversi tipi di algoritmi di ordinamento. Tuttavia, ricorda che per alcuni di questi può essere un po' noioso scrivere il programma. Ma poi, potrebbero tornare utili per risultati rapidi. D'altra parte, se si desidera ordinare set di dati di grandi dimensioni, è necessario scegliere l'ordinamento a bolle. Non solo fornisce risultati accurati, ma è anche facile da implementare. Poi di nuovo, è più lento degli altri tipi. Spero che l'articolo sull'ordinamento nella struttura dei dati ti sia piaciuto.

Per ottenere maggiori informazioni su come funziona lo smistamento, contattaci e ti aiuteremo a iniziare il corso più adatto alle tue esigenze!

Se sei curioso di conoscere la scienza dei dati, dai un'occhiata al programma Executive PG in Data Science di IIIT-B e upGrad, creato per i professionisti che lavorano e offre oltre 10 casi di studio e progetti, workshop pratici pratici, tutoraggio con esperti del settore, 1 -on-1 con mentori del settore, oltre 400 ore di apprendimento e assistenza al lavoro con le migliori aziende.

Divertiti a programmare!