Sortare cu bule este un algoritm de sortare simplu și intuitiv. Schimbă în mod repetat elementele adiacente dacă acestea sunt în ordinea greșită până când matricea este sortată. În acest algoritm, cel mai mare element „bulbează” până la sfârșitul matricei în fiecare iterație. Sortarea cu bule este ineficientă pentru seturi mari de date, dar este utilă în scopuri educaționale și seturi mici de date. În acest articol, vom implementa algoritmul de sortare cu bule în limbajul de programare C.
Primul pas este definirea funcției de sortare cu bule. Această funcție ia ca parametri un tablou întreg și dimensiunea matricei. Funcția nu returnează nimic deoarece modifică tabloul original. Aici este definiția funcției:
automate finite deterministe
void bubble_sort(int arr[], int n) { int i, j; for (i = 0; i <n - 1; i++) { for (j="0;" j <n i j++) if (arr[j]> arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } </n> Funcția are două bucle. Bucla exterioară rulează de la primul element până la ultimul element al matricei. Bucla interioară se desfășoară de la primul element până la ultimul element al părții nesortate a matricei. Condiția buclei interioare este n - i - 1 deoarece ultimele i elemente ale matricei sunt deja sortate.
În fiecare iterație a buclei interioare, comparăm elementele adiacente. Dacă elementul din stânga este mai mare decât elementul din dreapta, le schimbăm. După finalizarea buclei interioare, se garantează că cel mai mare element se află la sfârșitul părții nesortate a matricei.
Acum, putem scrie funcția principală pentru a testa implementarea noastră de sortare cu bule. Iată funcția principală împreună cu partea anterioară:
Programul C:
#include void bubble_sort(int arr[], int n) { int i, j; for (i = 0; i <n - 1; i++) { for (j="0;" j <n i j++) if (arr[j]> arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } int main() { int arr[] = {64, 34, 25, 12, 22, 11, 90}; int n = sizeof(arr) / sizeof(arr[0]); bubble_sort(arr, n); printf('Sorted array: '); for (int i = 0; i <n; i++) { printf('%d ', arr[i]); } return 0; < pre> <p>The main function creates an integer array arr of size 7 and initializes it with random numbers. We then calculate the size of the array by dividing the size of the array by the size of an integer element. Next, we call the bubble_sort function to sort the array. Finally, we print the sorted array using a for loop.</p> <p> <strong>When we run the program, we should see the following output:</strong> </p> <pre> Sorted array: 11 12 22 25 34 64 90 </pre> <p>This output shows that our bubble sort implementation correctly sorted the array in ascending order.</p> <p>To run the program, we need to compile it using a C compiler. Here is an example <strong>compilation command for GCC:</strong> </p> <pre> gcc -o bubble_sort bubble_sort.c </pre> <p>This command compiles the bubble_sort.c file and produces an executable file named bubble_sort.</p> <p>In summary, the bubble sort algorithm repeatedly swaps adjacent elements until the array is sorted. The algorithm has a time complexity of O(n<sup>2</sup>), which makes it inefficient for large data sets. However, it is useful for educational purposes and small data sets. We implemented the bubble sort algorithm in C programming language and tested it using a simple example.</p> <h3>Characteristics:</h3> <ul> <li>Bubble sort is a simple sorting algorithm.</li> <li>It works by repeatedly swapping adjacent elements if they are in the wrong order.</li> <li>The algorithm sorts the array in ascending or descending order.</li> <li>It has a time complexity of O(n<sup>2</sup>) in the worst case, where n is the size of the array.</li> </ul> <h3>Usage:</h3> <ul> <li>Bubble sort is useful for educational purposes and small data sets.</li> <li>It is not suitable for large data sets because of its time complexity.</li> </ul> <h3>Advantages:</h3> <ul> <li>Bubble sort is easy to understand and implement.</li> <li>It requires minimal additional memory space to perform the sorting.</li> </ul> <h3>Disadvantages:</h3> <ul> <li>It is not efficient for large data sets because of its time complexity.</li> <li>It has poor performance compared to other sorting algorithms, such as quicksort and mergesort.</li> </ul> <h2>Conclusion:</h2> <p>Bubble sort is a simple and intuitive sorting algorithm that is useful for educational purposes and small data sets. However, its time complexity makes it inefficient for large data sets. Therefore, it is not commonly used in real-world applications. Other sorting algorithms, such as quicksort and mergesort, are more efficient for large data sets.</p> <hr></n;></n> Această ieșire arată că implementarea noastră de sortare cu bule a sortat corect matricea în ordine crescătoare.
Pentru a rula programul, trebuie să-l compilam folosind un compilator C. Iată un exemplu comandă de compilare pentru GCC:
gcc -o bubble_sort bubble_sort.c
Această comandă compilează fișierul bubble_sort.c și produce un fișier executabil numit bubble_sort.
În rezumat, algoritmul de sortare cu bule schimbă în mod repetat elementele adiacente până când matricea este sortată. Algoritmul are o complexitate de timp de O(n2), ceea ce îl face ineficient pentru seturi mari de date. Cu toate acestea, este util pentru scopuri educaționale și seturi mici de date. Am implementat algoritmul de sortare cu bule în limbajul de programare C și l-am testat folosind un exemplu simplu.
Caracteristici:
- Bubble sort este un algoritm simplu de sortare.
- Funcționează schimbând în mod repetat elementele adiacente dacă acestea sunt în ordinea greșită.
- Algoritmul sortează matricea în ordine crescătoare sau descrescătoare.
- Are o complexitate de timp de O(n2) în cel mai rău caz, unde n este dimensiunea matricei.
Utilizare:
- Sortarea cu bule este utilă în scopuri educaționale și în seturi mici de date.
- Nu este potrivit pentru seturi mari de date din cauza complexității sale de timp.
Avantaje:
- Sortarea cu bule este ușor de înțeles și implementat.
- Este nevoie de un spațiu de memorie suplimentar minim pentru a efectua sortarea.
Dezavantaje:
- Nu este eficient pentru seturi mari de date din cauza complexității sale de timp.
- Are performanțe slabe în comparație cu alți algoritmi de sortare, cum ar fi sortare rapidă și sortare de mers.
Concluzie:
Bubble sort este un algoritm de sortare simplu și intuitiv, care este util în scopuri educaționale și seturi mici de date. Cu toate acestea, complexitatea timpului îl face ineficient pentru seturi mari de date. Prin urmare, nu este utilizat în mod obișnuit în aplicațiile din lumea reală. Alți algoritmi de sortare, cum ar fi quicksort și mergesort, sunt mai eficienți pentru seturi mari de date.