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

Đề tài: Thuật toán Quick Sort viết bằng C++, có lỗi làm sao sửa?

  1. #1
    Ngày gia nhập
    02 2009
    Bài viết
    7

    Mặc định Thuật toán Quick Sort viết bằng C++, có lỗi làm sao sửa?

    Code của mình đây
    PHP Code:
    #include <iostream.h>
    #include <conio.h>
    #include <iomanip.h>
    void NhapMang(int a[],int n)
    {
        for(
    int i=0;i<n;i++)
        {
            
    cout<<"a["<<i+1<<"]=";
            
    cin>>a[i];
        }
    }
    void InMang(int a[],int n)
    {
        for(
    int i=0;i<n;i++)
            
    cout<<setw(40)<<a[i];
    }
    void quicksort(int a[],int l,int r)
    {
        if(
    l>=r) return;
        
    int i=l;
        
    int j=r;
        
    int x=a[(l+r)/2];
        while(
    i<=j)
        {
            while(
    a[i]<xi++;
            while(
    a[j]>xj--;
            if(
    i<=j)
            {
                
    int temp=a[i];
                
    a[i]=a[j];
                
    a[j]=temp;
                
    i++;j--;
            }
        }
        
    quicksort(a,l,j);
        
    quicksort(a,i,r);

    }
    void main()
    {
        
    clrscr();
        
    int a[20],n,i;
        
    cout<<"Nhap so phan tu n= ";
        
    cin >>n;
        
    NhapMang(a,n);
        
    quicksort(a,0,n-1);
        
    cout<<"Mang sau khi sap xep : "<<endl;
        
    InMang(a,n);
        
    getch();

    Mình đang chạy tay bằng code trên mà chạy hoài ko đc. Các bạn giúp mình với nhé. Chạy từng bước 1 nhé chốt thì in đậm cho mình dễ hiểu nhé.
    VD mảng này: 42 23 47 11 65 58 94 36 99 87

  2. #2
    Ngày gia nhập
    02 2008
    Nơi ở
    Việt Nam
    Bài viết
    577

    Chạy tay là rất tốt, sẽ giúp hiểu rõ thuật toán hơn.

    *Start
    l=0, r=9
    x = a[4] = 65
    sau 2 vòng while thì i=6, j = 7
    swap dãy trở thành
    42 23 47 11 65 58 36 94 99 87
    i = 7, j = 6 =>dừng vòng while ở ngoài

    *Bước đệ quy:
    tiến hành sort mảng con 42 23 47 11 65 58 36
    và 94 99 87


    Với cách phân tích tương tự thì sẽ sort xong toàn mảng. Hình dung như vậy chứ viết hết cũng hơi mệt, bạn xem cái hình mô phỏng trong wikipedia sẽ thấy rõ.

  3. #3
    Ngày gia nhập
    02 2009
    Bài viết
    7

    Mình vẫn băn khoăn chỗ vòng swap đầu mong bạn giải thích dùm mình:
    42 23 47 11 65 58 94 36 99 87
    i->------------------------ <-j
    khi i= 0,1,2,3 thì a[i]<65 ko đổi chỗ đến i=4 a[i]=65 =x dừng ko đi tiếp nữa.
    j=9,8 a[j]>65 ko đổi chỗ đến j=7 a[j]=36<65 dừng i<j đổi chỗ a[4] <-> a[7] đổi xong i,j chạy tiếp khi i=6 j=5 dừng.
    Swap xong sẽ cho : 42 23 74 11 36 58 94 65 99 87
    Mình cũng bỏ đệ quy để máy chạy vòng swap đầu nó cũng ra như vậy ko hiểu tại sao mong các bạn chỉ mình với

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

    chạy tay thì bạn chạy ít phần tử thôi cho dễ ...
    tốt nhất là bạn cho mỗi lần có swap thì in ra màn hình để dễ nhận biết hoặc cho chạy từng dòng lệnh để theo dõi sự thay đổi của các biến là hay nhất.

    bạn chạy tay tiếp thì nó sẽ ra như trên, lưu ý là nó so sánh với x chứ ko so sánh với a[(i+j)/2]
    Mà bạn gõ nhầm 47 thành 74 kìa ...
    code ra gió bão

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

    Trích dẫn Nguyên bản được gửi bởi 6220119 Xem bài viết
    chạy tay thì bạn chạy ít phần tử thôi cho dễ ...
    tốt nhất là bạn cho mỗi lần có swap thì in ra màn hình để dễ nhận biết hoặc cho chạy từng dòng lệnh để theo dõi sự thay đổi của các biến là hay nhất.

    bạn chạy tay tiếp thì nó sẽ ra như trên, lưu ý là nó so sánh với x chứ ko so sánh với a[(i+j)/2]
    Mà bạn gõ nhầm 47 thành 74 kìa ...
    Thì mình vẫn chạy từng phần tử mà. Chạy lần lượt từ i đến j. Chạy từ i nếu a[i]<x thì chạy tiếp. Tiếp đến j nếu a[j]>x lùi. Cứ thế lần lượt i,j nếu tại i mà a[i]>x thì dừng chạy j nếu a[j]<x dừng 2 cái đổi chỗ cho nhau rồi i tăng j lùi.
    Ở dãy số trên khi chạy i=4 lúc này a[4]=65 mà a[4]= chốt ở đây là x=65 theo code trên thì i sẽ dừng. j cũng lùi xuống 7 a[7]=36<x thì a[4] swap a[7] rồi i tăng j giảm tiếp tục.

  6. #6
    Ngày gia nhập
    02 2009
    Bài viết
    7

    Mặc định Thuật toán Quick Sort viết bằng C++, có lỗi làm sao sửa?

    mình đã xem lại bạn QuangHoang vòng swap đầu sai
    vòng swap đầu phải là
    42 23 74 11 36 58 94 65 99 87
    lúc này chạy đến i=6 j=5 thôi ko quicksort nữa
    tiếp tục đệ quy quicksort 2 mảng 42 23 47 11 36 58 và 94 65 99 87
    Cuối cùng mình cũng chạy đc rồi. thanks Chỉ tại lúc đầu băn khoăn chỗ tưởng sau khi swap vòng đầu nó phải chỉa ra 2 mảng 1 mảng > chốt 1 mảng <chốt hóa ra nhiêu khi ko như vậy

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. Thuật toán quick sort viết trong C/C++?
    Gửi bởi nhoccon.uit trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 8
    Bài viết cuối: 30-10-2012, 07:44 PM
  3. Chuyển giải thuật Quick Sort viết bằng C sang ngôn ngữ assembly của MIPS ISA?
    Gửi bởi lehoangphuc0601 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: 18-09-2012, 06:37 PM
  4. quick sort viết bằng C++ không chạy
    Gửi bởi cttd trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 1
    Bài viết cuối: 13-04-2011, 12:51 AM
  5. Code Quick Sort không đệ qui viết bằng C??
    Gửi bởi darlong trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 17
    Bài viết cuối: 04-06-2007, 11:54 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