Cum se implementează sortarea selecției în C?

Selecția Sort este un alt algoritm care funcționează prin localizarea celui mai mic număr întreg al matricei și apoi atribuirea acestuia la poziția de sus. Indexul de lângă poziția celui mai mic întreg va fi folosit pentru a începe următoarea matrice care trebuie scanată.

Exemplu de sortare a selecției în C

Dacă luăm o matrice cu numere [10,2,8,4,6] în care cel mai mic număr este 2. Astfel, vom plasa cel mai mic număr, care este 2, în prima poziție, după care tabloul va arăta ca [2,10,8,4,6]. În continuare, vom lua următorul cel mai mic număr, deoarece 2 este deja în poziția corectă acum. Următorul cel mai mic număr este 4, care va fi plasat în a doua poziție, după care matricea va fi căutată în mod similar până când este în final sortată.

Sortarea de selecție în C sortează numerele în ordine crescătoare. Prin modificarea algoritmului, numerele pot fi aranjate într-o sortare de selecție descendentă poate fi efectuată și în alte limbi în afară de C, cum ar fi Selection Sort C++ sau Selection Sort Python.

Învață cursuri de dezvoltare software online de la cele mai bune universități din lume. Câștigați programe Executive PG, programe avansate de certificat sau programe de master pentru a vă accelera cariera.

Algoritmul de sortare a selecției

• Mai întâi, setăm elementul inițial din sortarea selecției să fie minim și căutăm cel mai mic element din matrice pentru procedura corectă a algoritmului de sortare a selecției .
• Elementul minim este acum comparat cu a doua componentă. Dacă al doilea element scade sub minimul, le vom schimba și apoi îi vom atribui celui de-al treilea element o valoare minimă.
• În caz contrar, vom continua cu cel de-al treilea element și îl vom compara cu minimul. Dacă al doilea element depășește primul nostru element, îl vom schimba. Repetați acest proces până la ultima componentă.
• După fiecare iterație, vom vedea că minimul nostru a ajuns la începutul listei nesortate.
• Vom începe indexarea de la prima intrare a listei nesortate pentru fiecare iterație. Până când lista este sortată sau toate componentele sunt poziționate corespunzător, vom repeta pașii de la 1 la 4 de mai multe ori.

Cursuri populare și articole despre inginerie software

Următorul exemplu cu fiecare iterație va ajuta la înțelegerea procesului de sortare a selecției în C în detaliu –

Iterația #1

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

Setați un minim – 8

Comparați i 0 și i 1

Ca, i 0 > i 1 , setați minim = 5.

• Comparați i 1 și i 2

Deoarece i 1 > i 2 , setați minim = 2.

• Comparați i 2 și i 3

Ca, i 2 < i 3 , setați minim= 2.

• Comparați i 2 și i 4

După cum, i 2 < i 4 , setați minim =2.

2 este cel mai mic număr dintre toate elementele, trebuie să schimbăm i 0 și i 2

­ Iterația #2

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

Setați minim 5

• Comparați i 1 și i 2

Deoarece i 1 < i 2 , setați minim = 5.

• Comparați i 1 și i 3

Ca i 1 < i 3, setați minim = 5

• Comparați i 1 și i 4

Din nou, i 1 < i 4 , setați minim = 4.

4 este cel mai mic element din tablou, prin urmare, trebuie să schimbăm i 1 și i 4 .

Iterația #3

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

Setați minim 8

• Comparați i 2 și i 3

Deoarece i 2 > i 3 , setați minim = 6.

• Comparați i 3 și i 4

Deoarece i 3 > i 4 , setați minim = 5.

5 este cel mai mic element din matrice, trebuie să schimbați i 2 și i 4 .

Iterația #4

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

Setați minim 6

• Comparați i 3 și i 4

Ca i 3 < i 4 , setați minim = 6.

Minimul este plasat în locul corect; astfel, nu va avea loc nicio schimbare.

Exemplu de sortare a selecției în C

// Sortare selecție în C

#include <stdio.h>

// funcția de a schimba poziția a două elemente

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

int temp = *a;

*a = *b;

*b = temperatură;

}

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

pentru (int pas = 0; pas < dimensiune – 1; pas++) {

int min_idx = pas;

pentru (int i = pas + 1; i < dimensiune; i++) {

// Pentru a sorta în ordine descrescătoare, schimbați > în < în această linie.

// Selectați elementul minim în fiecare buclă.

dacă (matrice[i] < matrice[min_idx])

min_idx = i;

}

// pune min în poziția corectă

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

}

}

// funcția de tipărire a unui tablou

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

pentru (int i = 0; i < dimensiune; ++i) {

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

}

printf(“\n”);

}

// codul driverului

int main() {

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

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

selectieSort(date, dimensiune);

printf(„Matrice sortată în ordinea de trimitere:\n”);

printArray(date, dimensiune);

}

Analiza complexității sortării selecției

Intrare – sunt date n elemente de intrare.

Ieșire – Numărul de pași care sunt necesari pentru sortarea listei.

Logica – Dacă ni se dau n itemi, se va face n-1 comparații în prima trecere, n-2 comparații în a doua trecere, n-3 comparații în a treia trecere și așa mai departe. În consecință, numărul total de comparații poate fi calculat folosind;

Ieșire -

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

Suma = n(n-1)/2 adică O(n²)

Deoarece metoda de sortare prin selecție are nevoie de spațiu de memorie suplimentar pentru variabilele temporare pentru schimbare, are o complexitate de timp de O(n2) și o complexitate de spațiu de O(1).

Analiza complexității timpului de sortare a selecției

Cel mai bun caz: pentru matricea care a fost sortată anterior, metoda de sortare prin selecție are o complexitate de timp în cel mai bun caz de O(n²).

Cazul mediu: algoritmul de sortare a selecției are o complexitate de timp medie a cazului de O(n²) atunci când elementele sunt aranjate amestecate, adică nici în ordine crescătoare, nici în ordine descrescătoare.

Cel mai rău caz: când inversăm ordinea descendentă a unui tablou în ordinea crescătoare, complexitatea timpului în cel mai rău caz este O(n²).

Complexitatea temporală a metodei de sortare prin selecție este O(n²) în fiecare dintre cele trei scenarii. Acest lucru se datorează faptului că trebuie să identificăm elementele minime stricte pentru fiecare etapă pentru a le aranja corect. După urmărirea întregii matrice, vom fi găsit elementul nostru minim.

Concluzie

Acest lucru duce la încheierea postării de blog despre „Selection Sort In C”. Trebuie să înțelegeți că poate fi efectuat și în alte limbi, cum ar fi Selection Sort C++ și Selection Sort Python. Sperăm că acest articol vă va ajuta să înțelegeți cum să sortați elementele în C.

Sortarea selecției nu este singurul segment din călătoria de a deveni programator. Dacă sperați să obțineți un impuls semnificativ pentru cariera dvs. de dezvoltare de software cu o diplomă profesională, upGrad este aici! Dezvoltarea frontend a upGrad (JavaScript, HTML, CSS), backend (NoSQL-MongoDB) și microservicii, apoi puteți urma cursul de Master în Științe Informatice al UpGrad. Livrat de IIIT Bangalore și LJMU Alumni Status, acest curs vă ajută să vă obțineți cariera ca inginer software/dezvoltator full-stack cu giganții tehnologici din întreaga lume.

Acest curs acoperă cunoștințele de bază despre instrumente precum Java, Spring și Hibernate, consolidându-ne abilitățile de dezvoltare full-stack pentru a explora piața muncii cu oportunități remarcabile.

Înscrie-te pentru a afla mai multe!