[Solved]Lỗi hàm quicksort

[RedHatLinux9]

#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

[zkday2686]

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

[Lugiavn]

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'

[RedHatLinux9]

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

[zkday2686]

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

 while(a[i]<key) i++;      //tim`tu`dau`doan: khoa' >=chot 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

[RedHatLinux9]

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

#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]);
                                             }

[thanh_rio]

@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