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

Đề tài: [ Solved ]Các anh em cho mình hỏi về Quicksort 1 tí!

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

    Cool [ Solved ]Các anh em cho mình hỏi về Quicksort 1 tí!

    Thầy mình yêu cầu lên mạng tìm thông tin về thuật toán Quicksort,yêu cầu là không dùng đệ quy và sắp theo giá trị tuyệt đối.quan trọng là thầy yêu cầu phải chú thích rõ từng bước.Rất mong mọi người giúp đỡ.


  2. #2
    Ngày gia nhập
    06 2007
    Nơi ở
    UIT
    Bài viết
    44

    Trích dẫn Nguyên bản được gửi bởi romanticdevil88 Xem bài viết
    Thầy mình yêu cầu lên mạng tìm thông tin về thuật toán Quicksort,yêu cầu là không dùng đệ quy và sắp theo giá trị tuyệt đối.quan trọng là thầy yêu cầu phải chú thích rõ từng bước.Rất mong mọi người giúp đỡ.

    Thì thầy nói bạn tìm cơ mà bạn hãy tự mình tìm tòi rồi nếu không hiểu ở đâu trong đoạn code đó thì đưa lên trên đây mọi người giải thích cho chứ

  3. #3
    Ngày gia nhập
    02 2008
    Nơi ở
    Gia Lai
    Bài viết
    6

    Người gì vậy trời, cái này phải dùng đầu thôi bạn ơi ^^
    Tin học là cuộc sống, Lập trình là người yêu, Vợ là computer
    http://diendanaptech.com/

  4. #4
    Ngày gia nhập
    04 2008
    Bài viết
    8

    Mình tìm ra rồi nhưng mà chạy không được,mình không hiểu gì hết.Các bạn check rùi giải thik dùm mình nha

    Code:
    void QuickSort(int a[], int n) 
    { 
    StackType stack; 
    int L, R, i, j; 
    int x; 
    stack = NULL; Push(0,n-1, Stack); 
    do 
    { 
            P = Pop(Stack); L = P->L; R = P->R;  
            do  
            {     /*Phan hoach aL..aR */ 
                        i = L,  
                        j = R;  
                        x = a[(L+R)/2]; 
                        do  
                        { 
                                while (a[i] < x) i++; 
                                while (a[j] > x) j--; 
                                 if (i <= j)  
                                 {     
                                           HoanVi(&a[i], &a[j]); 
                                           i++;  
                                           j--; 
                                 } 
                      } while (i <= j); 
                    if ( i < R) Push(i, R, Stack); 
                    R = j; 
         } while (L<R); 
    } while (Stack != NULL); 
    }

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

    Trích dẫn Nguyên bản được gửi bởi romanticdevil88 Xem bài viết
    Mình tìm ra rồi nhưng mà chạy không được,mình không hiểu gì hết.Các bạn check rùi giải thik dùm mình nha

    Code:
    void QuickSort(int a[], int n) 
    { 
    StackType stack; 
    int L, R, i, j; 
    int x; 
    stack = NULL; Push(0,n-1, Stack); 
    do 
    { 
            P = Pop(Stack); L = P->L; R = P->R;  
            do  
            {     /*Phan hoach aL..aR */ 
                        i = L,  
                        j = R;  
                        x = a[(L+R)/2]; 
                        do  
                        { 
                                while (a[i] < x) i++; 
                                while (a[j] > x) j--; 
                                 if (i <= j)  
                                 {     
                                           HoanVi(&a[i], &a[j]); 
                                           i++;  
                                           j--; 
                                 } 
                      } while (i <= j); 
                    if ( i < R) Push(i, R, Stack); 
                    R = j; 
         } while (L<R); 
    } while (Stack != NULL); 
    }
    Có lẽ chỗ bôi đậm là kiểu dữ liệu gì vậy. Code thiếu rồi.

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

    Mặc định [ Solved ]Các anh em cho mình hỏi về Quicksort 1 tí!

    Bài này mình vừa mới viết,xem thử đi nha
    Không dùng đệ qui thì chỉ có duy nhất là dùng stack để lưu vết cho chương trình.
    Đầu tiên bạn nên viết chương trình đệ qui cho QuickSort.
    Từ chương trình đệ qui tiến hành khử đệ qui theo cách sau:
    Ý tưởng khử đệ quy như sau:
    - Tại lời gọi đệ qui chúng ta cần lưu thông tin của các biến cục bộ vào stack, để sau khi hàm đệ qui hoàn thành thì chương trình khôi phục lại trị cho những thông số cục bộ để làm tiếp cho những câu lệnh sau lời gọi đệ qui.

    QuickSort đệ qui:
    C Code:
    1. void QuickSort_1(int a[],int left,int right){
    2.     int j,k;
    3.     int tmp;
    4.     if(left<right){
    5.  
    6.         j=left;
    7.         k=right+1;
    8.  
    9.         do
    10.         {
    11.  
    12.             do
    13.             {
    14.                 j=j++;
    15.             }while (a[j]<a[left]);
    16.        
    17.        
    18.             do
    19.             {
    20.                 k=k--;
    21.             }while (a[k]>a[left]);
    22.        
    23.             if(j<k)
    24.             {
    25.                 tmp=a[j];
    26.                 a[j]=a[k];
    27.                 a[k]=tmp;
    28.             }
    29.         }while (j<=k);
    30.        
    31.         tmp=a[left];
    32.         a[left]=a[k];
    33.         a[k]=tmp;
    34.        
    35.         QuickSort_1(a,left,k-1);
    36.         QuickSort_1(a,k+1,right);
    37.     }
    38. }
    QuickSort không đệ qui:
    C Code:
    1. void QuickSort_2(int a[],int left,int right){
    2.     int j,k;
    3.     int tmp;
    4.     Stack<int> leftStack,rightStack,kStack; //lưu giá trị của left,right,k
    5.     int top=0;
    6. L0:
    7.     if(left>=right)
    8.         goto L2;
    9.     else
    10.  
    11.         j=left;
    12.         k=right+1;
    13.  
    14.         do
    15.         {
    16.  
    17.             do
    18.             {
    19.                 j=j++;
    20.             }while (a[j]<a[left]);
    21.        
    22.        
    23.             do
    24.             {
    25.                 k=k--;
    26.             }while (a[k]>a[left]);
    27.        
    28.             if(j<k)
    29.             {
    30.                 tmp=a[j];
    31.                 a[j]=a[k];
    32.                 a[k]=tmp;
    33.             }
    34.         }while (j<=k);
    35.        
    36.         tmp=a[left];
    37.         a[left]=a[k];
    38.         a[k]=tmp;
    39.        
    40. //Khử đệ qui cho QuickSort_1(a,left,k-1) trong chương trình đệ qui
    41.        
    42.                 leftStack.push(left);
    43.         kStack.push(k);
    44.         rightStack.push(right);
    45.         top=top++;
    46.         right=k-1;
    47.         goto L0;
    48. L1:
    49.         left=k+1;
    50.         goto L0;
    51. L2:
    52.         if(top!=0){
    53.             leftStack.top(left);
    54.             leftStack.pop();
    55.  
    56.             kStack.top(k);
    57.             kStack.pop();
    58.  
    59.             rightStack.top(right);
    60.             rightStack.pop();
    61.  
    62.             top=top--;
    63.             goto L1;
    64.         }
    65. }

    Vui lòng để code vào trong tag code. Đọc Nội quy để biết thêm chi tiết
    Đã được chỉnh sửa lần cuối bởi Kevin Hoang : 23-04-2008 lúc 12:15 AM. Lý do: Nhắc nhở
    C++,C#,Java muôn năm

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

    Code:
    Bài này mình cũng vừa mới viết tham khảo nha :
    
    #include<iostream.h>
    #include<conio.h>
    #include<stdio.h>
    #include<stdlib.h>
    
    // Neu ta dung ham dem thoi gian trong thuat toan ta dung ham <time.h>
    class Sapxep
    {
    private:
    	int*arr;
    public:
    	void Nhapmang(int &n);
    	void Inmang(int a[],int n);
    	void Bubblesort(int a[],int N);
    	void Partition(int a[],int F,int L);// phan hoach  tim chi so dau va chi so cuoi
    	void Quicksort(int a[],int N); // chu y thuat toan quicksort
    };
    
    void Sapxep::Nhapmang(int &n)
    {
    		cout<<"Nhap vao so phan tu trong Mang :";
    		cin>>n;
    		arr=new int[n];
    	for(int i=0;i<n;i++)
    	{
    		cout<<"Phan tu thu "<<i+1<<":";
    		cin>>arr[i];
    	}
    }
    // Ham in mang 
    void Sapxep::Inmang(int a[],int n)
    {
    	for(int i=0;i<n;i++)
    	{
    		cout<<arr[i];
    	}
    	cout<<"\n";
    }
    
    void Sapxep::Partition(int a[],int F,int L)
    {
    	int i,j,x;
    	if(F>L)
    		 return;
    	int Mid=arr[(F+L)/2];
    	 i=F;
    	 j=L;
    	do
    	{
    		while(arr[i]<Mid)
    			i++;
    		while(arr[j]>Mid)
    			j--;
    		if(i<=j)
    		{
    				x = arr[j-1];
    				arr[j-1] = arr[j];
    				arr[j] = x;
    			
    		}
    		i++;
    		j--;
    	} while(i<=j) ;
    			Partition(a,F,j);
    		    Partition(a,j,L);
    			return;
    
    
    } 
    void Sapxep::Quicksort(int a[],int N)
    { 
    	Partition(a,0,N-1);
    	return;
    } 
    
    void main()
    {
    	int n,N;
    
    	// chu y o day ta nen viet ham phat sinh ngau nhien
    //	randomize();
    //	for(i=0;i<n;i++)
    //		arr[i]=random(100);
    	int a[1000];
        Sapxep s;
    	s.Nhapmang(n);
    	cout<<"Mang truoc khi chua sap xep :\n";
    	s.Inmang(a,n);
    	//cout<<"Sap xep bang Bubble sort: \n";
       // s.Bubblesort(a,n);
    //	s.Inmang(a,n);
    	cout<<"Sap xep Quicksort:\n";
    	s.Quicksort(a,N);
    	s.Inmang(a,n);

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

  1. Kỹ thuật C Ko rõ về quicksort
    Gửi bởi neverdie201111 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 13
    Bài viết cuối: 16-12-2013, 10:28 PM
  2. Quicksort sử dụng lặp????
    Gửi bởi 51203104 trong diễn đàn Nhập môn lập trình C#, ASP.NET
    Trả lời: 0
    Bài viết cuối: 05-11-2013, 06:50 PM
  3. so sánh điểm sv bằng quicksort
    Gửi bởi Lindan trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 3
    Bài viết cuối: 18-10-2011, 03:00 PM
  4. [Solved]Lỗi hàm quicksort
    Gửi bởi RedHatLinux9 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 6
    Bài viết cuối: 23-10-2008, 12:03 AM
  5. Trả lời: 6
    Bài viết cuối: 04-05-2008, 08:04 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