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

Đề tài: [Solved]Lỗi hàm quicksort

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

    Mặc định [Solved]Lỗi hàm quicksort

    Code:
    #include<conio.h>
    #include<stdio.h>
    
    void input(int a[],int n);
    
    void swap(int *a,int *b);
    
    void quicksort(int L,int H,int a[]); 
        
    void sapxep(int a[],int n);
    
    void output(int a[],int n);
    
    main(){
           const int n=8;
           int a[n]; 
           input(a,n);
           sapxep(a,n);
           output(a,n);
           getch();
           }
           
    void input(int a[],int n){
         printf("nhap mang :\n");
         for(int i=0;i<n;i++){
                 printf("a[%d]=",i+1);
                 scanf("%d",&a[i]);
                 }
                 }
                                
    void swap(int *a,int *b){
         *a^=*b^=*a^=*b;
         }
       
    void quicksort(int L,int H,int a[]){
         while(L<H){           
                 int key=(L+H)/2;//khai bao va` chon khoa'
                 int i=L,j=H;
                 do{
                      while(a[i]<key) i++;      //tim`tu`dau`doan: khoa' >=chot
                      while(a[j]>key)j--;       //tim`tu`cuoi'doan: khoa' <=chot
                      if(i<=j){                             //Neu' i dung truoc j thi`dao? a[i] va`a[j]
                              if(i<j) swap(&a[i],&a[j]);    //sau phep'dao? nay`ta co'
                              i++;                          //a[i]<= key <=a[j]
                              j--;
                              }      
                      }while(i<=j);//den khi i>j thi`dung`
              //chon day~ ngan' goi de quy con` day~ dai` phan doan tiep'               
                  if(j-L<H-i){
                       quicksort(L,j,a);
                       L=i;}   
                  else {
                       quicksort(i,H,a);
                       H=j;}                
                    }
              
           }                                   
    void sapxep(int a[],int n){
         quicksort(0,n-1,a);
         }
        
    void output(int a[],int n){
         printf("In mang :\n");
         for(int i=0;i<n;i++)printf("%d\t",a[i]);
                                                 }
    Nó không in ra được
    PhI nGự4 trÊn gI4Ng Hồ
    t4 mẶc sỨc TiÊu Gi40
    4nH hÙnG kHônG uỐn gỐi
    Dù gÁi đẸp NhưỜnG nÀo

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

    Thuật toán này đã nói nhiều trong 4rum rồi bạn à. Bạn chịu khó Search trước khi post câu hỏi lên nhé.
    http://forums.congdongcviet.com/showthread.php?t=10442 Bạn so sánh với bài làm của mình là biết sai chỗ nào liền

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

    Nhìn hàm swap hơi bị cao siêu, chẳng biết đúng hay sai, nhưng ko ai làm vậy cả
    void swap(int *a,int *b){
    *a^=*b^=*a^=*b;
    }
    chỗ này chắc là sai nè
    int key=(L+H)/2;//khai bao va` chon khoa'

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

    Trích dẫn Nguyên bản được gửi bởi Lugiavn Xem bài viết
    Nhìn hàm swap hơi bị cao siêu, chẳng biết đúng hay sai, nhưng ko ai làm vậy cả


    chỗ này chắc là sai nè
    Hàm swap là học hỏi thôi
    Còn cái chỗ int key=(L+H)/2; vì sao sai thì mình chưa hiểu
    PhI nGự4 trÊn gI4Ng Hồ
    t4 mẶc sỨc TiÊu Gi40
    4nH hÙnG kHônG uỐn gỐi
    Dù gÁi đẸp NhưỜnG nÀo

  5. #5
    Ngày gia nhập
    09 2007
    Bài viết
    724

    Bạn làm biếng không chịu search trước khi Post câu hỏi lên!


    int key = (L+H)/2;

    sau đó bạn lại lấy
    C Code:
    1.  while(a[i]<key) i++;      //tim`tu`dau`doan: khoa' >=chot
    2.  while(a[j]>key)j--;
    thằng này đi so sánh <== Bạn chẳng hiểu gì về QuickSort cả

    ý tưởng của Quick Sort là nó phân hoạch ra thành các mảng con dựa vào 1 giá trị trong mảng đó là pivot. để xác xuất chọn phần tử pivot có giá trị phân hoạch cho 2 dãy con có số phần tử là "bằng nhau nhất" được cao người ta chọn phần tử này tại vị trí ở giữa mảng. (cái này chỉ là niềm hy vọng của lập trình viên thôi ch
    Đã được chỉnh sửa lần cuối bởi zkday2686 : 17-10-2008 lúc 04:27 PM.

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

    Mặc định [Solved]Lỗi hàm quicksort

    Chương trình sau vẫn in sai nếu mình nhập 1 7 4 2 6 5 8 9 0 12
    mà vẫn chưa tìm được lỗi mọi người tìm giùm mình với
    Code:
    #include<conio.h>
    #include<stdio.h>
    
    void input(int a[],int n);
    
    void swap(int *a,int *b);
    
    void quicksort(int L,int H,int a[]); 
        
    void sapxep(int a[],int n);
    
    void output(int a[],int n);
    
    main(){
           const int n=10;
           int a[n]; 
           input(a,n);
           sapxep(a,n);
           output(a,n);
           getch();
           }
           
    void input(int a[],int n){
         printf("nhap mang :\n");
         for(int i=0;i<n;i++){
                 printf("a[%d]=",i+1);
                 scanf("%d",&a[i]);
                 }
                 }
                                
    void swap(int *a,int *b){
         *a^=*b^=*a^=*b;
         }
       
    void quicksort(int L,int H,int a[]){
         while(L<H){           
                 int key=(L+H)/2;//khai bao va` chon chot'
                 int i=L,j=H;
                 do{
                      while(a[i]<a[key]) i++;      //tim`tu`dau`doan: khoa' >=chot
                      while(a[j]>a[key])j--;       //tim`tu`cuoi'doan: khoa' <=chot
                      if(i<=j){                             //Neu' i dung truoc j thi`dao? a[i] va`a[j]
                              if(i<j) swap(&a[i],&a[j]);    //sau phep'dao? nay`ta co'
                              i++;                          //a[i]<= key <=a[j]
                              j--;
                              }      
                      }while(i<=j);//den khi i>j thi`dung`
              //chon day~ ngan' goi de quy con` day~ dai` phan doan tiep'               
                  if(j-L<H-i){
                       quicksort(L,j,a);
                       L=i;}   
                  else {
                       quicksort(i,H,a);
                       H=j;}                
                    }
              
           }                                   
    void sapxep(int a[],int n){
         quicksort(0,n-1,a);
         }
        
    void output(int a[],int n){
         printf("In mang :\n");
         for(int i=0;i<n;i++)printf("%d\t",a[i]);
                                                 }
    PhI nGự4 trÊn gI4Ng Hồ
    t4 mẶc sỨc TiÊu Gi40
    4nH hÙnG kHônG uỐn gỐi
    Dù gÁi đẸp NhưỜnG nÀo

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

    @redhlinux9: tôi thấy nó có sai với vd của bạn đâu.
    nhưng vd này thì sai nè:3 5 1 6 9 7 1 6 5

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 ]Các anh em cho mình hỏi về Quicksort 1 tí!
    Gửi bởi romanticdevil88 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: 12-05-2008, 11: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