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

Đề tài: Tính runtime của radix sort !

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

    Mặc định Tính runtime của radix sort !

    trong môn học của mình có yêu cầu viết và demo một thuật toán đó là radix sort nhưng có thêm phần tính độ phức tạp thuật toán tức là tính runtime, bạn nào rành về thuật toán này và cách tính runtime xin giúp mình ? thanks !

  2. #2
    Ngày gia nhập
    09 2007
    Bài viết
    724

    runtime là gì vậy bạn?
    có phải là tính thời gian thi hành của thuật toán hay là làm demo các bước chạy của một thuật toán?
    độ phức tạp là tính gì vậy bạn? O, o, ...
    Đã được chỉnh sửa lần cuối bởi zkday2686 : 17-11-2008 lúc 01:31 PM.

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

    Đây là lần đầu tiên mình post bài này (dân cntt nói phải có sách mách phải có chứng bạn thử recovery lại bài viết mà bạn nói là gì đó ko dấu trước khi nói bài này đã post rồi), bạn là mod bạn hỏi mình runtime là gì ? độ phức tạp thuật toán là gì thì bạn nên xem lại kiến thức của mình đi có đủ để làm mod hay không ? đề nghị anh admin xem xét lại vấn đề của mod này ? có bạn nào biết thì giúp mình vấn đề tính runtime của thuật toán radix sort ! thanks


    ps : Bạn chưa đủ tư cách làm mod :
    1/ chưa hiểu rõ vấn đề là gì mà đã vội vàng đánh giá, hấp tấp vội vã => dễ dẫn đến sai lầm.
    2/ đã là mod (vì đã dc anh admin tin tưởng) phải có thái độ nhiệt tình giúp đỡ thay vì bạn trả lời câu hỏi của mình bạn lại nói "giờ post lên lại hỏi không ra hỏi? pó tay" câu hỏi của mình quá rõ ràng

  4. #4
    Ngày gia nhập
    09 2007
    Bài viết
    724

    1 - Sorry bạn vì mình đã viết mà không xem lại vì trước đó mình đã xóa một bài cũng về radix sort nên mình nhầm.

    2 - Nếu bạn có ý kiến gì về tư cách và con người của mình trong diễn đàn thì mong bạn nêu ý kiến đóng góp bên mục ý kiến khiếu nại. chứ bỏ vào đây sẽ làm loãng topic và mọi người khó theo dõi topic.

    xin cảm ơn !!!

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

    Radix Sort – sắp xếp cơ số. Độ phức tạp O(n).
    Tư tưởng
    • Coi các phần tử trong mảng sắp xếp được cấu thành từng các lớp có độ ưu tiên khác nhau. Ví dụ, các số tự nhiên chia thành các lớp như: hàng đơn vị, hàng chục, hàng trăm, hàng nghìn,..
    • Bước đầu tiên ta sắp xếp dãy các phần tử bằng cách so sánh các phần tử ở lớp có độ ưu tiên thấp nhất (ví dụ các chữ số hàng đơn vị). Số nào có hàng đơn vị thấp hơn thì ta đưa lên trên. Như vậy các số có hàng đơn vị là 0 ở trên cùng, sau đó đến các số có hàng đơn vị là 1,…
    • Sau bước 1, ta thu được 1 thứ tự sắp xếp mới. Ta lại làm tương tự với các lớp kế tiếp(chữ số thuộc hàng chục, hàng trăm,…) cuối cùng ta sẽ có dãy đã sắp xếp.
    Qua do bước thứ i đã sắp thứ tự cho mức ưu tiên thứ i nên hiển nhiên sau bước thứ i+1 dãy vẫn được sắp đúng thứ tự tính đến mức i+1.

    Ví dụ:
    Cho dãy như sau: {701, 1725, 999, 9170, 3252, 4518, 7009, 1424, 428, 1239, 8425, 7013}.

    Quá trình sắp xếp. (Các cột là dãy số qua từng bước sắp xếp)

    0 7 0 1... 9 1 7 0... 0 7 0 1... 7 0 0 9... 0 4 2 8
    1 7 2 5... 0 7 0 1... 7 0 0 9... 7 0 1 3... 0 7 0 1
    0 9 9 9... 3 2 5 2... 7 0 1 3... 9 1 7 0... 0 9 9 9
    9 1 7 0... 7 0 1 3... 4 5 1 8... 1 2 3 9... 1 2 3 9
    3 2 5 2... 1 4 2 4... 1 4 2 4... 3 2 5 2... 1 4 2 4
    4 5 1 8... 1 7 2 5... 1 7 2 5... 1 4 2 4... 1 7 2 5
    7 0 0 9... 8 4 2 5... 8 4 2 5... 8 4 2 5... 3 2 5 2
    1 4 2 4... 4 5 1 8... 0 4 2 8... 0 4 2 8... 4 5 1 8
    0 4 2 8... 0 4 2 8... 1 2 3 9... 4 5 1 8... 7 0 0 9
    1 2 3 9... 0 9 9 9... 3 2 5 2... 0 7 0 1... 7 0 1 3
    8 4 2 5... 7 0 0 9... 9 1 7 0... 1 7 2 5... 8 4 2 5
    7 0 1 3... 1 2 3 9... 0 9 9 9... 0 9 9 9... 9 1 7 0

    Sở dĩ nói độ phức tạp của thuật toán là O(N) là do phần tử có trị tuyệt đối lớn nhất của dãy không phụ thuộc vào N, số lần sắp xếp coi là hằng số, mỗi lần sắp xếp ta nhìn mỗi phần tử 1 lần, do đó độ phức tạp của thuật toán là O(n).

    Radix sort nói chung là rất mạnh trong việc sắp xếp số nguyên với lượng phần tử lớn nhưng sử dụng lại hơi khó vì khi cần sắp xếp một tập đối tượng nào đó, lại phải định nghĩa phép so sánh cho tất cả các mức ưu tiên, trong khi dùng các thuật toán khác ta chỉ cần định nghĩa phép so sánh giữa 2 đối tượng.

    Ngoài ra radix sort bị suy biến khi log(max|C[i]|) khá lớn trong khi N nhỏ. (log ở đây là logarit cơ số 10 nhé)

  6. #6
    Ngày gia nhập
    05 2008
    Bài viết
    11

    Mặc định Tính runtime của radix sort !

    Ban thientran nóng tính quá.
    mình có cái code này, ban tét thử coi dúng hok nhé:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    #include <conio.h>
    #include <sys/timeb.h>
    #include <time.h>
    
    ////Radix sort
    int getMax(int a[],int n)
    {
    	int max=a[0];
    	for(int i=1;i<n;i++)
    		if(max<a[i])
    			max=a[i];
    	return max;
    }
    int countDigit(int n)
    {
    	int count=0;
    	while(n)
    	{
    		count++;
    		n/=10;
    	}
    	return count;
    }
    int getDigit(int n,int t)
    {
    	int tt=1;
    	for(int i=0;i<t;i++)tt*=10;
    	return ((n/tt)%10);
    }
    void send2Box(int a[],int n,int *b[10],int num[10],int t)
    {
    	for(int i=0;i<n;i++)
    	{
    		int tt=getDigit(a[i],t);
    		b[tt][num[tt]++]=a[i];
    	}
    }
    void getValue(int a[],int *b[10],int nn[10])
    {
    	int j=0;
    	for(int i=0;i<10;i++)
    	{
    		if(nn[i]!=0)
    		{
    			for(int k=0;
    			k<nn[i];
    			k++)a[j++]=b[i][k];
    			nn[i]=0;
    		}
    	}
    }
    void radixsort(int a[],int n)
    {
    	int *Box[10],i;
    	int number[10];
    	for(i=0;i<10;i++)
    	{
    		Box[i]=new int [n];
    		if(Box[i]==NULL)
    		{
    			printf("Not enough");
    			exit(0);
    		}
    		number[i]=0;
    	 }
    	int nn=countDigit(getMax(a,n));
    	for(i=0;i<nn;i++)
    	{
    		send2Box(a,n,Box,number,i);
    		getValue(a,Box,number);
    	}
    }
    void xuat(int a[], int n)
    {
    	int i=0;
    	printf("\n\t");
    	for (i=0;i<n;i++)
    	{
    		printf("%-6d",a[i]) ;
    		if ((i+1) % 10 == 0)
    		printf("\n\t");
    	}
    }
    void main()
    {
    //	clrscr();
    	int i,n,A[100];
    	struct _timeb timebuffer;
        _ftime( &timebuffer );
    	do
    	{
    		printf("\n\tNhap so phan tu mang\n\t( n>0 va n<=100) : ");
    		scanf("%d",&n);
    		}while (n<0||n>100);
    	for (i=0;i<n;i++)
    	{
    		printf("Nhap A[%d]=",i);
    		scanf("%d",&A[i]);
    	}
    	printf("\n\tMang moi nhap vao:\n");
    	xuat(A,n);
    
    
    	char *timeline = ctime( & ( timebuffer.time ) );
    
    	printf("\n\n\tMang da sap xep :\n");  
    	radixsort(A,n);
    	
    	struct _timeb timebuffer1;
    	_ftime( &timebuffer1 );
    
    	char *timeline1 = ctime( & ( timebuffer1.time ) );
    
    
    	long milisecond = timebuffer1.millitm - timebuffer.millitm;
    	long second = timebuffer1.time - timebuffer.time;
    
    	xuat(A,n);
    	printf("\n So giay: %ld  va %ld phan tram giay",second, milisecond);
     getch();
    }
    vì là mới sửa xong, 1 đoạn code(Radix Sort) copy từ "iamvtn" và mình thêm thuật toán tính thời gian mới thình giáo của giáo viên hôm wa.
    Nếu có sai, xin chỉ giáo thêm.
    Đã được chỉnh sửa lần cuối bởi hoangtulai_hp : 19-12-2008 lúc 04:43 PM.

  7. #7
    Ngày gia nhập
    01 2010
    Bài viết
    61

    Có ai giải thích cho minh tại sao lúc truyen box[10] vào hàm send2box va` getvalue là mảng 1 chiều mà khi dùng lại trong hàm send2box và getvalue lại là mảng 2 chiều???????

  8. #8
    Ngày gia nhập
    06 2010
    Nơi ở
    Hà Nội
    Bài viết
    48

    Ai giúp mình trả lời cụ thể các hàm trong thuật toán với!!Đang còn gà mờ wa
    !!

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

  1. Sắp xếp mảng số nguyên (âm dương) bằng Radix Sort
    Gửi bởi gialoui 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: 22-10-2013, 08:15 PM
  2. 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
  3. Sắp xếp Radix sort. Nhờ mọi người sửa giúp
    Gửi bởi alexander88 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 17-10-2009, 06:39 AM
  4. Thuật toán radix sort
    Gửi bởi huynguyen trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 3
    Bài viết cuối: 28-08-2009, 10:19 PM
  5. Thuật radix sort
    Gửi bởi kinhmoiban trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 11-09-2008, 10:55 AM

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