User Tag List

+ Trả lời chủ đề
Trang 1/2 12 CuốiCuối
Hiện kết quả từ 1 tới 10 của 17

Chủ đề: Code mô tả thuật toán Quick Sort này sai ở đâu?

  1. #1
    .:: Grumpy svBKer ::. Avatar của 1973
    Tham gia ngày
    Mar 2010
    Bài gửi
    3.793

    Mặc định Code mô tả thuật toán Quick Sort này sai ở đâu?

    Chào mọi người, mình đang cài đặt thuật toán sắp xếp Quick Sort bằng C nhưng gặp vấn đề là nó không chạy với một số trường hợp. Mình cài đặt như sau:

    PHP Code:
    //sap xep su dung thuat toan QuickSort
    // m va n lan luot la chi so dau va chi so cuoi
    // goi ham sap xep: qSort(a, 0, n-1);
    int qSort(int *aint mint n)
    {
            
    int ij;
            
            if (
    m==n)
                    return 
    1;
            
    m;
            for (
    i=m+1i<=ni++)
                    if (
    a[i]<a[m])
                    {
                            
    j++;
                            
    swap(&a[i], &a[j]);
                    }
            
    swap(&a[m], &a[j]);
            
    qSort(amj);
            
    qSort(aj+1n);               
    }

    //doi cho 2 phan tu
    int swap(int *aint *b)
    {
            
    int tg;
            
    tg = *a;
            *
    = *b;
            *
    tg;
            return 
    0;

    Biên dịch (bằng gcc trên Linux) ngon lành nhưng khi chạy thì gặp vấn đề với 1 số loại bộ dữ liệu:

    Đối với bộ dữ liệu:
    Mã:
    a[0] = 2
    a[1] = 1
    a[2] = 3
    a[3] = 5
    a[4] = 4
    thì khi chạy gặp lỗi "Segmentation fault"

    Đối với bộ dữ liệu:
    Mã:
    a[0] = 5
    a[1] = 1
    a[2] = 6
    a[3] = 3
    a[4] = 2
    thì khi chạy lại sắp xếp được.

    Đoạn cài đặt này mình tham khảo trong cuốn "B.W.Kernighan, R.Pike - The Practice of Programming" trang 33, ai học Kĩ thuật lập trình chắc biết cuốn này.

    Nhờ mọi người giúp 1 tay tìm hiểu xem vấn đề là ở đâu
    Contact me:
    Email: sangnd [at] svBK.vn
    Personal website: My Blog | Chat với người lạ
    Facebook Page của Bách Khoa Forum: http://www.facebook.com/svbk.vn

  2. #2
    Khánh Hòa
    Tham gia ngày
    Apr 2010
    Bài gửi
    159

    Mặc định Re: Code mô tả thuật toán Quick Sort này sai ở đâu?

    bài này c sửa lại là if (m>=n)... là được, vì sẻ có bộ test mà m=n và củng có test m>n

  3. Tớ cảm ơn khanhoatink4 đã chia sẻ.


  4. #3
    Điều hành viên Avatar của iexplore
    Tham gia ngày
    Sep 2010
    Bài gửi
    208

    Mặc định Re: Code mô tả thuật toán Quick Sort này sai ở đâu?

    cứ code mấy bài liên quan đến con trỏ, cấp phát bộ nhớ cũng hay gặp lỗi "Segmentation fault" mà chưa tìm hiểu được nguyên nhân

  5. #4
    .:: Grumpy svBKer ::. Avatar của 1973
    Tham gia ngày
    Mar 2010
    Bài gửi
    3.793

    Mặc định Re: Code mô tả thuật toán Quick Sort này sai ở đâu?

    Cảm ơn Hòa, tớ sửa được rồi, vừa xong tớ dò từng bước với bộ test bị lỗi thì đúng là có trường hợp m>n thật. Đơn giản nếu test với bộ a[0] = 2, a[1] = 1 là đã lỗi rồi.

    Như vậy chỉ cần sửa m==n thành m>=n là chạy ngon lành

  6. #5
    svBK's Member
    Tham gia ngày
    Feb 2012
    Bài gửi
    26

    Mặc định Re: Code mô tả thuật toán Quick Sort này sai ở đâu?

    mấy thuật toán sắp xếp này hình như trong sách cấu trúc dữ liệu và giải thuật của thầy Nghĩa có mà

  7. #6
    HUT's Engineer
    Tham gia ngày
    Jun 2011
    Bài gửi
    686

    Mặc định Re: Code mô tả thuật toán Quick Sort này sai ở đâu?

    segment fault là lỗi truy cập vùng nhớ trái phép, cậu xem lại xem đã cấp phát đủ bộ nhớ chưa.

  8. #7
    .:: Grumpy svBKer ::. Avatar của 1973
    Tham gia ngày
    Mar 2010
    Bài gửi
    3.793

    Mặc định Re: Code mô tả thuật toán Quick Sort này sai ở đâu?

    Quote Nguyên văn bởi pkthanh92 Xem bài viết
    segment fault là lỗi truy cập vùng nhớ trái phép, cậu xem lại xem đã cấp phát đủ bộ nhớ chưa.
    Đâu Thanh, vấn đề này tớ đã giải quyết được từ #4 sau bài của Hòa rồi mà. Cậu xem lại nhé.

    Lỗi này là do tớ đã đệ quy gặp lỗi đệ quy vô hạn khi xuất hiện m>n.

  9. #8
    HUT's Engineer
    Tham gia ngày
    Jun 2011
    Bài gửi
    686

    Mặc định Re: Code mô tả thuật toán Quick Sort này sai ở đâu?

    segment fault là lỗi truy cập vùng nhớ trái phép, cái này tưởng ai cũng biết chứ nhỉ.

    khi gọi đệ quy, thông thường trạng thái của các lần gọi sẽ được lưu trữ lại trong bộ nhớ (stack), khi các trạng thái này quá nhiều (đệ quy khoảng 2000 lần), bộ nhớ ko đủ để lưu trữ nữa, -> phải cảnh báo lập trình viên -> chương trình cố tình nhẩy vào và sử dụng bộ nhớ trái phép để hệ điều hành sinh ra một ngắt cảnh cáo, cái ngắt(exception) đó chính là segment fault (trên linux, còn windows là access violent).

  10. Tớ cảm ơn pkthanh92 đã chia sẻ.


  11. #9
    svBK's Member
    Tham gia ngày
    Sep 2009
    Bài gửi
    47

    Mặc định Re: Code mô tả thuật toán Quick Sort này sai ở đâu?

    code qsort này có vẻ chưa tối ưu?

  12. #10
    Le chevalier du ciel Avatar của luugu
    Tham gia ngày
    Dec 2008
    Bài gửi
    717

    Mặc định Re: Code mô tả thuật toán Quick Sort này sai ở đâu?

    Bonus cho các chú các thể loại sorting nhé, làm từ hồi năm thứ 3

    PHP Code:
    //6.Ham void InsertionSort(int A[],int n,int I[]) voi I[]-Indies la mang cac chi so

    void InsertionSort(int A[],int N,int I[])
    {
        for(
    int i=1;i<N;i++)
        {
            
    x=A[I[]];
            
    k=I[i];
            
    int j=i+1;
            while(
    j>0&&A[I[j]]>x)
            {
                
    I[j+1]=j;
                
    j=j-1;
            }
            
    I[j+1]=k;
        }
    }

    //7.Ham void SelectionSort(intA[],int N,int I[]) voi I[]- Indies la mang cac chi so

    void Swap(inta,intb)
    {
        
    int t=a;
        
    a=b;
        
    b=t;
    }
    void SelectionSort(int A[],int N,int I[])
    {
        for(
    int i=0;i<N-1;i++)
        {
            
    int m=I[i];//m la vi tri cua phan tu min
            
    for(int j=i+1;j<N;j++)
            {
                if(
    A[I[j]]<A[I[m]]) m=j;
            }
            if(
    m!=iSwap(I[m],I[i]);
        }
    }

    //8.Ham void BubbleSort(int A[],int N,int I[]) voi I[]- Indies la mang cac chi so

    void BubbleSort(int A[],int N,int I[])
    {
        for(
    int i=0;i<N-1;i++)
        {
            
    int c=0//cho c=false
            
    for(int j=N;j>=i+1;j++)
                if(
    A[I[j]<A[I[j-1]])
                {
                    
    Swap(I[j-1],I[j]);
                    
    c=1//cho c=true
                
    }
            if(
    c==0) return;
            
        }

    On ne voit bien qu'avec le coeur, l'essentiel est invisible pour les yeux ~ ♥

+ Trả lời chủ đề
Trang 1/2 12 CuốiCuối

Thông tin chủ đề

Users Browsing this Thread

Hiện có 1 người đọc bài này. (0 thành viên và 1 khách)

Chủ đề tương tự

  1. Trả lời: 6
    Bài cuối: 31-03-2012, 05:35 PM
  2. Hướng dẫn các chức năng chính của Source Code C2C (Code To Coder)
    Gửi bởi hoaianvn trong mục Thư viện mã nguồn
    Trả lời: 1
    Bài cuối: 23-10-2009, 02:13 PM
  3. ai muốn nghe Quick&snow Show naò
    Gửi bởi nguyenduylong trong mục Jazz - Soul - Other
    Trả lời: 0
    Bài cuối: 06-01-2007, 11:32 AM

Từ khóa (Tag) của chủ đề này

Quyền viết bài

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


About svBK.VN

    Bách Khoa Forum - Diễn đàn thảo luận chung của sinh viên ĐH Bách Khoa Hà Nội. Nơi giao lưu giữa sinh viên - cựu sinh viên - giảng viên của trường.

Follow us on

Twitter Facebook youtube