Come implementare l'ordinamento della selezione in C?

La selezione Sort è un altro algoritmo che opera individuando il numero intero più basso dell'array e quindi assegnandolo alla posizione più alta. L'indice accanto alla posizione del numero intero più piccolo verrà utilizzato per iniziare il seguente array che deve essere scansionato.

Esempio di ordinamento della selezione in C

Se prendiamo un array con numeri [10,2,8,4,6] in cui il numero più piccolo è 2. Pertanto, posizioneremo il numero più piccolo, che è 2, nella prima posizione, dopodiché l'array apparirà come [2,10,8,4,6]. Successivamente, prenderemo il numero più piccolo successivo perché 2 è già nella sua posizione corretta ora. Il successivo numero più piccolo è 4, che verrà inserito nella seconda posizione, dopodiché l'array verrà cercato in modo simile fino a quando non sarà finalmente ordinato.

L'ordinamento della selezione in C ordina i numeri in ordine crescente. Modificando l'algoritmo, i numeri possono essere disposti in un ordine discendente Selection Sort può essere eseguito anche in altri linguaggi oltre a C, come Selection Sort C++ o Selection Sort Python.

Impara i corsi di sviluppo software online dalle migliori università del mondo. Guadagna programmi Executive PG, programmi di certificazione avanzata o programmi di master per accelerare la tua carriera.

Algoritmo di ordinamento della selezione

• Per prima cosa, impostiamo l'elemento iniziale nell'ordinamento di selezione come minimo e cerchiamo l'elemento più piccolo nell'array per la procedura corretta dell'algoritmo di ordinamento della selezione .
• L'elemento minimo viene ora confrontato con il secondo componente. Se il secondo elemento scende al di sotto del minimo, li scambieremo e quindi assegneremo al terzo elemento un valore minimo.
• Altrimenti, continueremo con il terzo elemento e lo confronteremo con il minimo. Se il secondo elemento supera il nostro primo elemento, lo scambieremo. Ripetere questo processo fino all'ultimo componente.
• Dopo ogni iterazione, vedremo che il nostro minimo è arrivato all'inizio dell'elenco non ordinato.
• Inizieremo l'indicizzazione dalla prima voce dell'elenco non ordinato per ogni iterazione. Fino a quando l'elenco non sarà ordinato o tutti i componenti non saranno opportunamente posizionati, ripeteremo più volte i passaggi da 1 a 4.

Corsi e articoli popolari sull'ingegneria del software

Il seguente esempio con ogni iterazione aiuterà a comprendere in dettaglio il processo di ordinamento della selezione in C–

Iterazione #1

Io [ ] = 8,5,2,6,4

Imposta un minimo - 8

Confronta i 0 e i 1

Come, i 0 > i 1 , poniamo il minimo = 5.

• Confronta i1 e i2

Come, i 1 > i 2 , poni il minimo = 2.

• Confronta i2 e i3

Come, i 2 < i 3 , poniamo minimo= 2.

• Confronta i2 e i4

Come, i 2 < i 4 , poniamo minimo =2.

2 è il numero più piccolo di tutti gli elementi, dobbiamo scambiare i 0 e i 2

­ Iterazione #2

Io [ ]= 2,5,8,6,4

Imposta minimo 5

• Confronta i1 e i2

Come, i 1 < i 2 , poniamo il minimo = 5.

• Confronta i 1 e i 3

Poiché i 1 < i 3, poniamo minimo = 5

• Confronta i 1 e i 4

Di nuovo, i 1 < i 4 , poniamo minimo = 4.

4 è l'elemento più piccolo dell'array, quindi dobbiamo scambiare i 1 e i 4 .

Iterazione #3

Io [ ]= 2,4,8,6,5

Imposta minimo 8

• Confronta i2 e i3

Come, i 2 > i 3 , poniamo il minimo = 6.

• Confronta i3 e i4

Come, i 3 > i 4 , poniamo il minimo = 5.

5 è l'elemento più piccolo dell'array, devi scambiare i 2 e i 4 .

Iterazione #4

Io [ ] = 2,4,5,6,8

Imposta minimo 6

• Confronta i3 e i4

Poiché i 3 < i 4 , poniamo minimo = 6.

Il minimo è posto al posto giusto; pertanto, non si verificherà alcuno scambio.

Esempio di ordinamento della selezione in C

// Ordina la selezione in C

#include <stdio.h>

// funzione per scambiare la posizione di due elementi

void scambio(int *a, int *b) {

int temp = *a;

*a = *b;

*b = temperatura;

}

void selectionSort(int array[], int size) {

for (int step = 0; step < size – 1; step++) {

int min_idx = passo;

for (int i = passo + 1; i < dimensione; i++) {

// Per ordinare in ordine decrescente, cambia > in < in questa riga.

// Seleziona l'elemento minimo in ogni ciclo.

if (array[i] < array[min_idx])

min_idx = io;

}

// metti min nella posizione corretta

swap(&array[min_idx], &array[passo]);

}

}

// funzione per stampare un array

void printArray(int array[], int dimensione) {

for (int i = 0; i < dimensione; ++i) {

printf(“%d “, matrice[i]);

}

printf(“\n”);

}

// codice conducente

int main() {

int dati[] = {20, 12, 10, 15, 2};

int size = sizeof(data) / sizeof(data[0]);

selectionSort(dati, dimensioni);

printf("Array ordinato in ordine crescente:\n");

printArray(dati, dimensioni);

}

Analisi della complessità dell'ordinamento della selezione

Input: vengono forniti n elementi di input.

Output: il numero di passaggi necessari per ordinare l'elenco.

Logica: se ci vengono forniti n elementi, effettuerà n-1 confronti nel primo passaggio, n-2 confronti nel secondo passaggio, n-3 confronti nel terzo passaggio e così via. Di conseguenza, il numero totale di confronti può essere calcolato utilizzando il;

Produzione -

(n+1) + (n+2) + (n+3) + (n+4) + …. +1

Somma = n(n-1)/2 cioè, O(n²)

Poiché il metodo di ordinamento della selezione necessita di spazio di memoria aggiuntivo per le variabili temporanee per lo scambio, ha una complessità temporale di O(n2) e una complessità spaziale di O(1).

Analisi della complessità temporale dell'ordinamento della selezione

Caso migliore: per l'array precedentemente ordinato, il metodo di ordinamento per selezione ha una complessità temporale nel caso migliore di O(n²).

Caso medio: l'algoritmo di ordinamento della selezione ha una complessità temporale del caso medio di O(n²) quando gli elementi sono disposti in modo confuso, ovvero né in ordine crescente né in ordine decrescente.

Caso peggiore: quando invertiamo l'ordine discendente di un array nel suo ordine ascendente, la complessità temporale nel caso peggiore è O(n²).

La complessità temporale del metodo di ordinamento della selezione è O(n²) in ciascuno dei tre scenari. Ciò è dovuto al fatto che dobbiamo identificare gli elementi minimi indispensabili per ogni fase al fine di organizzarli correttamente. Dopo aver tracciato l'intero array, avremo trovato il nostro elemento minimo.

Conclusione

Questo conclude il post del blog su "Selection Sort In C". Devi capire che può essere eseguito anche in altri linguaggi, come Selection Sort C++ e Selection Sort Python. Speriamo che questo articolo ti aiuti a capire come ordinare gli elementi in C.

L'ordinamento della selezione non è l'unico segmento nel viaggio per diventare un programmatore. Se speri di ottenere una spinta significativa alla tua carriera di sviluppatore software con una laurea professionale, upGrad è qui! upGrad's frontend development (JavaScript, HTML, CSS), backend (NoSQL-MongoDB) e microservizi, allora puoi seguire il corso di Master of Science in Computer Science di UpGrad. Offerto da IIIT Bangalore e LJMU Alumni Status, questo corso ti aiuta a intraprendere la tua carriera come ingegnere del software / sviluppatore full-stack con i giganti della tecnologia di tutto il mondo.

Questo corso copre la conoscenza di base di strumenti come Java, Spring e Hibernate, rafforzando le nostre capacità di sviluppo full-stack per esplorare il mercato del lavoro con notevoli opportunità.

Iscriviti per saperne di più!