01/10/2018, 10:25

Thuật toán merge sort không sort được mảng

void merge(int* arr, int  left, int mid, int right){
	int n1 = mid - left + 1;//số lượng phần tử của mảng trái
	int n2 = right - mid;	// số lượng phần tử của mảng phải
	int tmp1[n1], tmp2[n2];
	int i = 0, j = mid + 1;
	
	while(i < n1){
		tmp1[i] = arr[i];
		i++;
	}
	
	i = 0;	
	while(i < n2){
		tmp2[i] = arr[j + i];
		i++;
	}
	
	i = 0, j = 0;
	int count = 0;//số lượng phần tử của mảng chính

	while(i < n1 && j < n2){
		if(tmp1[i] > tmp2[j]){
			arr[count] = tmp2[j];
			j++;
		}
		else{
			arr[count] = tmp1[i];
			i++;
		}
		count++;
	}	
	
	while(i < n1){
		arr[count] = tmp1[i];
		i++;
		count++;
	}
	
	while( j < n2){
		arr[count] = tmp2[j];
		j++;
		count++;
	}
}

void mergesort(int* arr, int left, int right){
        int mid = (left + right) / 2;
	if(left < right){
		mergesort(arr, left, mid);
		mergesort(arr, mid + 1, right);
		merge(arr, left, mid, left);
	}
}

đây là code Merge sort. Các anh có thể fix dùm em lỗi không ví dụ arr[5] = {2, 1, 5, 4, 3}; chạy trên ubuntu thì vẫn trả về 2 1 5 4 3 còn qua windows chạy visual debug thì nó nói mảng tmp1, tmp2 không có số phần tử xác định? không biết code em có sai gì không mong đc sự giúp đỡ!

HK boy viết 12:36 ngày 01/10/2018

merge(arr, left, mid, left);

Chỗ này sai nè. Phải là merge(arr, left, mid, right) chứ.

Góp ý: Không cần để mid làm tham trị. Có thể gán mid = (right + left) / 2 ở trong void merge().

nghia viết 12:34 ngày 01/10/2018

Ok anh! em fix thì nó vẫn còn sai giải thuật phiền anh có thể tìm lỗi sai đc không! giải khi em qua merge sort khi fix lại là: 1 3 4 3 5

HK boy viết 12:40 ngày 01/10/2018

j = mid + 1;

while(i < n1){
	tmp1[i] = arr[i];
	i++;
}

i = 0;	
while(i < n2){
	tmp2[i] = arr[j + i];
	i++;
}

Bạn đọc đoạn này sẽ thấy bạn không cần phải gán tmp2[i] = arr[j + i] mà bạn gán thẳng vào arr[j] luôn, và nhớ tăng j.

Góp ý: Đoạn code mình vừa quote của bạn hơi khó nhìn một chút, bạn có thể cải tiến mà không cần dùng while với nhiều biến phức tạp:

for (int i = left; i <= right; i++)
    if (i <= mid)
        tmp1[i - left] = arr[i];
    else
        tmp2[i - mid - 1] = arr[i];

nghia viết 12:36 ngày 01/10/2018

em tìm ra lỗi sai rồi anh lỗi rất nhiều cảm ơn anh!

Bình luận về bài viết này

Chia sẻ tin đăng đến bạn bè

Gửi Messenger

Bài liên quan

nghia

0 chủ đề

0 bài viết

Tác giả nổi bật

Từ khóa nổi bật

AngularJS Blog Bootstrap C / C++ Cấu trúc dữ liệu & Giải thuật Cơ sở dữ liệu Codeigniter Công cụ lập trình CSS CSS cơ bản CSS3 Học Excel HTML HTML cơ bản HTML5 Java Javascript jQuery Json Lập trình mobile Laravel Linux MongoDB MySQL NodeJS Oracle Pascal PHP PHP cơ bản PHP nâng cao Python React Native ReactJS Ruby SEO SQL Server Swift Visual Basic VueJS WordPress XML

Chủ đề nổi bật

Thuật toán merge sort không sort được mảng

Đăng ký nhận thông báo

HỖ TRỢ HỌC VIÊN

VỀ CODE24H

HỢP TÁC VÀ LIÊN KẾT

KẾT NỐI VỚI CHÚNG TÔI

TẢI ỨNG DỤNG TRÊN ĐIỆN THOẠI