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ì?

[hackevotinh]

#include <iostream.h>#include <conio.h>#include <iomanip.h>void quicksort(int A[],int l,int r){     if(l>=r) return;     int i=l;     int j=r;     int x=A[(l+r)/2];//x=A[random(l-r)]     while(i<=j)     {                while(A[i]<x) i++;                while(A[j]>x) j--;                if(i<=j)                {                        int temp=A[i];                        A[i]=A[j];                        A[j]=temp;                        i++;j--;                }     }     quicksort(A,l,j);     quicksort(A,i,r);     }main(){      int A[20],n,i;      cout<<"Nhap so phan tu n= ";      cin >>n;      for (i=0;i<n;i++)      {          cout << "A["<<i<<"]=";          cin>>A[i];      }      quicksort(A,0,n-1);      cout<<"Mang sau khi sap xep : ";     for(i=0;i<n;i++)      {      cout<<setw(7)<<A[i]<<"";      }      getch();}

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--;

[anggon]

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ả.

[HKuspc]

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 đó...^ ^

[hd_kinh_can]

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--;

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:

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

[soda_chanhmuoi]

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

[tom3cang]

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!

#include <stdio.h>#include <conio.h>#include <string.h>#define max 100 int A[max]; void Output(int n){    for(int i=0;i<n;i++)    printf("%d\t",A[i]);} void Swap(int *u,int *v){   int temp;   temp=*u;   *u=*v;   *v=temp;}     int FindPivot(int x,int y){    int j,k=x+1,f;        f=A[x];    while((k<=y)&&(A[k]==f))        k++;        if(k>y) j=0;        else        {         if(A[k]>f) j=k;             else j=x;        }        return j;} int Partition(int x,int y,int p){   int L,R;   L=x; R=y;   while(L<=R)   {    while(A[L]<p) L++;        while(A[R]>=p) R--;    if(L<R) Swap(&A[L],&A[R]);   }   return L;} void QuickSort(int x,int y){    int k,p,d=FindPivot(x,y);    if(d)       {                p=A[d];        k=Partition(x,y,p);            QuickSort(x,k-1);            QuickSort(k,y);   }} void main(){    char ch;        int n;    do   {    printf("n = "); scanf("%d",&n);    for(int i=0;i<n;i++)    {           printf("a[%d]= ",i);           scanf("%d",&A[i]);    }        printf("\n\nDay da cho\n");        Output(n);        printf("\nDay sau khi da sap xep\n");        QuickSort(0,n-1);        Output(n);        fflush(stdin);    printf("\nDo you want to continue? (y/n):\t");        scanf("%c",&ch);   }   while(ch=='y');    getch();}

[soldtheworld]

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

[lightingking]

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?

[jumona]

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?

[tesulakata]

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?

#include <stdio.h>#include <conio.h>#include <dos.h>#include <math.h> #define max 100void swap(int *x, int *y);int getkeyposition(int i, int j);void qsort(int list[], int m, int n);void inputdata(int list[], int n);void printlist(int list[], int n);int main(){    int list[max], n;    //printf("Nhap so phan tu mang \n ");    scanf("%d",&n);    inputdata(list, n);    //printf("Da nhap \n");    //printlist(list,n);    qsort(list,0,n-1);    //printf("\n da sap xep \n");//printlist(list,n);    getch();    return 0;}void inputdata( int list[], int n){    int i;    //printf(" Nhap cac phan tu:\n");    for(i =0;i<n;i++)    scanf("%d",&list[i]);    // xoa bo dem    fflush(stdin); }void printlist( int list[], int n){    int i;    //printf("Cac phan tu trong mang : \n");    for(i=0;i<n;i++)        printf("%d\n",list[i]);    //printf("\n");}void swap(int *x, int *y){    int temp;    temp=*x;    *x=*y;    *y= temp;}int getkeyposition(int i, int j){    return ((i+j)/2);}void qsort(int list[],int m,int n)// code oki. gio nhet vao dau ?{ int key,i,j,k;if(m<n){    k=m;    //printlist(list,n);    swap(&list[m],&list[k]);    //printlist(list,n);    key=list[m];     i=m+1;            j=n;        while(i<=j)    {        while((i<=n)&&(list[i]<=key))            i++;                while((j>=m)&&(list[j]>key))            j--;        if(i<j)            swap(&list[i],&list[j]);                }     swap(&list[m],&list[j]);            qsort(list,m,j-1);            qsort(list,j+1,n); } }

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ỉ

// quickSort.c#include <stdio.h> void quickSort( int[], int, int);int partition( int[], int, int);  void main() {    int a[] = { 7, 12, 1, -2, 0, 15, 4, 11, 9};     int i;    printf("\n\nUnsorted array is:  ");    for(i = 0; i < 9; ++i)        printf(" %d ", a[i]);     quickSort( a, 0, 8);     printf("\n\nSorted array is:  ");    for(i = 0; i < 9; ++i)        printf(" %d ", a[i]); }   void quickSort( int a[], int l, int r){   int j;    if( l < r )    {       // divide and conquer        j = partition( a, l, r);[COLOR="Red"][SIZE="5"]///////////////////// cho code in vào đây //////////////////////// Cũng ko chạy (:))[/SIZE][/COLOR]       quickSort( a, l, j-1);       quickSort( a, j+1, r);   }    }   int partition( int a[], int l, int r) {   int pivot, i, j, t;   pivot = a[l];   i = l; j = r+1;           while( 1)   {       do ++i; while( a[i] <= pivot && i <= r );       do --j; while( a[j] > pivot );       if( i >= j ) break;       t = a[i]; a[i] = a[j]; a[j] = t;   }   t = a[l]; a[l] = a[j]; a[j] = t;   return j;}