Program C pentru sortarea cu bule: sortarea cu bule în C

Introducere

Sortarea unei matrice ocupă un loc de o importanță imensă în informatică. Utilitatea acestuia este observată atunci când este nevoie de aranjarea datelor într-o anumită ordine. Există diferite tipuri de algoritmi de sortare. Cel mai comun și utilizat algoritm de sortare este Bubble Sort.

Sortare cu bule în C

Tehnica folosită pentru sortarea în Bubble sort este simplă și ușor de înțeles. Tot ce face este să compare elementul curent cu următorul element și să-l schimbe dacă este mai mare sau mai mic, după cum este dictat de condiție. Algoritmul este foarte precis. De fiecare dată când un element este comparat cu alte elemente până când este găsit locul său, se numește trecere.

Acest algoritm este comparabil cu bulele din apă, deoarece filtrează partea superioară a bulelor asemănătoare matricei. Dintre toți algoritmii utilizați pentru sortare, sortarea cu bule este cea mai simplă și cea mai lentă cu complexitatea timpului de O(n^2). Cu toate acestea, algoritmul poate fi optimizat prin utilizarea unei variabile de tip flag care iese din buclă când schimbul este finalizat. Cel mai bun caz pentru sortarea cu bule poate fi O(n) atunci când matricea este sortată.

De exemplu, să luăm o matrice nesortată de cinci numere, așa cum este prezentat mai jos

13, 32,26, 34,9

Sortarea cu bule va începe să ia în considerare primele două elemente și le va compara pentru a verifica care dintre ele este mai mare. În acest caz, 32 este mai mare decât 13. Deci această porțiune este deja sortată în y. Apoi, comparăm 32 cu 26. Așadar, constatăm că 32 este mai mare decât 26, deci trebuie schimbate. Noua matrice va arăta ca

13, 26, 32, 34, 9

În continuare, comparăm 32 și 34. Știm că sunt deja sortate. Astfel, trecem la ultimele două variabile 34 și 9. Deoarece 34 este mai mare decât 9, acestea trebuie schimbate.

Schimbăm valorile și ajungem la sfârșitul matricei după prima iterație. Acum matricea va arăta ca

13, 26. 32,9,34

După a doua iterație, matricea va arăta ca

13, 26, 9,32,34

După a treia iterație, matricea va deveni

13,9,26,32,34

După a patra iterație, matricea va fi complet sortată

9, 13,26,32,34

Trebuie citit: Idei de proiecte în C

Algoritmul

Aici presupunem că tabloul are n elemente. În plus, presupunem că funcția de schimb de valori schimbă toate valorile pentru a face numerele matricei în ordine sortată.

porniți BubbleSort (matrice)

pentru toate elementele listei

dacă matrice[i]> matrice[i+1]

valori de schimb(matrice[i], matrice[i+1] )

sfârşitul dacă

sfârşitul pentru

matrice de returnare

final Bubble Sort

Citiți: Sortare în structura datelor: categorii și tipuri

Pseudo cod

Este evident în algoritmul de mai sus că există o comparație între fiecare pereche a elementului matrice până când întreaga matrice este sortată în ordine crescătoare. Poate duce la câteva probleme de complexitate, cum ar fi rezultatul algoritmului atunci când matricea este deja sortată în ordine crescătoare. Pentru a rezolva problema, vom folosi o variabilă de tip flag, care ne permite să vedem dacă a existat vreo schimbare. Dacă nu mai este nevoie de schimburi, vom ieși din bucla interioară.

Pseudocodul pentru algoritmul BubbleSort poate fi scris după cum urmează

procedura BubbleSort (matrice: elemente din matrice)

iterare= array.count;

pentru k=0 pentru a repeta-1 face:

steag= fals

pentru l=0 pentru a repeta-1 face:

dacă (matrice[l]> matrice[l+1]) atunci

valori de schimb (matrice[l], matrice [l+1])

steag=adevarat

sfârşitul dacă

sfârşitul pentru

Dacă (nu schimbat) atunci

Pauză

Încheiați dacă

Sfârșit pentru

Încheierea matricei de returnare a procedurii

Să încercăm un exemplu de program de sortare cu bule în C :

# include<stdio.h>

void principal

{

int matrice [10], i, j, num

pentru (i=0; i<=9; i++)

{

scanf(„%d”, &array[i])

}

pentru(i=0;i<=9;i++)

{

pentru(j=0;j<=9-i;j++)

{

dacă(matrice[j]>matrice[j+1])

{

num= matrice[j];

matrice[j]=matrice[j+1];

matrice[j+1]=num;

}

}

}

printf(„Matricea sortată este /n”);

pentru(i=0;i<=9;i++)

{

printf(„%d”,&array[i])

}

}

După cum se arată în exemplu, acest algoritm de sortare cu bule acceptă 10 numere de la utilizator și le stochează în matrice. În partea următoare, există două bucle pentru. Bucla exterioară rulează pentru valoarea I, egală cu zero cu mai puțin decât egal cu nouă. Funcția buclei exterioare este de a avea grijă de toate elementele valorii care trebuie comparate cu alte elemente.

Există o altă buclă în interiorul buclei exterioare. Pornește de la j=0 și rulează până când este mai mic sau egal cu opt. În interior, există o instrucțiune condițională if care compară și verifică dacă matricea[j] este mai mare decât matricea [j+1]. Dacă condiția este îndeplinită, valorile matricei[j] și ale matricei [j+1] sunt schimbate între ele.

În acest scop este folosită o variabilă cu numele num. Mai întâi matricea[j] este atribuită num, apoi matricea[j+1] este atribuită matricei[j], iar în final num este atribuită matricei[j+1]. Acest proces va continua până când toate elementele din matrice sunt sortate în ordine crescătoare. După aceea, matricea sortată este tipărită.

Implementarea optimizată a Bubble Sort

Avem un algoritm optimizat pentru sortarea cu bule pentru îmbunătățirea rezultatelor. Utilizarea unei variabile flag face optimizarea. Variabila flag va păstra 1 dacă există o schimbare, altfel va ieși din buclă. Mai jos este programul optimizat de sortare cu bule în C.

#include<stdio.h>

void principal

{

int array [10], i, j, num, flag=0;

pentru (i=0; i<=9; i++)

{

scanf(„%d”, &array[i])

}

pentru(i=0;i<=9;i++)

{

pentru(j=0;j<=9-i;j++)

{

dacă(matrice[j]>matrice[j+1])

{

num= matrice[j];

matrice[j]=matrice[j+1];

matrice[j+1]=num;

steag=1;

}

dacă(! steag)

{

pauză;

}

}

}

printf(„Matricea sortată este /n”);

pentru(i=0;i<=9;i++)

{

printf(„%d”,&array[i])

}

}

Programul dat se execută într-un mod similar cu programul normal de sortare cu bule. Singura modificare este utilizarea variabilei flag. Inițial, indicatorul este setat la 0. Cu toate acestea, dacă are loc o schimbare, indicatorul devine 1. Aceasta implică faptul că matricea necesită încă o verificare. Pe de altă parte, dacă indicatorul nu este 1, ceea ce înseamnă că schimbarea nu a avut loc, ieșim din bucla interioară, presupunând că tabloul este deja sortat. Odată executat, vom obține același rezultat ca sortarea normală Bubble.

Complexitatea timpului

Complexitatea timpului în cel mai bun caz pentru sortarea cu bule este O(n). Se întâmplă atunci când matricea este deja sortată. Cel mai rău caz este O(n*n) când matricea nu a fost sortată.

Citiți: Top 12 programe de model în Java pe care ar trebui să le verificați astăzi

Ce urmează?

Dacă sunteți interesat să aflați mai multe despre Java, dezvoltarea de software full-stack, consultați UpGrad & IIIT-B's PG Diploma in Full-stack Software Development, care este concepută pentru profesioniști care lucrează și oferă peste 500 de ore de formare riguroasă, peste 9 proiecte , și misiuni, statutul de absolvenți IIIT-B, proiecte practice practice și asistență pentru locuri de muncă cu firme de top.