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

Đề tài: Kỹ thuật cài đặt thuật toán heapsort và quicksort trên C?

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

    Post Kỹ thuật cài đặt thuật toán heapsort và quicksort trên C?

    2 kỹ thuật sắp xếp này hầu hết trong các cuốn cấu trúc dữ liệu đều có.
    Mà vấn đề là nhiều khi sách in sai,hơn nữa lại trình bày hơi khó hiểu,riêng quicksort lại viết = đệ quy lại càng..khó.
    bạn nào có thể giúp mình viết code 2 kỹ thuật trên(có giải thích)..
    Xin cám ơn trước

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

    quicksort nè : Các thuật toán sắp xếp trong lập trình C | Cấu trúc dữ liệu và giải thuật
    còn heapsort:
    - là thuật toán sắp xếp chậm nhất trong số các thuật toán có độ phức tạp O(n*log cơ số 2 của n) //ko biết viết ký hiệu toán học này sao nữa :(
    - nhưng nó lại có ưu điểm vì tính thời gian của cài đặt không đòi hỏi vòng đệ quy phức tạp như Quicksort
    - Heap (đống) là một cây nhị phân gần hoàn chỉnh ( tức gần đầy í) và giá trị mỗi nút không bao giờ bé hơn giá trị các con.
    1/ Lưu trữ Heap bằng mảng: ec ec, cái này phải vẽ cây mà mình không biết vẽ cây trong đây, bạn đọc qua sách CTDL để biết heap được biểu diễn trong máy như thế nào nhá
    2/ Xây dựng đống Heap:
    - khôi phục tính chất đống của mảng a[n] từ nút i trỏ xuống

    C Code:
    1. void Heapify (int a[], int n, int i)
    2. {
    3.              int saved=a[i];        // lưu lại giá trị nút i
    4.              while(i<n/2) {         //a[i] phải là nút lá
    5.                      int child= 2*i + 1;
    6.                      if (child < n-1) {
    7.                             if(a[child]<a[child+1]) child +1;
    8.                                            }
    9.                      if(saved>=a[child]) break;
    10.                      a[i]=a[child];
    11.                      i=child;
    12.                                  }
    13.               c[i]=saved;            //gán giá trị của nút i vào vị trí mới
    14. }
    - BuildHeap:
    C Code:
    1. void BuildHeap (int a[], int n)
    2. {
    3.              int i;
    4.              for(i=n/2-1;i>=0;i--)
    5.                        Heapify(a,n,i);
    6. }
    3/Sắp xếp:
    Code:
    void HeapSort(int a[],int n)
    {
                  BuildHeap(a,n);
                  for(int i=n-1; i>=0; i--) {
                             swap(a[0],a[i]);
                             Heapify(a,i,0);
                                     }
    }
    4/ đánh giá: Heapsort luôn có độ phứctapj là O(n*log cơ số 2 của n) ^^

    Hmm Mình trình bày dễ còn khó hiểu hơn sách í . Bạn cứ đọc có j không hiểu hỏi nha
    MORE.........................

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

    Oạch,cám ơn bạn nhiều vì đã giúp đỡ.
    Có điều code...sai nhiều quá...

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

    Mình nghĩ đúng chứ sao mà sai?zzz

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

    Nghĩa là đưa đoạn code này vào VC++,báo lỗi
    Code:
    #include <stdio.h>
    
    #include <conio.h>
    void NhapMang(int a[],int &n)
    {
    printf("Nhap n:\n");
    scanf("%d",&n);
    for(int i=0;i<n;i++)
       {
       printf("a[%d]=",i);
       scanf("%d",&a[i]);
       }
    }
    void Heapify (int a[], int n, int i)
    {
                 int saved=a[i];        // luu l?i giá tr? nút i
                 while(i<n/2) {         //a[i] ph?i là nút lá
                         int child= 2*i + 1;
                         if (child < n-1) {
    						 if(a[child]<a[child+1]) {child +1;
                                               }
                         if(saved>=a[child]) break;
                         a[i]=a[child];
                         i=child;
                                     }
                  c[i]=saved;            //gán giá tr? c?a nút i vào v? trí m?i
    }
    void BuildHeap (int a[], int n)
    {
                 int i;
                 for(i=n/2-1;i>=0;i--)
                           Heapify(a,n,i);
    }
    void HeapSort(int a[],int n)
    {
                  BuildHeap(a,n);
                  for(int i=n-1; i>=0; i--) {
                             swap(a[0],a[i]);
                             Heapify(a,i,0);
                                     }
    }
    void main()
    {
    	int a[16],n;
    
    	NhapMang(a,n);
    	HeapSort(a,n);
    	for(int i=0;i<n;i++)
    	{
    		printf("%d ",a[i]);
    	}
    	getch();
    }
    mình đang tìm chỗ sai và sửa đây...

  6. #6
    Ngày gia nhập
    01 2008
    Nơi ở
    Gameloft Studio
    Bài viết
    294

    Mặc định Kỹ thuật cài đặt thuật toán heapsort và quicksort trên C?

    Mình đang đi thực tập mà ko hiểu về HeapSoft thì có thể cho là ngu hay không nhỉ?. Mình chỉ hiểu 2 thằng QuickSoft và ShellSoft là may rồi. Nhưng hình như QuickSoft nhanh nhất so với các thuật toán sắp xếp (chưa Test với HeapSoft vì ko hiểu nên không thèm CODE)

    Ai có thể giải tích HeapSoft cặn kẽ hơn mấy cuốn sách không??

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

    - Theo mình nghĩ thì các sách về Algorithm hay thì đã nói rất cặn kẽ rồi.Khó mà nói hay hơn được!...Nếu chưa tìm ra được cách học hay hơn thì theo mình cách để mình nhớ đc thuật toán đó là phải hiểu ý tưởng của nó và khi đã hiểu rồi thì làm siêng chạy bằng tay dùm mình.

    - Có khi là ghi lại cái mảng nhiều lần cũng ko sao nhưng mà 1 lần rồi nhớ mãi.

    Trích dẫn Nguyên bản được gửi bởi punkrock
    HeapSort là thuật toán sắp xếp chậm nhất trong số các thuật toán có độ phức tạp O(n*log cơ số 2 của n) //ko biết viết ký hiệu toán học này sao nữa :(
    cái này chưa chắc à nghen...
    Trích dẫn Nguyên bản được gửi bởi Sách CTDL Đỗ Xuân Lôi
    Mỗi thuật toán sắp xếp có điểm mạnh trong mỗi trạng thái của dãy sắp xếp...Nói một thuật toán sắp xếp nào luôn luôn tốt hơn các thuật toán khác là ko nên.
    Vd: dãy hầu như đã đc sắp xếp sẵn rồi thì ko nên dùng Quick.Trong khi đó dãy mà có thứ tự ngược với yêu cầu sắp xếp thì nên dùng Heap.

    - Còn chắc bạn nghe người ta nói đệ quy chạy chậm, tốn memory nhiều nên đã nghĩ tiêu cực về nó.Đệ Quy luôn có chỗ đứng của nó trong Lập trình và Toán học nói chung.Áp dụng của đệ quy trong tìm kiếm nhị phân cũng như trong QuickSort mang lại cho nó một sự đổi mới đối với ng lập trình trong tư tưởng.Nếu đệ quy là ko tốt thì làm sao mà tác giả của sắp xếp nhanh là Hoare lại tự tin đặt cho nó là QuickSort nhỉ?
    No way, No success..

  8. #8
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Ai có thể giải tích HeapSoft cặn kẽ hơn mấy cuốn sách không??
    Where's your best friend google ?

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

  1. 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
  2. cài đặt thuật toán quicksort trên kiểu dữ liệu chuổi
    Gửi bởi fanmaytinh trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 3
    Bài viết cuối: 15-10-2010, 11:39 PM
  3. Code thuật toán quicksort trên C++. Làm sao in số chẵn trước, số lẻ sau?
    Gửi bởi trungthuan trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 8
    Bài viết cuối: 17-08-2010, 11:43 PM
  4. Xây dựng thuật toán Quicksort trên C# như thế nào?
    Gửi bởi quockhanh.K94 trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 2
    Bài viết cuối: 12-08-2010, 10:04 PM
  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