Công cụ bảo vệ mã nguồn .NET mạnh nhất, không thể unpack, miễn phí cho các khách hàng đầu tiên đăng ký.
Từ 1 tới 6 trên tổng số 6 kết quả

Đề tài: Thuật toán QuickSort trong lập trình C

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

    Mặc định Thuật toán QuickSort trong lập trình C

    Mình đã cài đặt chương trình ứng dụng QuickSort,sau khi chạy thì chương trình bị đứng.
    Mong mọi người giúp đỡ !!
    Đây là code:
    C Code:
    1. #include<stdio.h>
    2. #include<conio.h>
    3. #define max 100
    4. void quicksort(int a[], int n) ;
    5. void main()                  
    6. {
    7.     int a[],n;
    8.     printf("\nNhap so phan tu mang:") ;
    9.     scanf("%d", &n);
    10.     for(int i=0 ; i<n; i++)
    11.     {   printf("Nhap so:") ;
    12.         scanf("%d", &a[i]) ;
    13.         }
    14.     printf("\nMang truoc khi sap xep:\t") ;
    15.     for(i=0 ; i<n; i++)
    16.     {   printf("%d", a[i]) ;
    17.     }
    18.     printf("\nMang sau khi sap xep:\t");
    19.     quicksort(a, n);
    20.         getch();
    21. }
    22. void quicksort(int a[],int n)
    23. {
    24.     int l,r,i,j,t,x,stack[max],top=-1;
    25.         stack[++top]=n-1;stack[++top]=0;
    26.     do
    27.     {       l=stack[top--];r=stack[top--];
    28.         i=l;j=r;x=a[(l+r)/2];
    29.         do
    30.         {
    31.             while(a[i]<x) i++;
    32.             while(a[j]>x) j--;
    33.             if(i>=j){t=a[i];a[i]=a[j];t=a[j];i++;j--;}
    34.          }while(i<=j);
    35.         if(i<r){stack[++top]=r;stack[++top]=i;}
    36.         if(j>l){stack[++top]=j;stack[++top]=l;}
    37.       }while(top!=-1);
    38.   }
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.
    Đã được chỉnh sửa lần cuối bởi playboy : 14-10-2008 lúc 09:13 AM. Lý do: code thiếu i++;j--;

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

    chưa xét tới vội thuật toán của bạn như thế nào phần cài đặt đã bị die rùi

    C Code:
    1. while(top!=-1);
    lặp chết ở đây là do nguyên nhân chẳng khi nào top == -1 để mà thoát cả

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

    Trước hết mình đưa cho bạn hàm QuickSort viết bằng đệ qui.

    do các hàm của nó hơi dài nên zkday sẽ chia ra thành từng hàm nhỏ và post lên cho các bạn tiện theo dõi.

    C++ Code:
    1.  
    2. void quickSortRecursive(int a[], int n)
    3. {
    4.   q_sort(a, 0, n - 1);
    5. }
    6.  
    7. void q_sort(int a[], int left, int right)
    8. {
    9.     int pivot, iLeft, iRight;
    10.     iLeft = left; // lưu lại các giá trị left và right để tính toán
    11.     iRight = right;
    12.  
    13.     pivot = a[left]; // lấy vị trí của pivot là left
    14.     while (left < right) // trong khi left còn nhỏ hơn right thì làm
    15.     {
    16.         while ((a[right] >= pivot) && (left < right)) // nếu a[right]>=pivot và left còn nhỏ hơn right thì làm
    17.             right--; // giảm right
    18.         if (left != right) // nếu left != right thì làm
    19.         {
    20.             a[left] = a[right]; //gán giá trị cho left
    21.             left++; // tăng left lên
    22.         }
    23.         //tương tự
    24.         while ((a[left] <= pivot) && (left < right))
    25.             left++;
    26.         if (left != right)
    27.         {
    28.             a[right] = a[left];
    29.             right--;
    30.         }
    31.     }
    32.     a[left] = pivot; // gán a[left] lại giá trị pivot
    33.  
    34.     pivot = left;// dùng biến pivot để lưu lại giá trị của left
    35.     left = iLeft; // đưa left lại giá trị của iLeft để gọi lại đệ qui
    36.     right = iRight; // đưa right lại giá trị của iRight để gọi lại đệ qui
    37.  
    38.     if (left < pivot)
    39.         q_sort(a, left, pivot-1);// gọi đệ qui q_sort với nửa mảng đầu của mảng cần sort
    40.     if (right > pivot)
    41.         q_sort(a, pivot+1, right); // gọi đệ qui q_sort với nửa mảng đầu của mảng cần sort
    42. }
    Đã được chỉnh sửa lần cuối bởi zkday2686 : 15-10-2008 lúc 01:15 AM.

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

    Còn đây là hàm QuickSort viết không đệ qui.
    Lưu ý trong chương trình có dùng lớp stack của STL. chi tiết tham khảo tại MSDN .


    C++ Code:
    1.  
    2. void QuickSortUnRecursive(int a[],int n)
    3. {
    4.     int left,right,iLeft,iRight;   
    5. // khai báo 2 đối tượng thuộc lớp stack với mỗi phần tử là kiểu int.
    6.     stack<int> stackLeftIndex;
    7.     stack<int> stackRightIndex;
    8.    
    9.     stackLeftIndex.push(0); //Push phần tử thứ 0: left vào stackLeft
    10.     stackRightIndex.push(n-1); // Push phần tử thứ n-1: right vào stackRight
    11.    
    12.     do
    13.     {
    14.         left = stackLeftIndex.top(); // lấy phần tử đầu ra
    15.         right = stackRightIndex.top(); // lấy phần tử đầu ra
    16.        
    17.         int pivot;// phần tử pivot
    18.  
    19.         iLeft = left;
    20.         iRight = right;
    21.  
    22.         pivot = a[left];
    23.  
    24.         while (left < right)
    25.         {
    26.             while ((a[right] >= pivot) && (left < right))
    27.                 right--;
    28.             if (left != right)
    29.             {
    30.               a[left] = a[right];
    31.               left++;
    32.             }
    33.             while ((a[left] <= pivot) && (left < right))
    34.                 left++;
    35.             if (left != right)
    36.             {
    37.               a[right] = a[left];
    38.               right--;
    39.             }
    40.         }
    41.         a[left] = pivot;
    42.  
    43.         pivot = left;
    44.         left = iLeft;
    45.         right = iRight;
    46.  
    47.         //Xóa phần tử trên cùng của Stack ra.
    48.         stackRightIndex.pop();
    49.         stackLeftIndex.pop();
    50.  
    51.         if (left < pivot)
    52.             q_sort(a, left, pivot-1);
    53.         if (right > pivot)
    54.             q_sort(a, pivot+1, right);
    55.  
    56.         if(left<pivot){
    57. // đẩy 2 vị trí tuơng ứng vào Stack để xét sau.
    58.             stackLeftIndex.push(left);
    59.             stackRightIndex.push(pivot-1);
    60.         }
    61.         if(right>pivot)
    62.         {
    63. //Đẩy 2 vị trí tương ứng vào Stack để xét sau
    64.             stackLeftIndex.push(pivot+1);
    65.             stackLeftIndex.push(right);
    66.         }
    67.  
    68.     } while(!stackRightIndex.empty()); // Nếu 1 trong 2 Stack còn khác rỗng thì còn làm
    69. }

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

    Các hàm còn lại để tạo thành một chương trình hoàn chỉnh


    C++ Code:
    1.  
    2. //khai báo các thư viện cần thiết
    3. #include<iostream>
    4. #include <stack>
    5.  
    6.  
    7. #define max 100
    8.  
    9. //Khai báo các Prototype của các hàm sử dụng trong chương trình.
    10.  
    11. void QuickSortRecursive(int a[], int n);
    12. void QuickSortUnRecursive(int a[],int n);
    13. void NhapMang(int a[],int &n);
    14. void XuatMang(int a[], int n);
    15. void q_sort(int a[], int left, int right);
    16.  
    17. using namespace std;
    18.  
    19. // viết hàm chính
    20. int main()                  
    21. {
    22.  
    23.     int a[max],n;
    24.  
    25.     NhapMang(a,n);
    26.  
    27.     cout<<"Mang truoc khi xuat phat";
    28.     XuatMang(a,n);
    29.     cout<<"\nMang truoc khi sap xep:\t";
    30.     XuatMang(a,n);
    31.     cout<<endl<<"Mang sau khi sap xep:";
    32.        
    33.     QuickSortUnRecursive(a, n);
    34.     //QuickSortRecursive(a,n);
    35.     XuatMang(a,n);
    36.     return 0;
    37. }
    38.  
    39. //viết hàm Nhập mảng
    40. void NhapMang(int a[],int &n)
    41. {
    42.     cout<<"Nhap so phan tu cua mang:";
    43.     cin>>n;
    44.  
    45.     for(int i=0 ; i<n; i++)
    46.     {
    47.         cout<<"Nhap pha tu a[" << i <<"]";
    48.         cin >> a[i];       
    49.     }
    50. }
    51. //Viết hàm xuất mảng
    52. void XuatMang(int a[], int n)
    53. {
    54.     cout<<endl;
    55.     for(int i=0 ; i<n; i++)
    56.         cout<<"\t"<<a[i] ;
    57. }


    Lưu ý: dùng các compiler hỗ trợ C++ (tốt nhất nên dùng VSC++).

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

    Mặc định Thuật toán QuickSort trong lập trình C

    Cảm ơn Zk đã nhiệt tình giúp đỡ !!
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.

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. Bài tập C++ Sử dụng Thuật toán QuickSort sắp xếp danh sách đối tượng
    Gửi bởi nhotboy999 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: 25-04-2013, 03:45 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. Trả lời: 6
    Bài viết cuối: 04-05-2008, 08:04 AM
  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