Từ 1 tới 6 trên tổng số 6 kết quả

Đề tài: natural merge sort

  1. #1
    Ngày gia nhập
    01 2008
    Bài viết
    0

    Mặc định natural merge sort

    Xin hướng dẫn cho mình cách cài đặt thuật toán natural merge sort trên một chuỗi kí tự = C#.
    tu 1 file input như sau:

    chuoithu 1
    chuoithu 2
    chuoithu 3
    ---------
    chuoithu n

    dùng natural merge sort để phân bố đường chạy vào 2 phụ temp1 và temp2.
    sau đó trộn lại thành 1 file output có thứ tự tăng(hoặc giảm).
    Mong các bạn giúp mình với. Mình không có tài liệu về natural merge sort.

  2. #2
    Ngày gia nhập
    01 2008
    Bài viết
    0

    hic hic, sao ko ai trả lời mình thế?

  3. #3
    No Avatar
    langtugacon Khách

    Sao lại sắp xếp chuỗi kí tự nhỉ, nếu thế thì sắp xếp theo ABC àh.

  4. #4
    Ngày gia nhập
    07 2006
    Nơi ở
    Hanoi, Vietnam
    Bài viết
    2,750

    Bạn có thể hình dung natural merge sort bằng hình ảnh sau:



    Đây là tài liệu về nó: http://penguin.ewu.edu/~trolfe/Natur.../NatMerge.html

    Và đây là code mô phỏng bằng C, bạn chuyển nó sang C#.
    C Code:
    1.    // MergeSort.cpp : Defines the entry point for the console application.
    2.     //
    3.     #include "conio.h"
    4.     #include "math.h"
    5.     #include "stdio.h"
    6.     #include "stdlib.h"
    7.  
    8.     typedef struct {
    9.        int *array;
    10.        int number;
    11.     } arr;
    12.  
    13.     arr getfromFile( char *a){
    14.        FILE *f;
    15.        arr t;
    16.        t.array=NULL;
    17.        t.number=-1;
    18.        if ((f=fopen(a,"rt"))==NULL){
    19.           printf("Can't read File");
    20.           exit(0);
    21.        }
    22.        if (a==NULL)
    23.           return t;
    24.        fscanf(f,"%d",&t.number); // Doc so phan tu ta da viet trong file
    25.        if (t.number<1)
    26.           return t;
    27.        t.array=new int[t.number];
    28.        if (t.array==NULL) // Kiem tra xin bo nho duoc hay khong?
    29.           return t;
    30.        for (int count=0;count<t.number;count++)// Doc tung phan tu
    31.           fscanf(f,"%d",&t.array[count]);
    32.        
    33.        fclose(f);
    34.        return t;
    35.     }
    36.  
    37.     void output(int a[],int n){
    38.        for (int i=0;i<n;i++)
    39.           printf("%5d",a[i]);
    40.        printf("\n");
    41.     }
    42.  
    43.     void hoanvi(int &a,int &b){
    44.        int tam;
    45.        tam = a;
    46.        a = b;
    47.        b = tam;
    48.     }
    49.  
    50.     void merge(int a[],int pos,int b[],int nb,int c[],int nc){
    51.        int *tam,n=nb+nc,k=0;
    52.        tam = new int[n];
    53.        if (!tam){
    54.           printf("Stack is over");
    55.           exit(0);
    56.        }
    57.        int i=0,j=0;
    58.        while(i<nb&&j<nc)
    59.           if (b[i]<c[j])
    60.              tam[k++] = b[i++];
    61.           else
    62.              tam[k++] = c[j++];
    63.           while(i<nb)
    64.              tam[k++] = b[i++];
    65.           while(j<nc)
    66.              tam[k++] = c[j++];
    67.           for (i=0;i<n;i++)
    68.              a[pos++] = tam[i];
    69.           delete tam;
    70.     }
    71.  
    72.     void mergeSort(int a[],int n){
    73.        int i,hb,hc,tb,tc,r,*b,*c,seq;
    74.        int nb,nc;
    75.        do{
    76.           hb = hc = 0;
    77.           i = 0;
    78.           tc = -1;
    79.           seq = 0;
    80.           do{
    81.              seq++;
    82.              i = tc +1;
    83.              while(a[i]<=a[i+1]&&i<n-1)
    84.                 i++;
    85.              if (i<n-1){
    86.                 tb = i;
    87.                 hc = tc = i+1;
    88.                 i = hc;
    89.              }
    90.              else
    91.                 break;
    92.              seq++;
    93.              while(a[i]<=a[i+1]&&i<n-1)
    94.                 i++;
    95.              tc = i;
    96.              b = &a[hb];
    97.              c = &a[hc];
    98.              nb = tb - hb+1;
    99.              nc = tc - hc+1;
    100.              merge(a,hb,b,nb,c,nc);
    101.              hb = tc+1;
    102.           }while(i<n);
    103.        }while(seq>=2);
    104.     }
    105.  
    106.  
    107.     void main(){
    108.        arr t;
    109.  
    110.        t = getfromFile("C:\\data.txt");
    111.        if (t.array==NULL){
    112.           printf("Error");
    113.           exit(0);
    114.        }
    115.        printf("Before sorting:");
    116.        output(t.array,t.number);
    117.        printf("After sorting:");
    118.        mergeSort(t.array,t.number);
    119.        output(t.array,t.number);
    120.        getch();
    121.     }

    Regards!
    Email: admin[@]congdongcviet.com | CC to: info[@]congdongcviet.com
    Phone: 0972 89 7667 (Office: 04 6329 2380)
    Yahoo & Skype: dreaminess_world (Vui lòng chỉ rõ mục đích ngay khi liên hệ, cảm ơn!)

    Một người nào đó coi thường ý thức kỷ luật cũng có nghĩa là người đó đã coi thường tương lai số phận của chính bản thân người đó. Những người coi thường ý thức kỷ luật sẽ không bao giờ có được sự thành công trong sự nghiệp!

  5. #5
    Ngày gia nhập
    03 2009
    Bài viết
    10

    e đang học ctdl, có 1 số hàm em ko hiểu? Pro nào giải thích dùm (nếu đc thì giải thích hết càng tốt).thanks

  6. #6
    Ngày gia nhập
    03 2011
    Bài viết
    4

    Mặc định natural merge sort

    Chào! Biết là gửi hơi thừa nhưng mình gửi các bạn code Natural Merge Sort mình tự viết. Đơn giản dễ hiểu hơn code trên kia. Mình post chủ yếu để bạn nào không biết khi search google có bài mà coi! P/s: code viết trên C, ai muốn dùng thì chuyển qua cái khác
    Code:
    #include "stdafx.h"
    #include <stdio.h>
    #include <conio.h>
    #include <stdlib.h>
    #include <time.h>
    #define MAX 5
    void TaoMang(int A[])
    {
    	int n = 0;
    	srand(time(NULL));
    	while(n<MAX)
    	{
    		A[n++] = rand();
    	}
    }
    int SoDuongChay(int A[])
    {
    	int dem = 0, i = 0;
    	while(i<MAX)
    	{
    		while(A[i]<A[i+1]&&i<MAX-1)
    			i++;
    		dem++;
    		i++;
    	}
    	return dem;	
    }
    void Merge(int A[], int B[], int C[], int &m, int &n, int &nA)
    {
    	int i = 0, j = 0;
    	while(i<m && j<n)
    	{
    		if(B[i]<C[j])
    			A[nA++] = B[i++];
    		else
    			A[nA++] = C[j++];
    	}
    	while(i<m)
    		A[nA++] = B[i++];
    	while(j<n)
    		A[nA++] = C[j++];
    	m = 0;
    	n = 0;
    }
    void PhanPhoiVaoMang(int A[], int B[], int C[])
    {
    	int i = 0, dem = 0, nA = 0;
    	int m = 0, n = 0;
    	while(i<MAX)
    	{
    		int tmp = i;
    		while(A[i]<A[i+1] && i<MAX-1)
    			i++;
    		if(dem%2==0)
    			for(int j = tmp; j<=i; j++)
    				B[m++] = A[j];
    		else
    		{
    			for(int j = tmp; j<=i; j++)
    				C[n++] = A[j];
    			Merge(A, B, C, m, n, nA);
    		}
    		i++;
    		dem++;
    	}
    	if(m!=0)
    		for(int k = 0; k<m; k++)
    			A[nA++] = B[k];
    }
    void NaturalMergeSort(int A[], int B[], int C[])
    {
    	while(SoDuongChay(A)>=2)
    		PhanPhoiVaoMang(A, B, C);
    }
    void PhanPhoiTheoK(int A[], int B[], int C[], int &m, int &n, const int &k)
    {
    	int i = 0;
    	while(i<MAX)
    	{
    		for(int j = 0; j<k; j++)
    			B[j] = A[i++];
    		for(int q = 0; q<k; q++)
    			C[q] = A[i++];
    	}
    }
    void InMang(int A[], int n)
    {
    	for(int i = 0; i<n; i++)
    		printf(" %d ", A[i]);
    	printf("\n");
    }
    int _tmain(int argc, _TCHAR* argv[])
    {
    	int A[MAX], B[MAX], C[MAX];
    	int m = 0, n = 0, k = 0;
    	TaoMang(A);
    	printf("Mang vua duoc tao ra theo ramdom la: \n");
    	InMang(A, MAX);
    	NaturalMergeSort(A, B, C);
    	printf("Mang A sau khi duoc sap xep bang giai thuat NaturalMergeSort: \n");
    	InMang(A, MAX);
    Đã được chỉnh sửa lần cuối bởi khaihuynh : 17-10-2011 lúc 09:21 PM.

Các đề tài tương tự

  1. Thuật toán C++ Ưu nhược điểm các kiểu sort Interchange sort, Selection sort, Insertion sort, Sharke sort , Quick sort, Heap sort
    Gửi bởi duythanhnguyen trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 7
    Bài viết cuối: 23-09-2013, 01:16 AM
  2. Mã nguồn C Lỗi Phương pháp trộn tự nhiên (Natural Merge Sort)?!
    Gửi bởi Cerberus. trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 10-05-2011, 12:06 AM
  3. Lập trình C++ Natural Merge Sort trên file
    Gửi bởi nvtin trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 21-10-2010, 03:31 PM
  4. Giúp em bài toán Mô phỏng thuật toán MERGE sort va RADIX Sort bằng C
    Gửi bởi mr.fan trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 6
    Bài viết cuối: 03-06-2010, 09:34 AM
  5. thuật toán Natural merge sort trong c#?
    Gửi bởi ninomaxx trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 1
    Bài viết cuối: 27-04-2010, 10:52 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn