Độ phức tạp:
Trường hợp tốt nhất: O(n)
Trường hợp trung bình: O(n2)
Trường hợp xấu nhất: O(n2)
Thuật toán
- Input: Mảng arr gồm n phần tử không có thứ tự
- Output: Mảng arr gồm n phần tử có thự tự (trong trường hợp này là thứ tự tăng dần)
Mã giả
Function bubble_sort (array arr, integer arr_size) { integer i; for i from 1 to arr_size do { integer j; for j from 2 to arr_size do { if arr[j - 1] > arr[j] then { swap(arr[j - 1], arr[j]); } } } return arr; } Function swap(integer a, integer b) { integer temp = a; a = b; b = temp; }
C++ code
void bubble_sort(int arr[], int arr_size) { for(int i = 0; i < arr_size; i++) { bool stop = true; for(int j = 1; j < arr_size; j ++) { if(arr[j - 1] > arr[j]) { stop = false; swap(arr[j - 1], arr[j]); } } if(stop) break; } }
No comments:
Post a Comment