Từ 1 tới 6 trên tổng số 6 kết quả

Đề tài: Code một số thuật toán sắp xếp

  1. #1
    Ngày gia nhập
    04 2011
    Bài viết
    9

    Mặc định Code một số thuật toán sắp xếp

    40% thời gian hoạt động của máy tính là sắp xếp --> Ngồi loay hoay tìm hiểu post lên diễn đàn cho vui

    Insertion sort
    Selection sort
    Bubble sort
    Shaker sort
    Shell sort
    Merge sort
    Heap sort
    Quick sort
    Couting sort
    Radix sort

    C Code:
    1. #include<stdio.h>
    2. #include<malloc.h>
    3. #include<conio.h>
    4.  
    5. int *a,n,i;
    6. //function
    7. void input();
    8. void output(int a[], int n);
    9.  
    10. void insertion_sort(int a[], int n);
    11.  
    12. void swap(int &a, int &b);
    13.  
    14. void selection_sort(int a[], int n);
    15.  
    16. void bubble_sort(int a[], int n);
    17.  
    18. void shaker_sort(int a[], int n);
    19.  
    20. void merge(int a[], int left, int right);
    21. void merge_sort(int a, int left, int right);
    22.  
    23. void shift(int a[], int left, int right);
    24. void create_heap(int a[], int n);
    25. void heap_sort(int a[], int n);
    26.  
    27. void quick_sort(int a[], int left, int right);
    28.  
    29. void couting_sort(int a[], int n);
    30.  
    31. void cout_sort(int a[], int n, int exp);
    32. void radix_sort(int a[], int n);
    33. void menu();
    34. int main()
    35. {
    36.     menu();
    37.     return 0;
    38. }
    39. void input()
    40. {
    41.     printf("Nhap so phan tu n= ");
    42.     scanf("%d",&n);
    43.     a=(int*)malloc(sizeof(int)*n);
    44.     for(i=0;i<n;i++)
    45.     {
    46.         printf("a[%d]= ",i);
    47.         scanf("%d",a+i);
    48.     }  
    49. }
    50. void output(int a[], int n)
    51. {
    52.     int i;
    53.     for(i=0;i<n;i++)
    54.         printf("%d\t",a[i]);
    55.     printf("\n");
    56. }
    57. void insertion_sort(int a[], int n)
    58. {
    59.     int i,j,x;
    60.     for(i=1;i<n;i++)
    61.     {
    62.         x=a[i];
    63.         j=i-1;
    64.         while(j>=0 && a[j]>x)
    65.         {
    66.             a[j+1]=a[j];
    67.             j=j-1;
    68.         }
    69.         a[j+1]=x;  
    70.     }
    71. }
    72. void swap(int &a, int &b)
    73. {
    74.     int c;
    75.     c=a;
    76.     a=b;
    77.     b=c;
    78. }
    79. void selection_sort(int a[], int n)
    80. {
    81.     int i,j;
    82.     int min;
    83.     for(i=0;i<n-1;i++)
    84.     {
    85.         min=i;
    86.         for(j=i+1;j<n;j++)
    87.             if(a[min]> a[j])
    88.                 min=j;
    89.         swap(a[i],a[min]);
    90.     }
    91. }
    92. void bubble_sort(int a[], int n)
    93. {
    94.     int i,j;
    95.     j=n-1;
    96.     while(j>=0)
    97.     {
    98.         for(i=0;i<j;i++)
    99.             if(a[i]>a[j])
    100.                 swap(a[i],a[j]);
    101.         j--;
    102.     }
    103. }
    104. void shaker_sort(int a[], int n)
    105. {
    106.     int l=0;
    107.     int r=n-1;
    108.     int k; // ghi nhan vi tri xay ra hoan vi
    109.     while(l!=r && l-1!=r)
    110.     {
    111.         k=l;
    112.         while(k<r)
    113.         {
    114.             if(a[k]>a[r])
    115.                 swap(a[k],a[r]);
    116.             k=k+1;
    117.         }
    118.         r=r-1;
    119.         k=r;
    120.         while(k>l)
    121.         {
    122.             if(a[k]<a[l])
    123.                 swap(a[k],a[l]);
    124.             k=k-1;
    125.         }
    126.         l=l+1;
    127.     }
    128. }
    129. void shell_sort(int a[], int n) // cai tien cua thuat toan insertion sort
    130. {
    131.     int temp,i,j,k;
    132.     for(k=n/2; k>0; k/=2)
    133.     {
    134.         for(i=0;i<n;i+=k)
    135.         {
    136.             temp=a[i];
    137.             for(j=i; j>0 && a[j-k]>temp; j-=k)
    138.                 a[j]=a[j-k];
    139.             a[j]=temp;
    140.         }
    141.     }
    142. }
    143. void merge(int a[], int left, int right) // tron 2 mang da duoc sap xep
    144. {
    145.     int i,j,temp,k,mid;
    146.     mid=(left+right)/2;
    147.     i=left;
    148.     j=mid+1;
    149.     while(i<=j && j<=right)
    150.     {
    151.         if(a[i]>a[j])
    152.         {
    153.             temp=a[j];
    154.             for(k=j;k>i;k--)
    155.                 a[k]=a[k-1];
    156.             a[i]=temp;
    157.             j++;
    158.         }
    159.         i++;
    160.     }
    161. }
    162. void merge_sort(int a[], int left, int right)
    163. {
    164.     int mid;
    165.     if(left>=right)
    166.         return;
    167.     mid=(left+right)/2;
    168.     merge_sort(a,left,mid);
    169.     merge_sort(a,mid+1,right);
    170.     merge(a,left,right);
    171. }
    172. void shift(int a[], int left, int right)
    173. {
    174.     int i,j,x;
    175.     i=left;
    176.     j=2*i+1;
    177.     x=a[i];
    178.     while(j<=right)
    179.     {
    180.         if(a[j]<a[j+1] && j<right)
    181.             j++;
    182.         if(a[j]<=x)
    183.             break;
    184.         else
    185.         {
    186.             swap(a[i],a[j]);
    187.             i=j;
    188.             j=2*i+1;
    189.         }
    190.     }
    191. }
    192. void create_heap(int a[], int n)
    193. {
    194.     int left;
    195.     left=(n-1)/2;
    196.     while(left>=0)
    197.     {
    198.         shift(a,left,n-1);
    199.         left--;
    200.     }
    201. }
    202. void heap_sort(int a[], int n)
    203. {
    204.     int right=n-1;
    205.     create_heap(a,n);
    206.     while(right>0)
    207.     {
    208.         swap(a[0],a[right]);
    209.         right--;
    210.         shift(a,0,right);
    211.     }
    212. }
    213.  
    214. void quick_sort(int a[], int left, int right)
    215. {
    216.     int i,j,x;
    217.     if(left>= right)
    218.         return ;
    219.     else
    220.     {
    221.         x=(left+right)/2;
    222.         i=left;
    223.         j=right;
    224.         while(i<j)
    225.         {
    226.             while(a[i]<a[x])
    227.                 i++;
    228.             while(a[j]>a[x])
    229.                 j--;
    230.             if(i<=j)
    231.             {
    232.                 swap(a[i],a[j]);
    233.                 i++;
    234.                 j--;
    235.             }
    236.         }      
    237.     }
    238.     quick_sort(a,left,j);
    239.     quick_sort(a,i,right);
    240. }
    241. void couting_sort(int a[], int n)
    242. {
    243.     int i,j;
    244.     int max=a[0];
    245.     int b[n],c[100];
    246.     for(i=1;i<n;i++)
    247.     {
    248.         if(max<a[i])
    249.             max=a[i];
    250.     }
    251.     for(i=0;i<=max;i++)
    252.         c[i]=0;
    253.     for(j=0;j<n;j++)
    254.         c[a[j]]++;
    255.     for(i=1;i<=max;i++)
    256.         c[i]+=c[i-1];
    257.     for(j=0;j<n;j++)
    258.     {
    259.         b[c[a[j]]-1]=a[j];
    260.         c[a[j]]--;
    261.     }
    262.        
    263.     for(j=0;j<n;j++)
    264.         a[j]=b[j];
    265. }
    266. void cout_sort(int a[], int n, int exp)
    267. {
    268.     int b[n];
    269.     int c[10];
    270.     int i;
    271.     for(i=0;i<10;i++)
    272.         c[i]=0;
    273.     for(i=0;i<n;i++)
    274.         c[(a[i]/exp)%10]++;
    275.     for(i=1;i<10;i++)
    276.         c[i]+=c[i-1];
    277.     for(i=n-1;i>=0;i--)
    278.         b[c[(a[i]/exp)%10]-- -1]=a[i];
    279.     for(i=0;i<n;i++)
    280.         a[i]=b[i];
    281. }
    282. void radix_sort(int a[], int n)
    283. {
    284.     int i,exp,max=a[0];
    285.     for(i=1;i<n;i++)
    286.         if(a[i]> max)
    287.             max=a[i];
    288.    
    289.     for(exp=1; max/exp>0 ; exp*=10)
    290.         cout_sort(a,n,exp);
    291. }
    292. void menu()
    293. {
    294.     int k;
    295.     tt:
    296.     system("cls");
    297.     printf("---------------MENU---------------\n");
    298.     printf("1. Input\n");
    299.     printf("2. Output\n");
    300.     printf("3. Insertion sort\n");
    301.     printf("4. Selection sort\n");
    302.     printf("5. Bubble sort\n");
    303.     printf("6. Shaker sort\n");
    304.     printf("7. Shell sort\n");
    305.     printf("8. Merge sort\n");
    306.     printf("9. Heap sort\n");
    307.     printf("10. Quick sort\n");
    308.     printf("11. Couting sort\n");
    309.     printf("12. Radix sort\n");
    310.     printf("0. Exit\n");
    311.     printf("\nEnter choice: ");
    312.     scanf("%d",&k);
    313.     switch(k)
    314.     {
    315.         case 1:
    316.             input();
    317.             getch();
    318.             goto tt;
    319.         case 2:
    320.             output(a,n);
    321.             getch();
    322.             goto tt;
    323.         case 3:
    324.             insertion_sort(a,n);
    325.             printf("Ban da sap xep thanh cong\n");
    326.             getch();
    327.             goto tt;
    328.         case 4:
    329.             selection_sort(a,n);
    330.             printf("Ban da sap xep thanh cong\n");
    331.             getch();
    332.             goto tt;
    333.         case 5:
    334.             bubble_sort(a,n);
    335.             printf("Ban da sap xep thanh cong\n");
    336.             getch();
    337.             goto tt;       
    338.         case 6:
    339.             shaker_sort(a,n);
    340.             printf("Ban da sap xep thanh cong\n");
    341.             getch();
    342.             goto tt;       
    343.         case 7:
    344.             shell_sort(a,n);
    345.             printf("Ban da sap xep thanh cong\n");
    346.             getch();
    347.             goto tt;       
    348.         case 8:
    349.             merge_sort(a,0,n-1);
    350.             printf("Ban da sap xep thanh cong\n");
    351.             getch();
    352.             goto tt;       
    353.         case 9:
    354.             heap_sort(a,n);
    355.             printf("Ban da sap xep thanh cong\n");
    356.             getch();
    357.             goto tt;       
    358.         case 10:
    359.             quick_sort(a,0,n-1);
    360.             printf("Ban da sap xep thanh cong\n");
    361.             getch();
    362.             goto tt;       
    363.         case 11:
    364.             couting_sort(a,n);
    365.             printf("Ban da sap xep thanh cong\n");
    366.             getch();
    367.             goto tt;       
    368.         case 12:
    369.             radix_sort(a,n);
    370.             printf("Ban da sap xep thanh cong\n");
    371.             getch();
    372.             goto tt;       
    373.         case 0:
    374.             break;
    375.         default:
    376.             printf("Ban chon ngu vl. Chon lai\n");
    377.             getch();
    378.             goto tt;
    379.     }
    380. }

  2. #2
    Ngày gia nhập
    01 2013
    Bài viết
    1,479

    Bubble có bản cải tiến mà bạn

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

    Trích dẫn Nguyên bản được gửi bởi prog10 Xem bài viết
    Bubble có bản cải tiến mà bạn
    Cải tiến của bubble sort là shaker sort mà

  4. #4
    Ngày gia nhập
    01 2013
    Bài viết
    1,479

    Trích dẫn Nguyên bản được gửi bởi hiepgv37 Xem bài viết
    Cải tiến của bubble sort là shaker sort mà
    Cải tiến là: Khi "bọt" đã nổi thì ko cần phải xét đến nữa
    Tức là trong mỗi lần duyệt, chỉ cần duyệt đến phần tử bị swap cuối cùng ở lần trước.

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

    Trích dẫn Nguyên bản được gửi bởi prog10 Xem bài viết
    Cải tiến là: Khi "bọt" đã nổi thì ko cần phải xét đến nữa
    Tức là trong mỗi lần duyệt, chỉ cần duyệt đến phần tử bị swap cuối cùng ở lần trước.
    bạn nói mình không hiểu

  6. #6
    Ngày gia nhập
    01 2013
    Bài viết
    1,479

    Mặc định Code một số thuật toán sắp xếp

    Trích dẫn Nguyên bản được gửi bởi hiepgv37 Xem bài viết
    bạn nói mình không hiểu
    http://en.wikipedia.org/wiki/Bubble_...ng_bubble_sort

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

  1. Bài tập C++ code thuật toán clipping và mô tả thuật toán
    Gửi bởi binhc trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 0
    Bài viết cuối: 05-06-2013, 07:56 PM
  2. Cần tìm người code C# lương thỏa thuận
    Gửi bởi zaroyahoo trong diễn đàn Việc làm IT(tự do)
    Trả lời: 0
    Bài viết cuối: 24-05-2013, 04:00 PM
  3. code tìm cây có trọng lượng nhỏ nhất bằng giải thuật prim-cách chạy tay code này
    Gửi bởi ruacon_206 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: 25-04-2011, 02:27 PM
  4. Cần source code thuật toán Apriori và thuật toán Eclat !
    Gửi bởi ronaldo1984 trong diễn đàn Thắc mắc lập trình Visual C++
    Trả lời: 0
    Bài viết cuối: 27-07-2010, 09:25 AM
  5. [HELP]Thuật toán và code tô màu đa giác
    Gửi bởi minhquan8338 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: 13-10-2008, 05:03 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