Merge sort run cố định

#1

cho mình hỏi cái thuật toán sấp xếp Merge Sort mà run cố định là sao. Mình hơi mơ hồ về cái đó, nó có giống với Merge Sort run tự nhiên ko ?

#2

anh mới nghe từ run(chạy) cố định và run(chạy) tự nhiên.
không hiểu là gì luôn.
em lấy thông tin này ở đâu ra vậy.

#4

đề lập trình của thầy em.
chính xát là đề nó thế này
3. Cài đặt mergesort theo run cố định (cách 2)
4*. Cài đặt mergesort theo run tự nhiên (cách 3)

#5

hic hic, thuật toán về merger sort anh bỏ lâu rồi.
Nên giờ không biết gì luôn.
không hiểu run cố định là sao luôn.
Em có thể tham khảo link

#6

Em cảm ơn anh !
Dạ em củng coi qua cái đó rồi
Không biết nó có phải là cái Trộn tại chỗ không ?

#7

Em đã tìm ra lời giải

#include "stdafx.h"
#include <iostream>
#include "math.h"
#define MAX 15
using namespace std;
// trả về số nhỏ hơn
int min(int a, int b)
{
	if (a < b)
		return a;
	return b;
}

// trộn 2 dãy phụ tạo dãy mới
void Tron(int a[], int temp1[], int n1, int temp2[], int n2, int k)
{
	int i1, i2, i;
	int k1, k2;
	int j1, j2;
	i = i1 = i2 = 0;
	j1 = j2 = 0;

	while (n2 > 0 && n2 > 0)
	{
		// xác định độ dài từng dãy con 2 dãy phụ
		k1 = min(k, n1);
		k2 = min(k, n2);

		// xét và trộn dãy con vào dãy
		if (temp1[i1 + j1] < temp2[i2 + j2])
		{
			a[i++] = temp1[i1 + j1];
			j1++;

			// trộn dãy con còn lại vào dãy
			if (j1 == k1)
			{
				for (; j2 < k2; j2++)
					a[i++] = temp2[i2 + j2];
				i1 += k1; i2 += k2;
				j1 = j2 = 0;
				n1 -= k1; n2 -= k2;
			}
		}
		else
		{
			a[i++] = temp2[i2 + j2];
			j2++;

			// trộn dãy con còn lại vào dãy
			if (j2 == k2)
			{
				for (; j1 < k1; j1++)
					a[i++] = temp1[i1 + j1];
				i1 += k1; i2 += k2;
				j1 = j2 = 0;
				n1 -= k1; n2 -= k2;
			}
		}
	}
}

void MergeSort(int a[], int n)
{
	int n1, n2;
	int i;
	int k;
	int ik;
	int temp1[MAX], temp2[MAX];
	k = 1;

	do
	{
		i = n1 = n2 = 0;

		// chia mảng ra 2 mảng phụ
		while (i < n)
		{
			ik = 0;

			while (ik < k && i < n)
			{
				temp1[n1++] = a[i++];
				ik++;
			}

			ik = 0;

			while (ik < k && i < n)
			{
				temp2[n2++] = a[i++];
				ik++;
			}
		}

		Tron(a, temp1, n1, temp2, n2, k);

		// tăng độ lớn tối đa dãy con
		k *= 2;
	} while (k < n);

}

void main()
{
	int n = 15;
	int a[MAX] = { 10,3,4,14,9,7,12,11,8,5,2,1,13,15,6 };
	cout << "Mang a " << endl;
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;
	cout << "Mang a sau khi sap xep bang MergeSort co dinh " << endl;
	MergeSort(a, n);
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;

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