Thuật toán sắp xếp trộn (Merge Sort)
2 posters
Trang 1 trong tổng số 1 trang
Thuật toán sắp xếp trộn (Merge Sort)
1. Bài toán
Cho dãy X = {X1, X1, ..., Xn}, hãy sắp xếp dãy theo chiều không giảm.
2. Ý tưởng
- Giả sử dãy X[1],...,X[i],...,X[n] có hai đoạn đã được sắp xếp không giảm là X[1],...,X[i] và X[i+1],...,X[n], ta tiến hành tạo ra dãy mới bằng cách lần lượt lấy hai phần tử đầu tiên của mỗi đoạn và so sánh với nhau. Phần tử nào nhỏ hơn thì lấy ra dãy mới và bỏ nó ra khỏi đoạn đang xét. Cứ tiến hành như vậy cho tới khi một dãy bị vét hết (không còn phần tử nào). Lấy toàn bộ phần tử còn lại của đoạn không xét hết nối vào sau dãy đích. Như vậy dãy mới là một dãy đã được sắp xếp.
- Trong mọi trường hợp, có thể coi dãy gồm duy nhất 1 phần tử là đã được sắp xếp. Lợi dụng việc này, ta phân chia một dãy ra thành nhiều dãy con chỉ gồm một phần tử rồi lần lượt hòa nhập từng đôi một với nhau.
3. Mã thực thi (tựa C)
4. Ví dụ
X = {7, 2, 5, 4, 1, 3, 8, 6}
Dãy ban đầu: 7, 2, 5, 4, 1, 3, 8, 6
Từ dãy ban đầu, chia làm 2 đoạn con {7, 2, 5, 4} và {1, 3, 8, 6}
Chia tiếp làm các đoạn con X1 = {7, 2}, X2 = {5, 4} và X3 = {1, 3}, X4 = {8, 6}
Merge từng đoạn ta được X1 = {2, 7}, X2 = {4, 5} và X3 = {1, 3}, X4 = {6, 8}
Merge(X1+X2), Merge(X3+X4) ta được X5 = {2, 4, 5, 7} và X6 = {1, 3, 6, 8}
Merge(X5+X6) ta được {1, 2, 3, 4, 5, 6, 7 ,8}
Cuối cùng ta có 1, 2, 3, 4, 5, 6, 7, 8, dãy đã được sắp xếp.
Cho dãy X = {X1, X1, ..., Xn}, hãy sắp xếp dãy theo chiều không giảm.
2. Ý tưởng
- Giả sử dãy X[1],...,X[i],...,X[n] có hai đoạn đã được sắp xếp không giảm là X[1],...,X[i] và X[i+1],...,X[n], ta tiến hành tạo ra dãy mới bằng cách lần lượt lấy hai phần tử đầu tiên của mỗi đoạn và so sánh với nhau. Phần tử nào nhỏ hơn thì lấy ra dãy mới và bỏ nó ra khỏi đoạn đang xét. Cứ tiến hành như vậy cho tới khi một dãy bị vét hết (không còn phần tử nào). Lấy toàn bộ phần tử còn lại của đoạn không xét hết nối vào sau dãy đích. Như vậy dãy mới là một dãy đã được sắp xếp.
- Trong mọi trường hợp, có thể coi dãy gồm duy nhất 1 phần tử là đã được sắp xếp. Lợi dụng việc này, ta phân chia một dãy ra thành nhiều dãy con chỉ gồm một phần tử rồi lần lượt hòa nhập từng đôi một với nhau.
3. Mã thực thi (tựa C)
- Code:
// Thủ tục trộn gọi đệ quy
void MergeSort(int X[], int L, int R)
{
int M;
if (L<R){
M=int((L+R)/2);
MergeSort(X,L,M);
MergeSort(X,M+1,R);
Merge(X,L,M+1,R);
}
}
// Thủ tục trộn hai đoạn đã sắp xếp trong một dãy
void Merge(int a[], int k1, int k2, int k3)
{
int i,j,k,t;
int temp[];
i=k1; j=k2; k=k3;
while (i<k2) and (j<=k3)
{
if (a[i]<=a[j]){
temmp[k]=a[i];
i=i+1;
}
else{
temp[k]=a[j];
j=j+1;
}
k=k+1;
}
if (i>=k2)
for(t=j;t<=k3,t++)
temp[k+t-j]=a[t];
else
for(t=i;t<=k2,t++)
temp[k+t-i]=a[t];
for(k=k1;t<=k3,k++)
a[k]=temp[k];
}
4. Ví dụ
X = {7, 2, 5, 4, 1, 3, 8, 6}
Dãy ban đầu: 7, 2, 5, 4, 1, 3, 8, 6
Từ dãy ban đầu, chia làm 2 đoạn con {7, 2, 5, 4} và {1, 3, 8, 6}
Chia tiếp làm các đoạn con X1 = {7, 2}, X2 = {5, 4} và X3 = {1, 3}, X4 = {8, 6}
Merge từng đoạn ta được X1 = {2, 7}, X2 = {4, 5} và X3 = {1, 3}, X4 = {6, 8}
Merge(X1+X2), Merge(X3+X4) ta được X5 = {2, 4, 5, 7} và X6 = {1, 3, 6, 8}
Merge(X5+X6) ta được {1, 2, 3, 4, 5, 6, 7 ,8}
Cuối cùng ta có 1, 2, 3, 4, 5, 6, 7, 8, dãy đã được sắp xếp.
hosytan- Tổng số bài gửi : 29
Join date : 02/05/2013
Re: Thuật toán sắp xếp trộn (Merge Sort)
Để dễ hiểu Thuật toán sắp xếp trộn chúng ta nên biết thuật ngữ trộn(merge):
Trộn (merge)
Giả sử có 2 mảng được sắp xếp A1[a...n] và A2[b...m] khi ta trộn (merge) 2 mảng thành một mảng mới A3[a...(n+m)]
- So sánh 2 phần từ đầu của 2 mảng, lấy phần bé hơn cho vào mảng mới, làm như vậy cho đến khi một trong 2 mảng trở thành rỗng.
- Cho phần còn lại của mảng kia vào cuối danh sách
Trộn (merge)
Giả sử có 2 mảng được sắp xếp A1[a...n] và A2[b...m] khi ta trộn (merge) 2 mảng thành một mảng mới A3[a...(n+m)]
- So sánh 2 phần từ đầu của 2 mảng, lấy phần bé hơn cho vào mảng mới, làm như vậy cho đến khi một trong 2 mảng trở thành rỗng.
- Cho phần còn lại của mảng kia vào cuối danh sách
hbs315- Tổng số bài gửi : 8
Join date : 13/12/2013
Similar topics
» Thuật toán sắp xếp nổi bọt (Bubble Sort)
» Thuật toán sắp xếp chọn (Selection Sort)
» Thuật toán sắp xếp chèn (Insertion Sort)
» Thuật toán sắp xếp vun đống (Heap Sort)
» Thuật toán sắp xếp phân đoạn/sắp xếp nhanh (Quick Sort)
» Thuật toán sắp xếp chọn (Selection Sort)
» Thuật toán sắp xếp chèn (Insertion Sort)
» Thuật toán sắp xếp vun đống (Heap Sort)
» Thuật toán sắp xếp phân đoạn/sắp xếp nhanh (Quick Sort)
Trang 1 trong tổng số 1 trang
Permissions in this forum:
Bạn không có quyền trả lời bài viết
|
|