Bubble Sort đệ quy

#1

Đây là thuật toán Bubble Sort em viết bằng cách đệ quy (C++), không biết có sai sót gì không nữa…
Em muốn đóng góp code của mình và nếu có sai sót hay cần optimize thì mong các bác chỉ giáo cho em thêm ạ!! Thân ái <3

void BubbleSort(int arr[] ,int  low ,int  high) {
    int j  = high;
    while(arr[j - 1] < arr[j]) j--;
    if(arr[j - 1] > arr[j]) {
    if(arr[j - 2] > arr[j - 1]) Swap(arr[j - 2] , arr[j - 1]);
    Swap(arr[j - 1], arr[j]); 
    j--;
    }if(low >= high  - 1) return ;
    return BubbleSort(arr , low + 1, high);
}
#2
  1. Dùng thế nào, bạn có thể ví dụ code sử dụng không?
  2. Bạn có chạy test cases nào chưa?
3 Likes
#3

em có chạy test case là mảng cho sẵn và sau đó là tự input vô r ạ và đều chạy dc ạ, cho em hỏi là code này clean chưa ạ?

#4

code hoạt động kiểu này ạ:
Cho j = high , lặp nếu vị trí j lớn hơn vị trí j - 1 thì j sẽ giảm xuống;
Nếu vị trí j - 1 lớn hơn vị trí j thì sẽ xét tiếp xem tại vị trí j - 2 có lớn hơn j - 1 hay không (mục đích có j - 2 là để dồn phần tử bé nhất lên đầu mảng), nếu có thì Swap j - 2 và j - 1, nếu không thì chỉ swap j - 1 và j; Sau đó vì đã xét xong nên j sẽ giảm xuống. Hàm HĐ cho đến khi vị trí low >= vị trí high - 1 thì Kết thúc hàm, còn không thì gọi đệ quy

#5

Câu này là hỏi cách dùng hàm của bạn. Khi call hàm của bạn thì phải truyền vào thông số thế nào?
Nhìn BubbleSort(int arr[] ,int low ,int high) mình đâu biết truyền low, high bằng mấy đâu.

Câu này muốn bạn đưa ra các mẫu test cases của bạn, để đánh giá test cases của bạn có cover hết các trường hợp chưa. Đa số các hàm sẽ sai ở corner cases.

Về hình thức thì không được, vì format hàng này dính hàng kia, không có indent tốt.
Muốn đóng góp code thì còn thiếu: Hướng dẫn cách dùng hoặc mô tả hàm ở đầu hàm, thiếu comment.
Về nội dung thì mình không biết, đọc không hiểu code lắm :smiley:

4 Likes
#6

em đã thử test 2 case như này
arr = {3,5,2,1,4,6};
t n = sizeof(arr)/sizeof(arr[0]);

BubbleSort(arr , 0 , n - 1);

và case 2 là: em tự input mảng vào với các phần từ a[i] lần lượt là: 5,1,3,2,6
BubbleSort(arr , 0 , n - 1);
thì nó đều ra kq đúng anh ạ

#7

cả 2 thông số em đều test từ đầu => cuối mảng ạ, em ko biết còn 1 vaià corner cases nào nữa không ạ, nếu có anh chỉ em nhé

#8

em mới thử 1 case nữa là low từ đoạn 2 => n - 1 (n là độ lớn của mảng)
với arr[i] = 0,6,3,5,2

kq ra là 0 3 2 5 6. Em có test ra giấy thì thấy đúng, em ko biết em có test sai ko nữa anh coi giúpp em nhé… Em xem hết r mà vẫn ko dám chắc còn corner cases nào ko nữa

#9

Đoạn này:

Bạn viết vậy nhằm mục đích gì nhỉ?

1 Like
#10

dạ em cảm ơn ạ <3 để em thêm và chỉnh sửa ạ

#11

dạ để đẩy phần tử nhỏ nhất xuống đầu mảng ạ
vì nếu ko có thì phần tử nhỏ nhất sẽ chỉ dồn dc đến vị trí arr[1] chứ không phải arr[0]

#12

Cho bạn vài test case:

{}
{0}
{1,1}
{1,2,1}
{9, 8, 7, 4, 1, 0, 0}
{9, 8, 7, 4, 1, 0, 0, 8}
{2, 2, 1, 3, 3, 3, 5, 4}
4 Likes
#13

Dạ vâng em cảm ơn, em sẽ test thử ạ em cảm ơn nhiều ạ !!

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?