Thuật toán Bubble Sort
Hôm nay chúng ta cùng tìm hiểu về thuật toán Bubble Sort.
1. Nguyên lý cơ bản của Bubble Sort
– Là một thuật toán đơn giản dễ hiểu và dễ thực hiện.
– Thực hiện việc kiểm tra so sánh sánh hai phần tử bên cạnh nhau, rồi hoán đổi vị trí cho nhau.
– Độ phức tạp của thuật toán là: O = N²
2 Thực hành.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
// Phattrienphanmem123az.com #include <iostream> #include <conio.h> using namespace std; void Swap(int& x, int& y) { int temp = x; x = y; y = temp; } void BubbleSort(int arr[], int n) { for (int i = 0; i < n-1; ++i) { bool swapped = false; for (int j = 0; j < n-i-1; ++j) { if (arr[j] > arr[j+1]) { Swap(arr[j], arr[j+1]); swapped = true; } } if (swapped == false) break; } } void Show(int arr[], int size) { for (int i=0; i < size; ++i) std::cout << arr[i] << " "; } int main() { int arr[] = {44, 36, 15, 12, 32, 10, 80}; int n = sizeof(arr)/sizeof(arr[0]); BubbleSort(arr, n); std::cout << "Sorted List: \n"; Show(arr, n); _getch(); return 0; } |
TPham