Trang 1 trên tổng số 3 123 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 29 kết quả

Đề tài: Các giải thuật sắp xếp - Lý thuyết và cài đặt trên C

  1. #1
    Ngày gia nhập
    10 2006
    Nơi ở
    Hà Nội
    Bài viết
    146

    Angry Các giải thuật sắp xếp - Lý thuyết và cài đặt trên C

    Thấy nhu cầu về các giải thuật sắp xếp và tìm kiếm là nhiều, và hơn nữa viết thành bài cho nó hoàn chỉnh cho tiện tham khảo đối với các bạn mới học, nên mình viết bài này.
    Đáng lẽ là post bên box cấu trúc dữ liệu và giải thuật, tuy nhiên thấy bên ấy ít người vào hơn, và hơn nữa ở đây thuộc quyền quản lí của mình nên mình đưa vào box này.
    Bài này là tương đối dài, do đó mình sẽ post mỗi lần một giải thuật thôi.


    I - Giảt thuật Selection sort
    Nội dung của phương pháp này là lần lượt chọn 1 phần tử nhỏ nhất trong dãy chỉ số k1, k2, …, kn với i=0,1…,n; ki¬<ki+1<….,kn và đổi chỗ cho phần tử thứ ki. Như vậy sau j=n-1 lần chọn chúng ta dãy khoá được sắp xếp tăng dần. Các bước thực hiện như sau:
    Lần chọn thứ 0: Tìm trong khoảng từ 0 đến n-1 bằng cách thực hiện n-1 lần so sánh để xác định phần tử min0 và đổi chỗ cho phần tử ở vị trí 0
    Lần chọn thứ 1: Tìm trong khoảng từ 1 đến n-1 bằng cách thực hiện n-2 lần so sánh để xác định phần tử min1 và đôỉ chỗ cho phần tử vị trí 1
    …………………….
    Lần chọn thứ i : tìm trong khoảng từ i đến n-1 bằng cách thực hiện n-i lần so sánh để xác định phần tử mini và đổi chỗ cho phần tử vị trí thứ i
    Lần chọn thứ n-2: Tìm trong khoảng n-2 đến n-1 bằng cách thực hiện 1 lần so sánh để xác định phần tử min(n-2) và đổi chỗ cho phần tử vị trí thứ n-2
    Độ phức tạp của thuật toán này là: Cmin=Cmax=Ctb=n(n-1)/2
    Chính vì thế nên thuật toán có tên là sắp xếp lựa chọn

    Cài đặt thuật toán trên tập số nguyên như sau:
    C Code:
    1. #include<stdio.h>
    2. #include<conio.h>
    3. #include<stdlib.h>
    4. #include<alloc.h>
    5. #include<dos.h>
    6. void Select(int *, int);
    7. void Init(int *, int);
    8. void In(int *, int);
    9. void Init(int *A, int n){
    10.     int i;
    11.     printf("\n Tao lap day so:");
    12.     for (i=0; i<n;i++){
    13.         A[i]=random(1000);
    14.         printf("%5d",A[i]);
    15.     }
    16.     delay(1000);
    17. }
    18. void Select(int *A, int n){
    19.     register i,j,temp;
    20.     for(i=0;i<n-1;i++){
    21.         for (j=i+1;j<n;j++){
    22.             if(A[i]>A[j]){
    23.                 temp=A[i];
    24.                 A[i]=A[j];
    25.                 A[j]=temp;
    26.             }
    27.         }
    28.         In(A,n);
    29.     }
    30. }
    31. void In(int *A, int n){
    32.     register int i;
    33.     for(i=0;i<n;i++)
    34.         printf("%5d",A[i]);
    35.     delay(1000);
    36. }
    37. void main(void){
    38.     int *A,n;clrscr();
    39.     printf("\n Nhap n="); scanf("%d",&n);
    40.     A=(int *) malloc(n*sizeof(int));
    41.     Init(A,n);Select(A,n);
    42.     free(A);
    43. }
    (Còn nữa)

  2. #2
    Ngày gia nhập
    09 2006
    Nơi ở
    /usr/share/.hack@
    Bài viết
    1,433

    Mặc định Giảt thuật Selection sort

    Mình thu gọn lại ý kiến của bạn cho dễ hiểu hơn :
    C Code:
    1. void selectionSort( int list[], int last )
    2. {
    3.      int smallest;
    4.      int temp,current,walk;
    5.      
    6.      for ( current = 0 ; current < last ; current++ ) //  Scan all items in array
    7.      {
    8.          smallest = current;
    9.          
    10.          for ( walk = current + 1 ; walk <= last ; walk++ ) // sort
    11.              if ( list[walk] < list[smallest] ) smallest = walk; //exhange if it is suitable
    12.          
    13.          temp = list[current];
    14.          list[current] = list[smallest];
    15.          list[smallest] = temp;
    16.      }
    17.      return;
    18. }

    Có gì sai sót sửa giùm nha ^_^!

  3. #3
    Ngày gia nhập
    10 2006
    Nơi ở
    Hà Nội
    Bài viết
    146

    Thumbs down Giải thuật Insertion sort

    II- Giải thuật Insertion sort

    Giải thuật này dựa trên kinh nghiệm của những nguời chơi bài. Khi trên tay có i-1 lá bài đã được sắp xếp dang trên tay, nay ta thêm lá bài thứ i thì lá bài đó với là bài i-1, i-2,… để tìm được vị trí thích hợp để chèn vào cho đúng thứ tự.

    Với nguyên tắc sắp xếp như trên thì giải thuật sắp xếp như sau:
    Lấy phần tử đầu tiên i0 làm khởi tạo
    Lấy tiếp phần tử i1 chọn vị trí thích hợp của phần tử i1 trong tập 2 phần tử và thực hiện đổi chỗ .
    ……………….
    Lấy tiếp phần tử thứ ik, chọn vị trí thích hợp của phần tử ik trong tập k+1 phần tử và thực hiện đổi chỗ.
    Dãy sẽ được sắp xếp hoàn toàn sau n-1 bước chèn.
    Độ phức tạp bé nhất là : Cmin = n-1
    Độ phức tạp lớn nhất là : n(n-1)/2 = O(n^2)
    Độ phức tạp trung bình là: (n^2+n-2)/4=O(n^2)

    Thuật toán được cài đặt như sau: (Trên tập mẫu là số nguyên)
    C Code:
    1. #include    <stdio.h>
    2. #include    <conio.h>
    3. #include    <stdlib.h>
    4. #include    <alloc.h>
    5. #include    <dos.h>
    6. void Insert(int *, int);
    7. void Init(int *, int);
    8. void In(int *, int);
    9. void Init(int *A, int n){
    10.     int i;
    11.     printf("\n Tao lap day so:");
    12.     for (i=0; i<n;i++){
    13.         A[i]=random(1000);
    14.         printf("%5d",A[i]);
    15.     }
    16.     delay(1000);
    17. }
    18. void Insert(int *A, int n){
    19.     register i,j,temp;
    20.     for (i=1;i<n;i++){
    21.         temp=A[i];
    22.         for(j=i-1;j>=0 && temp<A[j];j--)
    23.             A[j+1]=A[j];
    24.         A[j+1]=temp;
    25.         printf("\n");
    26.         In(A,i+1);
    27.     }
    28. }
    29. void In(int *A, int n){
    30.     register int i;
    31.     for(i=0;i<n;i++)
    32.         printf("%5d",A[i]);
    33.     delay(1000);
    34. }
    35. void main(void){
    36.     int *A,n;clrscr();
    37.     printf("\n Nhap n="); scanf("%d",&n);
    38.     A=(int *) malloc(n*sizeof(int));
    39.     Init(A,n);Insert(A,n);
    40.     free(A);
    41. }

  4. #4
    Ngày gia nhập
    09 2006
    Nơi ở
    /usr/share/.hack@
    Bài viết
    1,433

    Mặc định Giải thuật Insertion sort

    Mình thu gọn lại nhé :

    C Code:
    1. void insertionSort ( int list[] , int last )
    2. {
    3. // Statements
    4. // Local Declarations
    5.      int walk;
    6.      int temp;
    7.      bool located;
    8.  
    9. // Statements
    10.      // Outer Loop
    11.     for ( int current = 1 ; current <= last ; current++ )
    12.     {
    13.      // Inner loop ; Select and move 1 element
    14.           located = false;
    15.           temp = list[current];
    16.           for ( walk = current - 1 ; walk >= 0 && located ; )
    17.               if ( temp < list[walk] )
    18.                  {
    19.                   list[walk + 1] = list[walk] ;
    20.                   walk--;
    21.                  } // if
    22.               else
    23.                   located = true ;
    24.           list[walk + 1] = temp ;
    25.      } // for
    26.       return;
    27. }
    None!

  5. #5
    Ngày gia nhập
    10 2006
    Nơi ở
    Hà Nội
    Bài viết
    146

    Thumbs down Giải thuật Bubble Sort

    III- Giải thuật Bubble Sort (sắp xếp theo phương pháp sủi bọt)

    Giải thuật này thực hiện bằng cách đổi chỗ liên tiếp hai phần tử kế cận nhau khi chúng ngược thứ tự. Quá trình thực hiện được duyệt từ đáy lên đỉnh, như vậy sau lần duyệt thứ nhất phần tử lớn nhất sẽ xếp đúng ở vị trí n-1, ở lần duyệt thứ k thì k phần tử lớn nhất đã xếp đúng vị trí n-1, n-2, …, n-k+1. Sau lần duyệt thứ n-1 thì toàn bộ n phần tử sẽ được sắp xếp. Với phương pháp này các phần tử nhỏ sẽ được nổi dần lên như là nước sủi bọt nhờ đó nó có tên gọi là phương pháp sủi bọt.
    Độ phức tạp của thuật toán là : Cmin = Cmax = Ctb = n(n-1)/2

    Chương trình cài đặt được mô tả như sau:
    C Code:
    1. #include    <stdio.h>
    2. #include    <conio.h>
    3. #include    <stdlib.h>
    4. #include    <alloc.h>
    5. #include    <dos.h>
    6. void Bubble(int *, int);
    7. void Init(int *, int);
    8. void In(int *, int);
    9. void Init(int *A, int n){
    10.     int i;
    11.     printf("\n Tao lap day so:");
    12.     for (i=0; i<n;i++){
    13.         A[i]=random(1000);
    14.         printf("%5d",A[i]);
    15.     }
    16.     delay(1000);
    17. }
    18. void Bubble(int *A, int n){
    19.     register i,j,temp;
    20.     for (i=1; i<n; i++){
    21.         for (j=n-1; j>=i; j--){
    22.             if (A[j-1]>A[j]){
    23.                 temp=A[j-1];
    24.                 A[j-1]=A[j];
    25.                 A[j]=temp;
    26.             }
    27.         }
    28.         printf("\n Ket qua lan:%d", i);
    29.         In(A,n);
    30.     }
    31. }
    32. void In(int *A, int n){
    33.     register int i;
    34.     for(i=0;i<n;i++)
    35.         printf("%5d",A[i]);
    36.     delay(1000);
    37. }
    38. void main(void){
    39.     int *A,n;clrscr();
    40.     printf("\n Nhap n="); scanf("%d",&n);
    41.     A=(int *) malloc(n*sizeof(int));
    42.     Init(A,n);Bubble(A,n);
    43.     free(A);
    44. }

  6. #6
    Ngày gia nhập
    10 2006
    Nơi ở
    Hà Nội
    Bài viết
    146

    Mặc định Giải thuật Shaker Sort

    IV - Giải thuật Shaker Sort

    Là cải tiến của thuật toán Bubble Sort, trong đó sau mỗi lần duyệt đi để xếp đúng vị trí phần tử lớn nhất chúng ta thực hiện duyệt lại để sắp xếp đúng vị trí phần tử nhỏ nhất. Dãy sẽ được sắp xếp sau [n/2] +1 lần duyệt.

    Chương trình mô tả thuật toán như sau :
    C Code:
    1. #include    <stdio.h>
    2. #include    <conio.h>
    3. #include    <stdlib.h>
    4. #include    <alloc.h>
    5. #include    <dos.h>
    6. void Shaker(int *, int);
    7. void Init(int *, int);
    8. void In(int *, int);
    9. void Init(int *A, int n){
    10.     int i;
    11.     printf("\n Tao lap day so:");
    12.     for (i=0; i<n;i++){
    13.         A[i]=random(1000);
    14.         printf("%5d",A[i]);
    15.     }
    16.     delay(1000);
    17. }
    18. void Shaker(int *A, int n){
    19.     register i,j,temp, exchange;
    20.     do {
    21.         exchange=0;
    22.         for (i=n-1; i>0; i--){
    23.             if (A[i-1]>A[i]){
    24.                 temp=A[i-1];
    25.                 A[i-1]=A[i];
    26.                 A[i]=temp;
    27.                 exchange=1;
    28.             }
    29.         }
    30.         for(j=1; j<n;j++){
    31.             if (A[j-1]>A[j]){
    32.                 temp=A[j-1];
    33.                 A[j-1]=A[j];
    34.                 A[j]=temp;
    35.                 exchange=1;
    36.             }
    37.         }
    38.         printf("\n Ket qua lan:");
    39.         In(A,n);
    40.     }while(exchange);
    41. }
    42. void In(int *A, int n){
    43.     register int i;
    44.     for(i=0;i<n;i++)
    45.         printf("%5d",A[i]);
    46.     delay(1000);
    47. }
    48. void main(void){
    49.     int *A,n;clrscr();
    50.     printf("\n Nhap n="); scanf("%d",&n);
    51.     A=(int *) malloc(n*sizeof(int));
    52.     Init(A,n);Shaker(A,n);
    53.     free(A);
    54. }

  7. #7
    Ngày gia nhập
    10 2006
    Nơi ở
    Hà Nội
    Bài viết
    146

    Mặc định Giải thuật Quick sort

    V - Giải thuật Quick sort

    Phương pháp sắp xếp này là phương pháp sắp xếp kiểu phân đoạn, là một cải tiến của phương pháp Selection sort .

    Nội dung chủ đạo của phương pháp này là chọn ngẫu nhiên một phần tử nào đó của dãy làm khoá chốt. Tính từ khoá chốt, các phần tử nhỏ hơn khoá được sắp xếp trước chốt (Đầu dãy) , các phần tử còn lại thì xếp sau chốt (cuối dãy).

    Để làm được việc đó các phần tử trong dãy sẽ được so sánh với khoá chốt và trao đổi vị trí cho nhau hoặc cho khoá chốt nếu phần tử đó lớn hơn chốt mà lại nằm trước chốt hoặc nhở hơn chốt mà lại nằm sau chốt. Khi việc đổi chỗ lần đầu tiên thực hiện xong thì dãy hình thành hai đoạn : một đoạn bao gồm các phần tử nhỏ hơn chốt, và một đoạn gồm các phần tử lớn hơn chốt. Còn chốt thì chính là vị trí của phần tử trong dãy đc sắp xếp.

    Áp dụng kĩ thuật trên cho mỗi đoạn trước chốt và sau chốt cho tới khi các đoạn chỉ còn 2 phần tử nữa thì việc ghi nhớ là kô cần thiết nữa.
    Dãy sẽ được sắp xếp khi tất cả các đoạn được xử lí xong.

    Độ phức tạp của thuật toán:
    Trường hợp tốt nhất : Cmax = Ctb = O(nlogn)
    Trường hợp xấu nhất Cmin = k*O(n^2)

    Sau đây là cài đặt thuật toán trên C theo đệ qui:
    C Code:
    1. #include    <stdio.h>
    2. #include    <conio.h>
    3. #include    <stdlib.h>
    4. #include    <alloc.h>
    5. #include    <dos.h>
    6. void qs(int *, int ,int);
    7. void Quick(int *,int );
    8. void Init(int *, int);
    9. void In(int *, int);
    10. void Init(int *A, int n){
    11.     int i;
    12.     printf("\n Tao lap day so:");
    13.     for (i=0; i<n;i++){
    14.         A[i]=random(1000);
    15.         printf("%5d",A[i]);
    16.     }
    17.     delay(1000);
    18. }
    19. void Quick(int *A, int n){
    20.     qs(A,0,n-1);
    21. }
    22. void qs(int *A, int left,int right) {
    23.     register i,j;int x,y;
    24.     i=left; j=right;
    25.     x= A[(left+right)/2];
    26.     do {
    27.         while(A[i]<x && i<right) i++;
    28.         while(A[j]>x && j>left) j--;
    29.         if(i<=j){
    30.             y=A[i];A[i]=A[j];A[j]=y;
    31.             i++;j--;
    32.         }
    33.     } while (i<=j);
    34.     if (left<j) qs(A,left,j);
    35.     if (i<right) qs(A,i,right);
    36. }
    37. void In(int *A, int n){
    38.     register int i;
    39.     for(i=0;i<n;i++)
    40.         printf("%5d",A[i]);
    41.     delay(1000);
    42. }
    43. void main(void){
    44.     int *A,n;clrscr();
    45.     printf("\n Nhap n="); scanf("%d",&n);
    46.     A=(int *)malloc(n*sizeof(int));
    47.     Init(A,n);Quick(A,n);printf("\n");
    48.     In(A,n);getch();
    49.     free(A);
    50. }

  8. #8
    Ngày gia nhập
    10 2006
    Nơi ở
    Hà Nội
    Bài viết
    146

    Mặc định Giải thuật Heap Sort

    VII - Giải thuật Heap Sort
    Heap là một cây nhị phân được biểu diễn bằng một mảng mà mảng đó biểu diễn một cây nhị phân hoàn chỉnh sao cho khoá ở node cha bao giờ cũng lớn hơn khoá của node con của nó.

    Sắp xếp kiểu Heap Sort được tiến hành qua hai giai đoạn. Giai đoạn đầu tiên cây nhị phân biểu diễn bảng khoá được biến đổi đưa về một heap. Như vậy, đối với heap nếu j là chỉ số của node con thì [j/2] là chỉ số của node cha. Như vậy node gốc của heap là khoá có giá trị lớn nhất trong mọi node.

    Để chuyển từ cây nhị phân bình thường thành một cây nhị phân heap. Chúng ta thực hiênh duyệt từ dưới lên (bottom up). Node lá đương nhiên là một heap. Nếu cây con bên trái và cây con bên phải đều là một heap thì toàn bộ cây cũng là một heap. Như vậy để tạo thành một heap chúng ta thực hiện so sánh nội dung node bên trái , nội dung node bên phải với node cha của nó, node nào có giá trị lớn hơn sẽ được thay đổi làm node cha. Quá trình lần lượt ngược lại cho tới khi gặp node gốc thì nội dung node gốc chính là khoá có giá trị lớn nhất.

    Giai đoạn hai của thuật giải là đưa nội dung của node gốc về vị trí cuối cùng và nội dung của node cuối cùng được thay vào cị trí node gốc sau đó coi như node cuối cùng đã bị loại bỏ vì thực tế node cuối cùng là giá trị lớn nhất trong dãy số.

    Cây mới được hình thành (không kể phần tử loại bỏ) không phải là một heap, chúng ta lại thực hiện vun thành đống và thực hiện tương tự như trên cho tới khi đống còn một phần tử là phần tử bé nhất của dãy.

    Độ phức tạp của Heap Sort là : Cmã = Cmin = O(n logn) cơ số hai.

    Giải thuật được cài đặt như sau:
    C Code:
    1. #include    <conio.h>
    2. #include    <stdlib.h>
    3. #include    <alloc.h>
    4. #include    <dos.h>
    5. void Heap(int *, int );
    6. void Init(int *, int);
    7. void In(int *, int);
    8. void Init(int *A, int n){
    9.     int i;
    10.     printf("\n Tao lap day so:");
    11.     for (i=0; i<n;i++){
    12.         A[i]=random(1000);
    13.         printf("%5d",A[i]);
    14.     }
    15.     delay(1000);
    16. }
    17. void Heap(int *A, int n) {
    18.     int k,x,s,f,ivalue;
    19.     for(k=1;k<n;k++){
    20.         x=A[k];
    21.         s=k; f=(s-1)/2;
    22.         while(s>0 && A[f]<x){
    23.             A[s]=A[f];
    24.             s=f; f=(s-1)/2;
    25.         }
    26.         A[s]=x;
    27.     }
    28.     for(k=n-1;k>0;k--){
    29.         ivalue=A[k];
    30.         A[k]=A[0];
    31.         f=0;
    32.         if(k==1)
    33.             s=-1;
    34.         else
    35.             s=1;
    36.         if(k>2 && A[2]>A[1])
    37.             s=2;
    38.         while(s>=0 && ivalue<A[s]){
    39.             A[f]=A[s];
    40.             f=s;s=2*f +1;
    41.             if (s+1<=k-1 && A[s]<A[s+1])
    42.                 s=s+1;
    43.             if (s>k-1)
    44.                 s=-1;
    45.         }
    46.         A[f]=ivalue;
    47.     }
    48. }
    49.  
    50. void In(int *A, int n){
    51.     register int i;
    52.     for(i=0;i<n;i++)
    53.         printf("%5d",A[i]);
    54.     delay(1000);
    55. }
    56. void main(void){
    57.     int *A,n;clrscr();
    58.     printf("\n Nhap n="); scanf("%d",&n);
    59.     A=(int *) malloc(n*sizeof(int));
    60.     Init(A,n);Heap(A,n);printf("\n");
    61.     In(A,n);getch();
    62.     free(A);
    63. }

  9. #9
    Ngày gia nhập
    10 2006
    Nơi ở
    Hà Nội
    Bài viết
    146

    Talking Giải thuật Merge Sort

    VIII - Giải thuật Merge Sort

    Sắp xếp theo Merge sort là sắp xếp bằng cách trộn hai danh sách đã được sắp xếp thành một danh sách đã được sắp xếp. Phương pháp này được tiến hành thông qua các bước sau:
    1- Coi danh sách cần sắp xếp (có n phần tử) là n danh sách con mỗi danh sách con gồm 1 phần tử , như vậy các danh sách con đã được sắp xếp. Trộn từng cặp hai danh sách con kế cận thành một danh sách có hai phần tử ta nhận được n/2 danh sách con đã được sắp xếp.
    2- Xem danh sách cần sắp xếp như n/2 danh sách con đã được sắp xếp. Trộn từng cặp hai danh sách kế cận thành từng danh sách có 4 phần tử đã được sắp xếp ta nhận được n/4 danh sách con.
    3- …
    ……
    i- Làm tương tự như bước i-1. Quá trình tiếp tục khi ta nhận được danh sách có n phần tử đã được sắp xếp.
    Ví dụ :
    Sample Code:
    1.         42  23  74  11  68  58  94  36
    2. Lần 1: [23    42] [11 74] [58 68] [36 94]
    3. Lần 2: [11    23  42  74] [36 58  68  94]
    4. Lần 3: [11    23  36  42  58  68  74  94]
    Nhận được dãy đã sắp xếp.

    Chương trình cài đặt thuật toán như sau:
    C Code:
    1. #include    <stdio.h>
    2. #include    <conio.h>
    3. #include    <stdlib.h>
    4. #include    <alloc.h>
    5. #include    <dos.h>
    6. #define     MAX 10
    7. void Merge(int *, int );
    8. void Init(int *, int);
    9. void In(int *, int);
    10. void Init(int *A, int n){
    11.     int i;
    12.     printf("\n Tao lap day so:");
    13.     for (i=0; i<n;i++){
    14.         A[i]=random(1000);
    15.         printf("%5d",A[i]);
    16.     }
    17.     delay(1000);
    18. }
    19. void Merge(int *A, int n) {
    20.     int i,j,k,low1,up1,low2,up2,size;
    21.     int *dstam;size=1;dstam=(int *) malloc(n*sizeof(int));
    22.     while(size<n){
    23.         low1=0;k=0;
    24.         while(low1 +size <n){
    25.             low2=low1+size; up1=low2-1;
    26.             if (low2+size-1< n)
    27.                 up2=low2+size-1;
    28.             else
    29.                 up2=n-1;
    30.             for(i=low1, j=low2; i<=up1 && j<=up2; k++){
    31.                 if(A[i]<=A[j])
    32.                     dstam[k]=A[i++];
    33.                 else
    34.                     dstam[k] =A[j++];
    35.             }
    36.             for(;i<=up1;k++)
    37.                 dstam[k]=A[i++];
    38.             for(;j<=up2;k++)
    39.                 dstam[k]=A[j++];
    40.             low1=up2+1;
    41.         }
    42.         for (i=low1; k<n;i++)
    43.             dstam[k++]=A[i];
    44.         for(i=0;i<n;i++)
    45.             A[i]=dstam[i];
    46.         size*=2;
    47.     }
    48.     printf("\n Ket qua:");
    49.     In(A,n);free(dstam);
    50. }
    51. void In(int *A, int n){
    52.     register int i;
    53.     for(i=0;i<n;i++)
    54.         printf("%5d",A[i]);
    55.     delay(1000);
    56. }
    57. void main(void){
    58.     int *A,n;clrscr();
    59.     printf("\n Nhap n="); scanf("%d",&n);
    60.     A=(int *) malloc(n*sizeof(int));
    61.     Init(A,n);Merge(A,n);printf("\n");
    62.     free(A);
    63. }

    Ngoài ra còn có một số thuật toán Sắp xếp cải tiến, tuy nhiên trên đây là các thuật toán sắp xếp nổi tiếng và tiêu biểu.

    Các bạn có thể tự mình nằm suy ngẫm ra 1 thuật toán sắp xếp cho riêng mình chăng? Hãy cố lên.
    Từ hôm sau chúng ta sẽ tiếp xúc với các thuật toán tìm kiếm.

  10. #10
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Mặc định Bucket Sort

    Bucket Sort :
    A bucket sort begins with a single-subcripted array of positive integers to be sorted and double subscripted array of integers with rows subscripted from 0 to 9 and colunm subscripted from 0 to n-1, where n í the number of values in the array to be sorted. Each row of the double subscripted array is referred to as a bucket. Description :
    -Place each value of the single subscripted array into a row of the bucket array based on the value's ones digit. For example 97 is placed in row 7, 3 is placed in row 3, and 100 is placed in row 0. This is called "distribution pass".
    -Loop through the bucket array row by row, and copy the values back to the orginal array. This is called a " gathering pass". The new order of the preceding values in the single subscripted array is 100, 3 and 97.
    -Repeat this process for each subsequent digit position ( tens, hundreds, thousands...etc )
    -On the second pass, 100 is placed in row 0, 3 is placed ỉn row 0 ( because 3 has no ten digit ) and 97 is placed in row 9. After the gathering pass, the order of the values in the single subscripted array is 100, 3 and 97. On the third pass, 100 is placed in row 1, 3 is placed in row zero and 97 is placed in row zero ( after the 3 ). After the last gathering pass, the orginal array is now in sorted order.
    Note that : the double subscripted array of bucket is 10 times the size of the size of the integer array being sorted. This sorting technique provides better performance than a bubble sort, but requires much more memory. The bubble sort require space for only one additional element of data. This is an example of space-time trade off: The bucket sort uses more memory than the bubble sort, but performs better. This version of bucket sort requires copying all the data back to the original array on each pass. Another accessibility is to create a second double subscripted bucket array and repeatedly swap the data between the two bucket arrays.
    Code Details


    #solution 1
    C++ Code:
    1. #include<iostream>
    2. #include<conio.h>
    3. #include<iomanip>
    4. #include<cmath>
    5. /* Bucket Sort */
    6. #include<iostream>
    7. #include<iomanip>
    8. #include<cmath>
    9. /* Bucket Sort */
    10. using std::cout;
    11. using std::cin;
    12. using std::endl;
    13. using std::setw;
    14.  
    15. const int size = 10;                                              
    16. int max_digit;
    17. int Bucket[size],
    18.     Bucket_Temp[size],
    19.     Double[10][size],
    20.     Double_Temp[10][size],
    21.     Number_Digit[size] ,Store[size];  
    22. int main()
    23. {
    24.     int Bucket[size] = { 97,121,20,3,55,12,44,1,5,9 };
    25.     for ( int i = 0; i < size; i++ )
    26.         for ( int j = 0; j < size; j++ )
    27.             Double[i][j] = -1;
    28.     for ( int i = 0; i < size; i++ )
    29.         Store[i] = -1;
    30.     for ( int i = 0; i < size; i++ )
    31.         Bucket_Temp[i] = Bucket[i];
    32.     max_digit = 0;
    33.     for ( int i = 0; i < size; i++ )
    34.     {
    35.         int num_digit = (log(Bucket[i])/log(10)) + 1;
    36.         if (num_digit > max_digit)
    37.             max_digit = num_digit;
    38.     }
    39.     cout << " MAX DIGIT OF THE NUMBER OF ELEMENT IN ARRAY IS: " << max_digit << endl;              
    40.      
    41.     for ( int c = 0; c < max_digit; c++ )
    42.     {
    43.         for ( int i = 0; i < size; i++ )
    44.             for ( int j = 0; j < size; j++ )
    45.                 Double[i][j] = -1;
    46.         for (  int i = 0; i < size; i++ )
    47.             Store[i] = -1;
    48.  
    49.         cout << "B-E-F-O-R-E"<< endl;
    50.         for ( int i = 0; i < size; i++)
    51.             cout << setw(5) << Bucket[i];
    52.         cout << endl;
    53.  
    54.         for ( int j = 0; j < size; j++ )
    55.         {    
    56.             int position = 0;
    57.             int digit = Bucket_Temp[j]%10;
    58.             Store[j] = digit;
    59.             for ( int a = j; a >= 0; a-- )
    60.                 if ( Store[a] == Store[j] )
    61.                     position++;
    62.             Double[digit][position] = Bucket[j];
    63.             Double_Temp[digit][position] = Bucket_Temp[j];
    64.         }
    65.                
    66.         for ( int i = 0; i < size; i++ )
    67.         {      
    68.             for ( int j = 0; j < size; j++ )
    69.                 cout << Double[i][j] << setw(4);
    70.             cout << "\n\n";
    71.         }
    72.  
    73.                
    74.         int index = 0;
    75.         for ( int i = 0; i < size; i++ )
    76.         {
    77.             for ( int j = 0; j < size; j++ )
    78.             {
    79.                 if ( Double[i][j] != -1 )
    80.                 {                                                      
    81.                     Bucket_Temp[index] = Double_Temp[i][j]/10;
    82.                     Bucket[index] = Double[i][j];
    83.                     index++;
    84.                                                      
    85.                 }
    86.             }
    87.         }
    88.                            
    89.                        
    90.         cout << "A-F-T-E-R" << endl;
    91.         for ( int i = 0; i < size; i++)
    92.         {
    93.             cout << setw(5) << Bucket[i];
    94.         }
    95.         cout << "\n\n";
    96.         cout << "*><*><*><*>TRANSFORMING-SUPERXAYDA<*><*><*><*" << "\n\n";
    97.     }
    98.     cout << "T-H-E---F-I-N-A-L---A-R-R-A-Y" << endl;
    99.     cout << endl;
    100.     for ( int i = 0; i < size; i++ )
    101.     {
    102.           cout <<  Bucket[i] << setw(5) ;
    103.     }
    104.     cout << endl;
    105.     return 0;
    106. }

    #solution 2
    C++ Code:
    1. #include <iostream>
    2. #include <iomanip>
    3. #include <cmath>
    4. #include <conio.h>
    5. using namespace std;
    6. const int size = 10;
    7. int Bucket[size], Double[10][size], Save[size], row_pos[10];
    8. int max_digit;
    9.  
    10. void main()
    11. {
    12.     int Bucket[size] = { 97,121,20,3,55,28,44,1,5,9 };
    13.     int temp[size], temp2[10][size];
    14.    
    15.     for ( int i = 0; i < size; i++)
    16.                 temp[i] = Bucket[i];
    17.     /* the maximum digit of all the elements in the array */
    18.         max_digit = 0;
    19.     for ( int i = 0; i < size; i++ )
    20.     {
    21.         int num_digit = (log(temp[i])/log(10)) + 1;
    22.        
    23.         if (num_digit > max_digit)
    24.                         max_digit = num_digit;
    25.         }
    26.  
    27.                 cout << "Max_digit is " << max_digit << endl;
    28.                 cout << "The array befor sorted: " << endl ;           
    29.                 for ( int i = 0; i < size; i++ ) cout << Bucket[i] << setw(3) ;
    30.    
    31.         for ( int c = 0; c < max_digit; c++ )
    32.         {
    33.                         for ( int i = 0; i < 10; i++)
    34.                                 row_pos[i] = -1;
    35.            
    36.  
    37.             for ( int j = 0; j < size; j++ )
    38.             {  
    39.                                 int digit = temp[j]%10;
    40.                 int position = ++row_pos[digit];
    41.                 temp[j] = temp[j] / 10;
    42.                                 Double[digit][position] = Bucket[j];
    43.                 temp2[digit][position] = temp[j];
    44.  
    45.             }
    46.                        
    47.             int index = 0;
    48.             for ( int i = 0; i < 10; i++ )
    49.             {
    50.                               cout << "===========================" << endl;
    51.                 if (row_pos[i] >= 0)
    52.                 {
    53.                     for ( int j = 0; j <= row_pos[i]; j++ )
    54.                     {
    55.                         cout << "index = " << index << endl;
    56.                         Bucket[index] = Double[i][j];
    57.                         temp[index] = temp2[i][j];
    58.                         index++;
    59.                     }
    60.                 }
    61.             }
    62.                      
    63.                         for ( int i = 0; i < size; i++ )
    64.                         {        
    65.                                 for ( int j = 0; j < size; j++ )
    66.                                         cout << setw(3) << Double[i][j] << setw(4) ;
    67.                                 cout << "\n\n" ;
    68.                         }                      
    69.                        
    70.         }
    71.         cout << " The array after sorted: " << endl ;          
    72.     for ( int i = 0; i < size; i++ ) cout << Bucket[i] << setw(5) ;
    73.    
    74.        
    75. cin.get();
    76. }
    Đã được chỉnh sửa lần cuối bởi rox_rook : 16-02-2008 lúc 10:23 AM.

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

  1. Các giải thuật tìm kiếm - Lý thuyết và cài đặt trên C
    Gửi bởi PoPoPoPo trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 5
    Bài viết cuối: 24-02-2015, 05:21 PM
  2. Lý thuyết C++ | Giải thuật đồ thị cài đặt bằng C++
    Gửi bởi rox_rook trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 31
    Bài viết cuối: 30-01-2015, 10:41 PM
  3. Lý thuyết đồ thị | Giải thuật DFS (Depth First Search)
    Gửi bởi vie_kainznz trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 1
    Bài viết cuối: 14-01-2013, 10:48 PM
  4. [Lý thuyết giải thuật] Một số bài tập về giải thuật và cách giải
    Gửi bởi hailoc12 trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 6
    Bài viết cuối: 27-01-2010, 04:10 PM
  5. Lý thuết đồ thị | Bài tập Lý thuyết đồ thị
    Gửi bởi soda_chanhmuoi 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: 11-02-2008, 08:01 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