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.
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
Bài liên quan
Em cũng code lại phát kẻo lâu ngày quên:
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
I moved 2 posts to a new topic: [Wiki] Sort cơ bản 3 - Quick Sort
Em cập nhật lại độ phức tạp nhé @minh_vu_03
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
@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 =))
đ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
@nguyenchiemminhvu Please help
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ử.
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ỉ @@
Đú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