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

Đề tài: Thuật toán Quicksort trong C. Cách đánh giá độ phức tạp của giải thuật, tính ổn định của thuật toán Quicksort?

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

    Mặc định Thuật toán Quicksort trong C. Cách đánh giá độ phức tạp của giải thuật, tính ổn định của thuật toán Quicksort?

    Xin các bác pro chỉ giáo giúp em thuật toán qsort voi
    Em rất cám ơn

  2. #2
    Ngày gia nhập
    04 2008
    Nơi ở
    Bốn bề là nhà
    Bài viết
    703

    Thuật toán dựa trên kỹ thuật chia để trị,được đề xuất bởi C.A.R Hoare
    Ý tưởng như sau:Sắp xếp dãy khóa k[1..n] thì có thể coi là sắp xếp đoạn từ chỉ số 1 tới chỉ số n trong dãy khóa đó.
    Nếu đoạn đó có ít hơn 2 khóa thì không cần làm gì cả,nếu đoạn đó có ít nhất 2 khóa,ta chọn một khóa ngẫu nhiên nào đó làm chốt(pivot).Mọi khóa nhỏ hơn khóa chốt được xếp vào vị trí đứng trước chốt,mọi khóa lớn hơn chốt được xếp vào vị trí sau chốt.Sau phép hoán chuyển như vậy thì đoạn đang xét được chia làm 2 đoạn khác rỗng mà mọi khóa trong đoạn đầu đều <=chốt và mọi khóa trong đoạn sau đều >=chốt.Vấn đề trở thành sắp xếp 2 đoạn mới được tạo ra (độ dài ngắn hơn độ dài đoạn ban đầu ) bằng phương pháp tương tự (gọi đệ quy)
    Độ phức tạp là O(n*lgn)
    Sau đây là code của mình:
    C Code:
    1. /* Tac gia C.A.R-Hoare    -1960 */
    2. #include <stdio.h>
    3. #include <stdlib.h>
    4. #define MAX 10000
    5. char *input="day_so.inp";
    6. float a[MAX];
    7. int N;
    8.  
    9. void quick_sort(int l,int r)
    10.      {
    11.                     float tg;
    12.                     float pivot;
    13.                     int i,j;
    14.                     if (l<r)                //truong hop suy bien
    15.                       {
    16.                             i=l;j=r;
    17.                             pivot=a[random(r-l+1)+l];    //Các bạn đặc biệt chú ý chỗ này
    18.                             do
    19.                                   {
    20.                                        while (a[i]<pivot) i++;
    21.                                        while (a[j]>pivot) j--;
    22.                                        if (i<=j)  
    23.                                           {
    24.                                                tg=a[i];
    25.                                                a[i]=a[j];
    26.                                                a[j]=tg;
    27.                                                i++;j--;
    28.                                           }
    29.                                   }
    30.                             while (i<=j);
    31.                             quick_sort(l,j);
    32.                             quick_sort(i,r);
    33.                        }
    34.      }
    35.                    
    36.                      
    37. void main()
    38.     {
    39.           FILE *f;
    40.           int i;
    41.           /* Doc du lieu vao tu FILE */    
    42.           f=fopen(input,"r");
    43.                     fscanf(f,"%d",&N);                    
    44.                     for (i=0;i<N;i++)
    45.                     fscanf(f,"%f",&a[i]);
    46.           fclose(f);
    47.           quick_sort(0,N-1);
    48.       /* in ra ket qua */
    49.       printf("\n Mang sau khi da sap xep la:\n");  
    50.           for (i=0;i<=N-1;i++)   printf("%f\n",a[i]);
    51.           getch();
    52.  
    53.     }
    54.  
    55. Các bạn lưu ý trong đoạn code của mình dùng "pivot=a[random(r-l+1)+l]",cái này rất nhiều sách không đề cập tới,thông thường người ta chọn chốt là phần tử đầu dãy a[l] hoặc cuối dãy a[r]
    56. nhưng với bộ dữ liệu đặc biệt sẽ làm tăng thời gian thực hiện chương trình,do đó mình chọn phần tử bất kì làm chốt.  
    57. Nếu có bug các bạn post lên để mình fix nha.

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

    Các anh cho em hỏi về cách đánh giá độ phức tạp của giải thuật ( Tính toán trên giấy ạ) với lại tính ổn định của thuật toán, Hiệu suất Quicksort trong trường hợp : Phân hoạch xấu nhất, Phân hoạch tốt nhất. Phân hoạch cân bằng.Phân hoạch trung bình (option). Em cám ơn các anh nhiều

  4. #4
    Ngày gia nhập
    11 2007
    Nơi ở
    Hà Nội
    Bài viết
    520

    cho mình hỏi chỗ
    pivot=a[random(r-l+1)+l];
    tại sao bạn không dùng luôn phần tử đầy tiên trong đoạn cần sắp xếp

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

  6. #6
    Ngày gia nhập
    04 2008
    Nơi ở
    Bốn bề là nhà
    Bài viết
    703

    Mặc định Thuật toán Quicksort trong C. Cách đánh giá độ phức tạp của giải thuật, tính ổn định của thuật toán Quicksort?

    mình giả sử :khi cần sắp xếp dãy tăng dần,mà dãy cần sắp có chiều giảm dần ,thì thuật toán trở thành O(n^2) bạn ạ.Đây chính là 1 trong các trường hợp xấu nhất của thuật toán ,vì vậy mình chọn 1 phần tử bất kì trong đoạn [l..r].

  7. #7
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    358

    Pivot không nhất thiết phải bằng một phần tử trong mảng. Ví dụ, để sắp xếp mảng gồm bốn số 1, 2, 4, 10, pivot cho lần gọi quicksort đầu tiên có thể chọn là 3.

    Phép chọn pivot cần có độ phức tạp O(1).

    Pivot tối ưu là median của mảng, tức là một giá trị sao cho một nửa số phần tử của mảng nhỏ hơn nó và nửa còn lại lớn hơn hoặc bằng nó. Nhưng bởi vì không có cách nào O(1) để tính được median, người ta chỉ có thể chọn pivot một cách hú họa và bất kể cách đó hú họa thế nào thì độ phức tạp của Quicksort trong trường hợp xấu nhất vẫn là O(n^2), không thể giảm được nữa.

    Do đó để giảm thời gian tính toán, nên chọn pivot theo những công thức rất đơn giản (chẳng hạn như lấy phần tử đầu tiên của mảng, lấy trung bình cộng của phần tử đầu tiên và cuối cùng trong mảng, hoặc lấy trung bình cộng của 4 phần tử trong mảng), không nên dùng công thức phức tạp nhất là công thức chứa lời gọi hàm (random,...) thì càng không nên.

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

  1. Thuật toán QuickSort
    Gửi bởi yongie36 trong diễn đàn Nhập môn lập trình Java
    Trả lời: 0
    Bài viết cuối: 05-09-2013, 09:13 PM
  2. Giải thuật quicksort triển khai trên C?
    Gửi bởi bachkhoa9x trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 03-08-2011, 11:27 PM
  3. Sử dụng đệ quy cho giải thuật QuickSort trong C?
    Gửi bởi lamrung trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 5
    Bài viết cuối: 25-03-2011, 09:29 PM
  4. Thuật toán QuickSort trong lập trình C
    Gửi bởi playboy trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 5
    Bài viết cuối: 15-10-2008, 10:41 PM
  5. Kỹ thuật cài đặt thuật toán heapsort và quicksort trên C?
    Gửi bởi Taylaptrinh trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 7
    Bài viết cuối: 06-04-2008, 06:50 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