Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 13 kết quả

Đề tài: Code sắp xếp bằng giải thuật quick sort trong lập trình C. while(A[i]<x) i++ là gì?

  1. #1
    Ngày gia nhập
    05 2007
    Bài viết
    1

    Mặc định Code sắp xếp bằng giải thuật quick sort trong lập trình C. while(A[i]<x) i++ là gì?

    C++ Code:
    1. #include <iostream.h>
    2. #include <conio.h>
    3. #include <iomanip.h>
    4. void quicksort(int A[],int l,int r)
    5. {
    6.      if(l>=r) return;
    7.      int i=l;
    8.      int j=r;
    9.      int x=A[(l+r)/2];//x=A[random(l-r)]
    10.      while(i<=j)
    11.      {
    12.                 while(A[i]<x) i++;
    13.                 while(A[j]>x) j--;
    14.                 if(i<=j)
    15.                 {
    16.                         int temp=A[i];
    17.                         A[i]=A[j];
    18.                         A[j]=temp;
    19.                         i++;j--;
    20.                 }
    21.      }
    22.      quicksort(A,l,j);
    23.      quicksort(A,i,r);
    24.      
    25. }
    26. main()
    27. {
    28.       int A[20],n,i;
    29.       cout<<"Nhap so phan tu n= ";
    30.       cin >>n;
    31.       for (i=0;i<n;i++)
    32.       {
    33.           cout << "A["<<i<<"]=";
    34.           cin>>A[i];
    35.       }
    36.       quicksort(A,0,n-1);
    37.       cout<<"Mang sau khi sap xep : ";
    38.      for(i=0;i<n;i++)
    39.       {
    40.       cout<<setw(7)<<A[i]<<"";
    41.       }
    42.       getch();
    43. }

    Bài này viết trong môi trường DEl C++.
    Tôi không hiểu chỗ này bạn nào giải thích giúp tôi với cảm ơn trước nha:
    while(A[i]<x) i++;
    while(A[j]>x) j--;
    Đã được chỉnh sửa lần cuối bởi hieubm : 30-05-2007 lúc 09:35 AM. Lý do: sợ tên pete xóa mất

  2. #2
    Ngày gia nhập
    12 2006
    Bài viết
    8

    Chịu khó chạy tay đi bạn...cái này bạn phải hiểu ý tửong của Quick sort cái đã...
    MÌnh bảo đảm sau khi bạn chạy tay bạn sẽ hiểu mà ko cần hỏi ai cả.

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

    while(A[i]<x) i++; ---> i sẽ dừng lại tại vị trí A[i]>=x
    while(A[j]>x) j--; ---> j sẽ dừng lại tại vị trí A[j]<=x
    tiếp theo , nếu i<j thì ta có A[i] >= x >= A[j] => cần phải hoán vị A[i],A[j];
    lúc học QuickSort mình hiểu như trên đó...^ ^

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

    Tôi không hiểu chỗ này bạn nào giải thích giúp tôi với cảm ơn trước nha:
    Code:
    while(A[i]<x) i++;
    while(A[j]>x) j--;
    Tư tưởng của Quick Sort là chọn một khóa nào đó nằm giữa đoạn ừ l đến r làm khóa chốt, sau đó đổi chỗ những phần tử bên trái khóa với phần tử bên phải khóa sao cho các phần tử bên trái khóa đó không lớn hơn khóa và bên phải khóa không nhỏ hơn khóa. Phần code này chính là phần tìm 2 phần tử đó, đoạn:
    Code:
    while(i<=j)
    ... bao bên ngoài chính là lặp đến khi nào không tìm được 2 phần tử thỏa mãn để đổi chỗ nữa.
    Vậy thôi

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

    while(A[i]<x) i++;//1
    while(A[j]>x) j--;//2
    tức là nếu thấy phần tử A[i]<x (mốc) tức là phần tử đó nhỏ hơn mốc đã nằm bên trái mốc nên bỏ qua và đi tiếp, nếu thấy phần tử A[j]>x (mốc) tức là phần tử lớn hơn mốc đã nằm bên trái mốc nên bỏ qua và đi tiếp, ngược lại thì dừng roài, khi vòng while 1 dừng ở một vị trí A[i](vì A[i]>x) thì chạy tiếp sang vòng while 2 vòng while 2 dừng tại 1 vị trí A[j]<x thì chạy tiếp cái hoán vị A[i] với A[j] (cái dòng lệnh tiếp theo 2 vòng while này). hix, nói thế thôi cứ chạy tay cái này là hiểu cho 1 dãy số, roài chạy = tay

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

    Mặc định Code sắp xếp bằng giải thuật quick sort trong lập trình C. while(A[i]<x) i++ là gì?

    Mình đọc trong sách Giáo trình giải thuật của Nguyễn Văn Linh cũng có nói về ý tưởng của QuickSort

    Nó khác một chút so với cách các bạn nêu
    - Chọn chốt: Chọn số lớn hơn trong 2 số khác nhau đầu tiên làm chốt
    - Cho l chạy từ trái sang cho đến khi gặp phần tử >= chốt, r chạy từ phải sang cho đến khi gặp phần tử nhỏ hơn chốt. Nếu l<r thì hoán vị 2 phần tử. Còn không thì lấy giá trị l làm phần tử mảng đầu tiên của mảng con thứ 2
    - Tách làm 2 mảng (x,l-1) va (l,y) rồi làm tiếp tục như vậy

    Mình đã thử với dãy số bất kỳ thì cách làm này cũng ko nhanh hơn so với cách làm của hackevotinh nhưng cài đặt thuật toán thì dài dòng hơn (phải có 1 hàm để tìm chốt!)

    Mình chạy tay thì ok nhưng cài đặt lại chạy tầm bậy
    Các bạn tham khảo code của mình và góp ý giùm mình với nha
    Thanks!

    C Code:
    1. #include <stdio.h>
    2. #include <conio.h>
    3. #include <string.h>
    4. #define max 100
    5.  
    6. int A[max];
    7.  
    8. void Output(int n)
    9. {
    10.     for(int i=0;i<n;i++)
    11.     printf("%d\t",A[i]);
    12. }
    13.  
    14. void Swap(int *u,int *v)
    15. {
    16.    int temp;
    17.    temp=*u;
    18.    *u=*v;
    19.    *v=temp;
    20. }
    21.  
    22.     int FindPivot(int x,int y)
    23. {
    24.     int j,k=x+1,f;
    25.         f=A[x];
    26.     while((k<=y)&&(A[k]==f))
    27.         k++;
    28.         if(k>y) j=0;
    29.         else
    30.         {
    31.          if(A[k]>f) j=k;
    32.              else j=x;
    33.         }
    34.         return j;
    35. }
    36.  
    37. int Partition(int x,int y,int p)
    38. {
    39.    int L,R;
    40.    L=x; R=y;
    41.    while(L<=R)
    42.    {
    43.     while(A[L]<p) L++;
    44.         while(A[R]>=p) R--;
    45.     if(L<R) Swap(&A[L],&A[R]);
    46.    }
    47.    return L;
    48. }
    49.  
    50. void QuickSort(int x,int y)
    51. {
    52.     int k,p,d=FindPivot(x,y);
    53.     if(d)
    54.        {
    55.                 p=A[d];
    56.         k=Partition(x,y,p);
    57.             QuickSort(x,k-1);
    58.             QuickSort(k,y);
    59.    }
    60. }
    61.  
    62. void main()
    63. {
    64.     char ch;
    65.         int n;
    66.     do
    67.    {
    68.     printf("n = "); scanf("%d",&n);
    69.     for(int i=0;i<n;i++)
    70.     {
    71.            printf("a[%d]= ",i);
    72.            scanf("%d",&A[i]);
    73.     }
    74.         printf("\n\nDay da cho\n");
    75.         Output(n);
    76.         printf("\nDay sau khi da sap xep\n");
    77.         QuickSort(0,n-1);
    78.         Output(n);
    79.         fflush(stdin);
    80.     printf("\nDo you want to continue? (y/n):\t");
    81.         scanf("%c",&ch);
    82.    }   while(ch=='y');
    83.     getch();
    84. }

  7. #7
    Ngày gia nhập
    08 2010
    Bài viết
    81

    Hiểu ý tưởng của QS+chạy tay là bạn hiểu ngay.

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

    Mặc định Quick sort

    Quick sort như vậy đúng với trường hợp trong dãy cần sắp xếp chốt là số duy nhất. vậy nếu trong trường hợp ví dụ như chọn chốt = 5 nhưng mà trong dãy có đến 2 số 5 nữa thì thuật toán đâu còn đúng?

  9. #9
    Ngày gia nhập
    12 2010
    Nơi ở
    Thiếu Thất
    Bài viết
    143

    Trích dẫn Nguyên bản được gửi bởi lightingking Xem bài viết
    Quick sort như vậy đúng với trường hợp trong dãy cần sắp xếp chốt là số duy nhất. vậy nếu trong trường hợp ví dụ như chọn chốt = 5 nhưng mà trong dãy có đến 2 số 5 nữa thì thuật toán đâu còn đúng?
    sao lại không đúng nữa hả bạn? ví dụ sắp xếp tăng dần, sau khi chọn chốt thì thằng nào bé hơn chốt thì quăng sang bên trái, thằng nào lớn hơn hoặc bằng thì quăng sang phải. có gì mà không còn đúng nữa?

  10. #10
    Ngày gia nhập
    03 2009
    Nơi ở
    Heaven
    Bài viết
    277

    Trích dẫn Nguyên bản được gửi bởi jumona Xem bài viết
    sao lại không đúng nữa hả bạn? ví dụ sắp xếp tăng dần, sau khi chọn chốt thì thằng nào bé hơn chốt thì quăng sang bên trái, thằng nào lớn hơn hoặc bằng thì quăng sang phải. có gì mà không còn đúng nữa?
    Visual C# Code:
    1. #include <stdio.h>
    2. #include <conio.h>
    3. #include <dos.h>
    4. #include <math.h>
    5.  
    6. #define max 100
    7. void swap(int *x, int *y);
    8. int getkeyposition(int i, int j);
    9. void qsort(int list[], int m, int n);
    10. void inputdata(int list[], int n);
    11. void printlist(int list[], int n);
    12. int main()
    13. {
    14.     int list[max], n;
    15.     //printf("Nhap so phan tu mang \n ");
    16.     scanf("%d",&n);
    17.     inputdata(list, n);
    18.     //printf("Da nhap \n");
    19.     //printlist(list,n);
    20.     qsort(list,0,n-1);
    21.     //printf("\n da sap xep \n");
    22. //printlist(list,n);
    23.     getch();
    24.     return 0;
    25. }
    26. void inputdata( int list[], int n)
    27. {
    28.     int i;
    29.     //printf(" Nhap cac phan tu:\n");
    30.     for(i =0;i<n;i++)
    31.     scanf("%d",&list[i]);
    32.     // xoa bo dem
    33.     fflush(stdin);
    34.  
    35. }
    36. void printlist( int list[], int n)
    37. {
    38.     int i;
    39.     //printf("Cac phan tu trong mang : \n");
    40.     for(i=0;i<n;i++)
    41.         printf("%d\n",list[i]);
    42.     //printf("\n");
    43. }
    44. void swap(int *x, int *y)
    45. {
    46.     int temp;
    47.     temp=*x;
    48.     *x=*y;
    49.     *y= temp;
    50. }
    51. int getkeyposition(int i, int j)
    52. {
    53.     return ((i+j)/2);
    54. }
    55. void qsort(int list[],int m,int n)// code oki. gio nhet vao dau ?
    56. {
    57.  
    58. int key,i,j,k;
    59. if(m<n)
    60. {
    61.     k=m;
    62.     //printlist(list,n);
    63.     swap(&list[m],&list[k]);
    64.     //printlist(list,n);
    65.     key=list[m];
    66.  
    67.     i=m+1;
    68.        
    69.     j=n;
    70.    
    71.     while(i<=j)
    72.     {
    73.         while((i<=n)&&(list[i]<=key))
    74.             i++;
    75.        
    76.         while((j>=m)&&(list[j]>key))
    77.             j--;
    78.         if(i<j)
    79.             swap(&list[i],&list[j]);
    80.            
    81.     }
    82.  
    83.     swap(&list[m],&list[j]);
    84.        
    85.     qsort(list,m,j-1);
    86.        
    87.     qsort(list,j+1,n);
    88.  
    89. }
    90.  
    91. }

    Mình muốn nó in ra mảng sau mỗi lần chọn lại khóa
    Nhưng cho hàm in vào sau chỗ chọn khóa mà không được?
    Vậy là sao nhỉ


    Visual C# Code:
    1. // quickSort.c
    2. #include <stdio.h>
    3.  
    4. void quickSort( int[], int, int);
    5. int partition( int[], int, int);
    6.  
    7.  
    8. void main()
    9. {
    10.     int a[] = { 7, 12, 1, -2, 0, 15, 4, 11, 9};
    11.  
    12.     int i;
    13.     printf("\n\nUnsorted array is:  ");
    14.     for(i = 0; i < 9; ++i)
    15.         printf(" %d ", a[i]);
    16.  
    17.     quickSort( a, 0, 8);
    18.  
    19.     printf("\n\nSorted array is:  ");
    20.     for(i = 0; i < 9; ++i)
    21.         printf(" %d ", a[i]);
    22.  
    23. }
    24.  
    25.  
    26.  
    27. void quickSort( int a[], int l, int r)
    28. {
    29.    int j;
    30.  
    31.    if( l < r )
    32.    {
    33.        // divide and conquer
    34.         j = partition( a, l, r);
    35. [COLOR="Red"][SIZE="5"]///////////////////// cho code in vào đây //////////////////////// Cũng ko chạy (:))[/SIZE][/COLOR]
    36.        quickSort( a, l, j-1);
    37.        quickSort( a, j+1, r);
    38.    }
    39.    
    40. }
    41.  
    42.  
    43.  
    44. int partition( int a[], int l, int r) {
    45.    int pivot, i, j, t;
    46.    pivot = a[l];
    47.    i = l; j = r+1;
    48.        
    49.    while( 1)
    50.    {
    51.        do ++i; while( a[i] <= pivot && i <= r );
    52.        do --j; while( a[j] > pivot );
    53.        if( i >= j ) break;
    54.        t = a[i]; a[i] = a[j]; a[j] = t;
    55.    }
    56.    t = a[l]; a[l] = a[j]; a[j] = t;
    57.    return j;
    58. }
    Tôi là con chim đến từ núi lạ
    Ngứa cổ hót chơi

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

  1. Thuật toán C++ Ưu nhược điểm các kiểu sort Interchange sort, Selection sort, Insertion sort, Sharke sort , Quick sort, Heap sort
    Gửi bởi duythanhnguyen trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 7
    Bài viết cuối: 23-09-2013, 01:16 AM
  2. Thuật toán quick sort viết trong C/C++?
    Gửi bởi nhoccon.uit trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 8
    Bài viết cuối: 30-10-2012, 07:44 PM
  3. Chuyển giải thuật Quick Sort viết bằng C sang ngôn ngữ assembly của MIPS ISA?
    Gửi bởi lehoangphuc0601 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: 18-09-2012, 06:37 PM
  4. code Thuật toán Quick Sort. Giúp em sửa lỗi?
    Gửi bởi chuong01 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 20-10-2009, 09:25 PM
  5. giải thuật quick sort trong DSLKD
    Gửi bởi persevering 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-04-2009, 12:07 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