30/09/2018, 16:04

[Wiki] Sort cơ bản 2 - Merge Sort - Sắp xếp trộn

Tiếp theo với Merge sort.

vi.wikipedia.org

Sắp xếp trộn

Trong khoa học máy tính, sắp xếp trộn (merge sort) là một thuật toán sắp xếp để sắp xếp các danh sách (hoặc bất kỳ cấu trúc dữ liệu nào có thể truy cập tuần tự, v.d. luồng tập tin) theo một trật tự nào đó. Nó được xếp vào thể loại sắp xếp so sánh. Thuật toán này là một ví dụ tương đối điển hình của lối thuật toán chia để trị do John von Neumann đưa ra lần đầu năm 1945. Một thuật toán chi tiết được Goldstine và Neumann đưa ra năm 1948. Giả sử có hai danh sách đã được sắp xếp ...

Coi video này để lấy ý tưởng về Merge sort

Code lại bằng C++ [Code by @minh_vu_03]

#include <iostream>
using namespace std;

void merge(int* array,int left,int mid,int right)	{
	
	int temp1[mid-left+1];
	int temp2[right-mid];
	int index_array = left;
	
	for(int i = 0; i < mid-left+1; i++)
		temp1[i] = array[index_array++];
		
	for(int i = 0; i < right - mid; i++)
		temp2[i] = array[index_array++];
		
	int index_temp1 = 0,index_temp2 = 0;
	index_array = left;
	
	while(index_temp1 <= mid - left && index_temp2 < right - mid)	{
		
		if(temp1[index_temp1] < temp2[index_temp2]) 	{
			
			array[index_array] = temp1[index_temp1];
			index_temp1++;
		}
		else	{
			
			array[index_array] = temp2[index_temp2];
			index_temp2++;
		}
		index_array++;
	}
	
	while(index_temp1 <= mid - left)	{
		
		array[index_array] = temp1[index_temp1];
		index_array++;
		index_temp1++;
	}
	
	while(index_temp2 < right - mid)	{
		
		array[index_array] = temp2[index_temp2];
		index_array++;
		index_temp2++;
	}
}

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

int main() {
	
	int array[] = { 9,8,7,6,5,4,3,2,1 };
	int n = sizeof(array)/sizeof(array[0]);
	
	merge_sort(array,0,n-1);
	
	cout << n << endl;
	
	for(int i = 0; i < n; i++)
		cout << array[i] << " ";
	
	return 0;
}

Độ phức tạp

Thời gian chạy: O(nlogn)
Bộ nhớ: N
viết 18:12 ngày 30/09/2018

Em cũng code lại phát kẻo lâu ngày quên:

#include <iostream>
using namespace std;

void merge(int* array,int left,int mid,int right)	{
	
	int temp1[mid-left+1];
	int temp2[right-mid];
	int index_array = left;
	
	for(int i = 0; i < mid-left+1; i++)
		temp1[i] = array[index_array++];
		
	for(int i = 0; i < right - mid; i++)
		temp2[i] = array[index_array++];
		
	int index_temp1 = 0,index_temp2 = 0;
	index_array = left;
	
	while(index_temp1 <= mid - left && index_temp2 < right - mid)	{
		
		if(temp1[index_temp1] < temp2[index_temp2]) 	{
			
			array[index_array] = temp1[index_temp1];
			index_temp1++;
		}
		else	{
			
			array[index_array] = temp2[index_temp2];
			index_temp2++;
		}
		index_array++;
	}
	
	while(index_temp1 <= mid - left)	{
		
		array[index_array] = temp1[index_temp1];
		index_array++;
		index_temp1++;
	}
	
	while(index_temp2 < right - mid)	{
		
		array[index_array] = temp2[index_temp2];
		index_array++;
		index_temp2++;
	}
}

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

int main() {
	
	int array[] = { 9,8,7,6,5,4,3,2,1 };
	int n = sizeof(array)/sizeof(array[0]);
	
	merge_sort(array,0,n-1);
	
	cout << n << endl;
	
	for(int i = 0; i < n; i++)
		cout << array[i] << " ";
	
	return 0;
}
Nguyễn Minh Dũng viết 18:16 ngày 30/09/2018

Ai test dùm code @minh_vu_03 viết rồi sửa post 1 bỏ vào phần code luôn đi

Nguyễn Minh Dũng viết 18:20 ngày 30/09/2018

I moved 2 posts to a new topic: [Wiki] Sort cơ bản 3 - Quick Sort

Nguyễn Minh Dũng viết 18:21 ngày 30/09/2018

Em cập nhật lại độ phức tạp nhé @minh_vu_03

viết 18:16 ngày 30/09/2018

Em đã học độ phức tạp gì đâu. Nghe người ta nói vậy em bắt chước nói theo thế thôi

Nguyễn Minh Dũng viết 18:05 ngày 30/09/2018

@Gio đã cập nhật rồi. Cảm ơn @minh_vu_03 và @Gio nhé

Đạt ủng hộ video
@Gio cho cái độ phức tạp
@minh_vu_03 cho cái code

Phối hợp rất nhịp nhàng, để đi tìm vài cái videos nữa :trollface: Công việc tìm videos khá là cực nhọc =))

TTmagic viết 18:16 ngày 30/09/2018

void merge(int* array,int left,int mid,int right) {

int temp1[mid-left+1];
int temp2[right-mid];
int index_array = left;

đoạn này mấy biến mid right left nó báo lỗi expression must have a constant value a @ltd ơi

Nguyễn Minh Dũng viết 18:06 ngày 30/09/2018

@nguyenchiemminhvu Please help

... viết 18:06 ngày 30/09/2018
Ideone.com

Ideone.com

Ideone is something more than a pastebin; it's an online compiler and debugging tool which allows to compile and run code online in more than 40 programming languages.

Ở trang ideone.com mình run bằng C++14 và C++4.9.2 vẫn chạy được bình thường. Chắc do IDE nó yêu cầu

Nếu thế thì gán biểu thức mid - left + 1 với right - mid bằng 1 biến nào đó xem thử.

TTmagic viết 18:20 ngày 30/09/2018

Ở trang ideone.com mình run bằng C++14 và C++4.9.2 vẫn chạy được bình thường. Chắc do IDE nó yêu cầu

Nếu thế thì gán biểu thức mid - left + 1 với right - mid bằng 1 biến nào đó xem thử.

cho nó bằng 1 số cụ thể thì chạy ngon. Nhưng mà mình tưởng mảng 2 chiều mới phải khai báo thêm 1 chiều chứ sao mảng 1 chiều nó cũng báo lỗi nhỉ @@

... viết 18:19 ngày 30/09/2018

cho nó bằng 1 số cụ thể thì chạy ngon.

Đúng rồi chứ sao nữa. Mình nhát làm kiểu nhập n từ bàn phím nên bỏ số vô làm luôn cho lẹ thôi

Bài liên quan
0