Trang 2 trên tổng số 3 Đầu tiênĐầu tiên 123 Cuối cùngCuối cùng
Từ 11 tới 20 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. #11
    Ngày gia nhập
    03 2007
    Nơi ở
    Nhà hát của những giấc mơ
    Bài viết
    33

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

    for ( walk = current + 1 ; walk <= last ; walk++ ) // sort
    if ( list[walk] < list[smallest] ) smallest = walk; //exhange if it is suitable

    temp = list[current];
    list[current] = list[smallest];
    list[smallest] = temp;

    Ở đoạn này các bác thêm {} cho đúng chỗ giùm em cái đi

    Làm cho thấy rõ cấu trúc của if và for nhé

    Thank các bác

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

    Mặc định sắp xếp, đọc file, lưu file, tính thời gian

    sắp xếp, đọc file, lưu file, tính thời gian, có hết đó.nhớ tạo lại file data và thay lại đường link của các file nha!

    C++ Code:
    1. #include<iostream.h>
    2. #include<conio.h>
    3. #include<fstream.h>
    4. #include<stdlib.h>
    5. #include<ctype.h>
    6. #include<time.h>
    7. clock_t  start, end;
    8. double t;
    9. long  *abc;
    10. long  n,i;
    11. void xuat(long  a[])
    12. {
    13.     for(long  i=0;i<n;i++)
    14.          cout<<a[i]<<"  ";
    15.     cout<<endl;
    16.    
    17. }
    18. //////////////////////////////////////////////////////////////////////////////////////////////////////
    19. void bubbleSort(long a[],long n)
    20. {
    21.     long  temp;
    22.     for(long  i=0;i<n;i++)
    23.            for(long  j=n-1;j>i;j--)
    24.               if(a[j]<a[j-1])
    25.             {
    26.                  temp=a[j];
    27.                 a[j]=a[j-1];
    28.                 a[j-1]=temp;
    29.             }
    30. }
    31. //////////////////////////////////////////////////////////////////////////////////////////////////////
    32. void chonTrucTiep( long a[], long n)
    33. {
    34.     long  possMin;
    35.     long  temp;
    36.     for(long  i=0;i<n-1;i++)
    37.     {
    38.         possMin=i;
    39.         for(long  j=i+1;j<n;j++)
    40.             if(a[j]<a[possMin])
    41.                 possMin=j;
    42.             temp=a[i];
    43.             a[i]=a[possMin];
    44.             a[possMin]=temp;
    45.    
    46.     }
    47. }
    48. ////////////////////////////////////////////////////////////////////////////////////////////////////
    49. void chenTrucTiep(long  a[],long  n)
    50. {
    51.     long j;
    52.     long x;
    53.     for(long i=1;i<n;i++)
    54.     {
    55.         x=a[i];
    56.         j=i-1;
    57.         while(a[j]>x && j>=0)
    58.         {
    59.             a[j+1]=a[j];
    60.             j--;
    61.         }
    62.         a[j+1]=x;
    63.     }
    64. }
    65. //////////////////////////////////////////////////////////////////////////////////////////////////
    66. void chenNP(long a[],long n)
    67. {
    68.     long x;
    69.     for(long i=1;i<n;i++)
    70.     {
    71.         long l=0,r=i-1;long j=i-1;
    72.         x=a[i];
    73.         while(l<=r)                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            
    74.         {
    75.             long m=(l+r)/2;
    76.             if(a[m]>x)
    77.                    r=m-1;
    78.             else   l=m+1;
    79.         }
    80.         for( j=i-1;j>l;j--)
    81.         a[j+1]=a[j];
    82.         a[l]=x;
    83.     }
    84. }
    85. ///////////////////////////////////////////////////////////////////////////////////////////////////
    86. void tronHaiNua(long a[],long l1,long r1,long l2,long r2)
    87. {
    88.     for(long i=l2;i<r2;i++)
    89.     {
    90.         long  x=a[i];
    91.         long j=r1;
    92.         while(a[j]>x && j>=l1)
    93.         {
    94.             a[j+1]=a[j];
    95.             j--;
    96.         }
    97.         a[j+1]=x;
    98.         r1++;
    99.     }
    100. }
    101. void tronTuNhien(long a[],long l, long r)
    102. {
    103.     if(l<r)
    104.     {
    105.         tronTuNhien(a,l,(l+r)/2);
    106.         tronTuNhien(a,(l+r)/2+1,r);
    107.         tronHaiNua(a,l,(l+r)/2,(l+r)/2+1,r);
    108.     }
    109. }
    110. //////////////////////////////////////////////////////////////////////////////////////////////////
    111. void quickSort(long a[],long l,long r)
    112. {
    113.     long  x,temp;
    114.     long  i,j;
    115.     x=a[(l+r)/2];
    116.     i=l;j=r;
    117.     do
    118.     {    while(a[i]<x) i++;
    119.         while(a[j]>x) j--;
    120.         if(i<=j)
    121.         {    temp=a[i];
    122.             a[i]=a[j];
    123.             a[j]=temp;i++;j--;
    124.         }
    125.     }while(i<=j);
    126.     if(j>l)
    127.         quickSort(a,l,j);
    128.     if(i<r)
    129.         quickSort(a,i,r);
    130. }
    131. //////////////////////////////////////////////////////////////////////////////////////////////////
    132. void chenTrucTiepLC( long a[], long n)
    133. {
    134.     long j;
    135.     long x;
    136.     for(long i=1;i<n;i++)
    137.     {
    138.         x=a[i];
    139.         j=i-1;
    140.         while(a[j]>x )
    141.         {
    142.             a[-1]=x;
    143.             a[j+1]=a[j];
    144.             j--;
    145.         }
    146.         a[j+1]=x;
    147.     }
    148. }
    149. //////////////////////////////////////////////////////////////////////////////////////////////////
    150. void hieuChinhHM(long a[],long l,long r)
    151. {
    152.     long i,j,x;
    153.     i=l;j=2*i;x=a[i];
    154.     while (j<=r)
    155.     {
    156.         if(j<r)
    157.             if (a[j]<=a[j+1])
    158.                 j++;
    159.         if(a[j]<=x)
    160.             break;
    161.         a[i]=a[j];
    162.         i=j;
    163.         j=2*i;
    164.     }
    165.     a[i]=x;
    166. }
    167. ////////////////////////////
    168. void taoHeapMax(long a[],long n)
    169. {
    170.     long l,r;
    171.     l=n/2+1;r=n-1;
    172.     while(l>0)
    173.     {
    174.         l--;
    175.         hieuChinhHM(a,l,r);
    176.     }
    177. }
    178. ////////////////////////////
    179. void heapSort(long a[], long n)
    180. {
    181.     long tam;long r;r=n-1;
    182.     taoHeapMax(a,n);
    183.     while(r>0)
    184.     {
    185.         tam=a[0];
    186.         a[0]=a[r];
    187.         a[r]=tam;
    188.         r--;
    189.         hieuChinhHM(a,0,r);
    190.     }
    191. }
    192. //////////////////////////////////////////////////////////////////////////////////////////////////
    193. /*void heapSort(long a[],long n)
    194. {
    195.     long x,s,f,endHeap;
    196.     for(i=0;i<n;i++)
    197.     {
    198.         x=a[i];
    199.         s=i;
    200.         f=(s-1)/2;
    201.         while(s>0 && a[f]<x)
    202.         {
    203.             a[s]=a[f];
    204.             s=f;
    205.             f=(s-1)/2;
    206.         }
    207.         a[s]=x;
    208.     }
    209.     for(i=n-1;i>0;i--)
    210.     {
    211.         endHeap=a[i];
    212.         a[i]=a[0];
    213.         f=0;
    214.         if(i==1)
    215.             s=-1;
    216.         else
    217.             s=1;
    218.         if(i>2 && a[2]>a[1])
    219.             s=2;
    220.         while(s>=0 && endHeap<a[s])
    221.         {
    222.             a[f]=a[s];
    223.             f=s;
    224.             s=2*f+1;
    225.             if(s+1<=i-1 && a[s]<a[s+1])
    226.                 s=s+1;
    227.             if(s>i-1)
    228.                 s=-1;
    229.         }
    230.         a[f]=endHeap;
    231.     }
    232. }
    233. */
    234. //////////////////////////////////////////////////////////////////////////////////////////////////
    235. void ghiTep(long a[],long n)
    236. {
    237.       ofstream f;
    238.     f.open("D:\\data11.txt",ios::out);
    239.     srand(time(0));
    240.     f<<"So luong:"<<n<<endl;
    241.     for(long i=0;i<n;i++)
    242.         f<<a[i]<<" ";
    243.     f<<endl;
    244.     f<<"thoi gian chay:"<<t<<endl;
    245.     f.close();
    246. }
    247. void docFile(long a[],long ab, char *tFile)
    248. {
    249.     int t;
    250.     ifstream f(tFile);
    251.     if (!f) cout << "Error!!" << endl;
    252.     f >> ab;
    253.     cout << "So phan tu:"<< ab<<endl;
    254.     abc=new long [ab];
    255.     n=ab;
    256.     if (!abc) cout << "Error!!" << endl;
    257.     for(long i=0;i<ab;i++)
    258.     {
    259.         f >> t;
    260.         abc[i]=t;
    261.     }  
    262.     cout << endl;
    263.     f.close();
    264. }
    265. //////////////////////////////////////////////////////////////////////////////////////////////
    266. void main()
    267. {
    268.     char *tFile;int d;char c;
    269.     int k=-1;
    270.     int sel=-1;
    271.     cout<<"Chon tu 1 den 5:";
    272.     cin>>k;
    273.     switch(k)
    274.     {
    275.         case 1:tFile="C:\\Documents and Settings\\Thuy Trang\\My Documents\\data1.txt"; break;
    276.         case 2:tFile="C:\\Documents and Settings\\Thuy Trang\\My Documents\\data2.txt"; break;
    277.         case 3:tFile="C:\\Documents and Settings\\Thuy Trang\\My Documents\\data3.txt"; break;
    278.         case 4:tFile="C:\\Documents and Settings\\Thuy Trang\\My Documents\\data4.txt"; break;
    279.         case 5:tFile="C:\\Documents and Settings\\Thuy Trang\\My Documents\\data5.txt"; break;
    280.     }
    281.     cout<<"file dc doc:"<<tFile<<endl;
    282.     docFile(abc,n,tFile);
    283.     cout<<"CHON 1 TRON CAC GIAI THUAT SAU:"<<endl;
    284.     cout<<"     1:Bubble sort"<<endl;
    285.     cout<<"     2:Chen nhi phan"<<endl;            
    286.     cout<<"     3:Chon truc tiep"<<endl;    
    287.     cout<<"     4:Chen truc tiep"<<endl;    
    288.     cout<<"     5:Tron tu nhien"<<endl;    
    289.     cout<<"     6:Chen truc tiep linh canh"<<endl;
    290.     cout<<"     7:Quick Sort"<<endl;    
    291.     cout<<"     8:Heap sort"<<endl;
    292.     cin>>sel;
    293.     start=clock();
    294.     switch(sel)
    295.     {
    296.         case 1:bubbleSort(abc,n);        break;
    297.         case 2:chenNP(abc,n);            break;
    298.         case 3:chonTrucTiep(abc,n);        break;
    299.         case 4:chenTrucTiep(abc,n);        break;
    300.         case 5:tronTuNhien(abc,0,n);    break;
    301.         case 6:chenTrucTiepLC(abc,n);    break;
    302.         case 7:quickSort(abc,0,n-1);    break;
    303.         case 8:heapSort(abc,n);            break;
    304.     }
    305.     end=clock();
    306.     t=double(end-start)/CLOCKS_PER_SEC ;
    307.     cout<<"Thoi gian chay:"<<t<<endl;
    308.     cout<<"Xuat day sau khi sap xep(c/k)?";
    309.     cin>>c;d=c;
    310.     if(d==67 || d==99)
    311.         xuat(abc);
    312.     ghiTep(abc,n);
    313.     cout<<"Ket thuc chuong trinh"<<endl;
    314.     getch();
    315. }
    316. //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

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

    code tạo file dữ liệu luôn nè!tiện thể bạn nào làm cái khử đệ quy cho quick sort bằng stack trên danh sách liên kết đơn thì chỉ mình với! ý tưởng giải thuật thôi cũng được

    C++ Code:
    1. #include<iostream.h>
    2. #include<stdlib.h>
    3. #include<fstream.h>
    4. #include<ctype.h>
    5. #include<time.h>
    6. #include<conio.h>
    7. long *a;
    8. long n;
    9.  
    10. void nhap(long &n)
    11. {  
    12.     cout<<"Nhap vao n:";cin>>n;
    13.     a=new long  [n];
    14.     srand(time(0));
    15.     for(long  i=0;i<n;i++)
    16.     {   a[i]=rand();    }
    17.     cout<<endl;
    18. }
    19. void xuat(long  a[])
    20. {
    21.     for(long  i=0;i<n;i++)
    22.          cout<<a[i]<<"  ";
    23.    
    24. }
    25. void ghiTep(long a[],long n)
    26. {
    27.     ofstream f;
    28.     f.open("D:\\data5.txt",ios::out);
    29.     srand(time(0));
    30.     f<<n<<endl;
    31.     for(long i=0;i<n;i++)
    32.         f<<a[i]<<" ";
    33.     f<<endl;
    34.     f.close();
    35. }
    36. void main()
    37. {
    38.     nhap(n);
    39.     xuat(a);
    40.     cout<<endl;
    41.     ghiTep(a,n);
    42.     getch();
    43. }

  4. #14
    Ngày gia nhập
    04 2007
    Nơi ở
    tphcm
    Bài viết
    5

    mình cũng góp 1 bài nè

    C Code:
    1. #include<stdio.h>
    2. #include<conio.h>
    3. #include<stdlib.h>
    4. void NhapMangRand(int a[],int &n);
    5. void NhapMang(int a[],int &n);
    6. void XuatMang(int a[],int n);
    7. void InterchangeSort(int a[],int n);
    8. void SelectionSort(int a[],int n);
    9. void BubbleSort(int a[],int n);
    10. void ShakerSort(int a[],int n);
    11. void InsertionSort(int a[],int n);
    12. void ShellSort(int a[], int n);
    13. void main()
    14. {
    15.     int a[20],n;
    16.     int choice;
    17.     char c;
    18.     while(choice!=10)
    19.     {
    20.         clrscr();
    21.         printf("\n  +------- NHUNG THUAT TOAN SAP XEP (DAY TANG) -------+");
    22.         printf("\n  | 1. Nhap day so ngau nhien                         |");
    23.         printf("\n  | 2. Nhap day so bang tay                           |");
    24.         printf("\n  | 3. Sap xep doi choi truc tiep (Interchange Sort)  |");
    25.         printf("\n  | 4. Sap xep chon truc tiep (Selection Sort)        |");
    26.         printf("\n  | 5. Sap xep noi bot(Bubble Sort)                   |");
    27.         printf("\n  | 6. Sap xep noi bot cai tien (Shaker Sort)         |");
    28.         printf("\n  | 7. Sap xep chen truc tiep(Insertion Sort)         |");
    29.         printf("\n  | 8. Sap xep do dai buoc giam dan (Shell Sort)      |");
    30.         printf("\n  | 9. Sap xep theo cay (Heap Sort)                   |");
    31.         printf("\n  | 10. Thoat                                         |");
    32.         printf("\n  +---------------------------------------------------+");
    33.         printf("\n     Moi ban chon chuc nang: ");scanf("%d",&choice);
    34.         switch(choice)
    35.         {
    36.             case 1:
    37.             {
    38.                 clrscr();
    39.                 printf("\n      NHAP MANG NGAU NHIEN \n");
    40.                 NhapMangRand(a,n);
    41.                 printf("\n Day so ngau nhien la:");
    42.                 XuatMang(a,n);
    43.                 getch();
    44.             } break;
    45.             case 2:
    46.             {
    47.                 clrscr();
    48.                 printf("\n      NHAP MANG BANG TAY \n");
    49.                 NhapMang(a,n);
    50.                 printf("\n Day so ban da nhap la:");
    51.                 XuatMang(a,n);
    52.                 getch();
    53.             } break;
    54.             case 3:
    55.             {
    56.                 clrscr();
    57.                 printf("\n   SAP XEP DOI CHO TRUC TIEP (INTERCHANGE SORT) \n");
    58.                 printf("\n Day so ban dau:");
    59.                 XuatMang(a,n);
    60.                 InterchangeSort(a,n);
    61.                 printf("\n\n Day so sau khi Sap xep:");
    62.                 XuatMang(a,n);
    63.                 getch();
    64.             } break;
    65.             case 4:
    66.             {
    67.                 clrscr();
    68.                 printf("\n      SAP XEP CHON TRUC TIEP (SELECTION SORT) \n");
    69.                 printf("\n Day so ban dau:");
    70.                 XuatMang(a,n);
    71.                 SelectionSort(a,n);
    72.                 printf("\n\n Day so sau khi Sap xep:");
    73.                 XuatMang(a,n);
    74.                 getch();
    75.             } break;
    76.             case 5:
    77.             {
    78.                 clrscr();
    79.                 printf("\n      SAP XEP NOI BOT (BUBBLE SORT) \n");
    80.                 printf("\n Day so ban dau:");
    81.                 XuatMang(a,n);
    82.                 BubbleSort(a,n);
    83.                 printf("\n\n Day so sau khi Sap xep:");
    84.                 XuatMang(a,n);
    85.                 getch();
    86.             } break;
    87.             case 6:
    88.             {
    89.                 clrscr();
    90.                 printf("\n      SAP XEP NOI BOT CAI TIEN (SHAKER SORT) \n");
    91.                 printf("\n Day so ban dau:");
    92.                 XuatMang(a,n);
    93.                 ShakerSort(a,n);
    94.                 printf("\n\n Day so sau khi Sap xep:");
    95.                 XuatMang(a,n);
    96.                 getch();
    97.             } break;
    98.             case 7:
    99.             {
    100.                 clrscr();
    101.                 printf("\n      SAP XEP CHEN TRUC TIEP (INSERTION SORT) \n");
    102.                 printf("\n Day so ban dau:");
    103.                 XuatMang(a,n);
    104.                 InsertionSort(a,n);
    105.                 printf("\n\n Day so sau khi Sap xep:");
    106.                 XuatMang(a,n);
    107.                 getch();
    108.             } break;
    109.             case 8:
    110.             {
    111.                 clrscr();
    112.                 printf("\n      SAP XEP DO DAI GIAM DAN (SHELL SORT) \n");
    113.                 printf("\n Day so ban dau:");
    114.                 XuatMang(a,n);
    115.                 ShellSort(a,n);
    116.                 printf("\n\n Day so sau khi Sap xep:");
    117.                 XuatMang(a,n);
    118.                 getch();
    119.             } break;
    120.             case 9:
    121.             {
    122.                 clrscr();
    123.                 printf("\n      SAP XEP THEO CAY (HEAP SORT) \n");
    124.                 printf("\n Day so ban dau:");
    125.                 XuatMang(a,n);
    126.                 BubbleSort(a,n);
    127.                 printf("\n\n Day so sau khi Sap xep:");
    128.                 XuatMang(a,n);
    129.                 getch();
    130.             } break;
    131.         }
    132.     }
    133. }
    134. void NhapMangRand(int a[],int &n)
    135. {
    136.     int i;
    137.     printf("\n Day so cua ban co bao nhieu phan tu ?");
    138.     printf("\n\t n="); scanf("%d",&n);
    139.     randomize();
    140.     for(i=0;i<n;i++)
    141.         a[i]=random(20);
    142. }
    143. void NhapMang(int a[],int &n)
    144. {
    145.     int i;
    146.     printf("\n Day so cua ban co bao nhieu phan tu ?");
    147.     printf("\n\t n="); scanf("%d",&n);
    148.     printf("\n Moi ban nhap day so: \n");
    149.     for(i=0;i<n;i++)
    150.     {
    151.         printf("\t a[%d]= ",i);
    152.         scanf("%d",&a[i]);
    153.     }
    154. }
    155. void XuatMang(int a[],int n)
    156. {
    157.     for(int i=0;i<n;i++)
    158.         printf("  %d",a[i]);
    159. }
    160. void swap(int &x,int &y)
    161. {
    162.     int temp;
    163.     temp=x;
    164.     x=y;
    165.     y=temp;
    166. }
    167. void InterchangeSort(int a[],int n)
    168. {
    169.     printf("\n\n _Y Tuong: Doi cho a[i] voi a[j] neu a[i]>a[j] ");
    170.     printf("\n _Code:");
    171.     printf("\n\tvoid InterchangeSort(int a[],int n)\
    172. \n        {                         \
    173. \n            int i,j;              \
    174. \n            for(i=0;i<n-1;i++)    \
    175. \n            for(j=i+1;j<n;j++)    \
    176. \n                if (a[i]>a[j])    \
    177. \n                 swap(a[i],a[j]); \
    178. \n        }\n");
    179.  
    180.     int i,j;
    181.     for(i=0;i<n-1;i++)
    182.         for(j=i+1;j<n;j++)
    183.             if (a[i]>a[j])
    184.                 swap(a[i],a[j]);
    185. }
    186. void SelectionSort(int a[],int n)
    187. {
    188.     printf("\n\n _Y Tuong: Neu a[i]>a[j] thi luu vi tri cua a[j] sau do moi doi cho");
    189.     printf("\n _Code:");
    190.     printf("\n\tvoid SelectionSort(int a[],int n) \
    191. \n        {                      \
    192. \n            int i,j,min;       \
    193. \n            for(i=0;i<n-1;i++) \
    194. \n            {                  \
    195. \n                min=i;         \
    196. \n                for(j=i+1;j<n;j++) \
    197. \n                    if(a[min]>a[j]) min=j; \
    198. \n                    if(i!=min) swap(a[i],a[min]); \
    199. \n            }   \
    200. \n        } \n");
    201.  
    202.     int i,j,min;
    203.     for(i=0;i<n-1;i++)
    204.     {
    205.         min=i;
    206.         for(j=i+1;j<n;j++)
    207.             if(a[min]>a[j]) min=j;
    208.             if(i!=min) swap(a[i],a[min]);
    209.     }
    210. }
    211. void BubbleSort(int a[],int n)
    212. {
    213.     printf("\n\n _Y Tuong: Nhe thi noi len tren hay nang thi chim xuong duoi");
    214.     printf("\n _Code:");
    215.     printf("\n\tvoid BubbleSort(int a[],int n) \
    216. \n        {                          \
    217. \n            int i,j,k,flag;        \
    218. \n            for(i=0;i<n-1;i++)     \
    219. \n            {                      \
    220. \n                k=-1;              \
    221. \n                for(j=n-1;j>i;j--) \
    222. \n                    if(a[j]<a[j-1])\
    223. \n                    {              \
    224. \n                        swap(a[j],a[j-1]); \
    225. \n                        k=j-1;     \
    226. \n                    }              \
    227. \n                    if (k==-1) break; \
    228. \n                    i=k;           \
    229. \n            }                      \
    230. \n        }");
    231.     int i,j,k,flag;
    232.     for(i=0;i<n-1;i++)
    233.     {
    234.         k=-1;
    235.         for(j=n-1;j>i;j--)
    236.             if(a[j]<a[j-1])
    237.             {
    238.                 swap(a[j],a[j-1]);
    239.                 k=j-1;
    240.             }
    241.         if (k==-1) break;
    242.         i=k;
    243.     }
    244. }
    245. void ShakerSort(int a[],int n)
    246. {
    247.     printf("\n\n _Y Tuong: cai tien tu Bubble Sort sap xep day tu dau` va` cuoi' day");
    248.     printf("\n _Code:");
    249.     printf("\n\tvoid ShakerSort(int a[],int n)  \
    250. \n        {                             \
    251. \n            int i,j,k,flag;           \
    252. \n            for(i=0;i<n-1;i++)        \
    253. \n            {                         \
    254. \n                k=-1;                 \
    255. \n                for(j=n-1;j>i;j--)    \
    256. \n                    if(a[j]<a[j-1])   \
    257. \n                        swap(a[j],a[j-1]); \
    258. \n                for(j=i;j<n-i;j++)    \
    259. \n                    if(a[j]>a[j+1])   \
    260. \n                        swap(a[j],a[j+1]); \
    261. \n            }                         \
    262. \n        }");
    263.     int i,j,flag;
    264.     for(i=0;i<n-1;i++)
    265.     {
    266.         for(j=n-1;j>i;j--)
    267.             if(a[j]<a[j-1])
    268.                 swap(a[j],a[j-1]);
    269.         for(j=i;j<n-i;j++)
    270.             if(a[j]>a[j+1])
    271.                 swap(a[j],a[j+1]);
    272.     }
    273. }
    274. void InsertionSort(int a[],int n)
    275. {
    276.     printf("\n\n _Y Tuong: ta co doan tu a[0] den a[i] da co thu tu , xet tu vi tri i+1 tro ve sau va chen vao vi tri thich hop trong day da co thu tu");
    277.     printf("\n _Code:");
    278.     printf("\n\tvoid InsertionSort(int a[],int n)   \
    279. \n        {                                         \
    280. \n            int pos,i,x;                          \
    281. \n            for(i=1;i<n;i++)                      \
    282. \n            {                                     \
    283. \n                x=a[i];                           \
    284. \n                pos=i-1;                          \
    285. \n                while(pos>=0&&a[pos]>x)           \
    286. \n                {                                 \
    287. \n                    a[pos+1]=a[pos];              \
    288. \n                    pos--;                        \
    289. \n                }                                 \
    290. \n                a[pos+1]=x;                       \
    291. \n        }");
    292.     int pos,i,x;
    293.     for(i=1;i<n;i++) //doan a[0] da dc sap xep
    294.     {
    295.         x=a[i]; // luu lai vi tri a[i] de tranh mat gia tri cua a[i] khi ta di chuyen day so
    296.         pos=i-1; // vi tri cuoi cung cua day co thu tu va la vi tri so sanh dau tien
    297.         while(pos>=0&&a[pos]>x)
    298.         {
    299.             a[pos+1]=a[pos];  //doi gia tri cua a[pos] sang phai de cuoi cung chen gia tri cua x vao vi tri thich hop
    300.             pos--;   // vi tri so sanh dang` sau pos
    301.         }
    302.         a[pos+1]=x; // chen x (vong while thoat khi a[pos]<=x vay x phai nam sau vi tri pos tuc pos+1)
    303.     }
    304.  
    305. }
    306. void ShellSort(int a[], int n)
    307. {
    308.     printf("\n\n _Y Tuong: chon k buoc xap sep <=> chia ra cai day con voi do dai h[k] (thuong chon day so nguyen to) sau do dua tre InsertionSort de sap xep");
    309.     printf("\n _Code:");
    310.     printf("\n\tvoid ShellSort(int a[], int n)      \
    311. \n        {                                         \
    312. \n            int i,x,step,len,pos;                 \
    313. \n            int k;                                \
    314. \n            int h[10];                            \
    315. \n            for (step=0;step<k;step++)            \
    316. \n            {                                     \
    317. \n                len=h[step];                      \
    318. \n                for(i=len;i<n;i++)                \
    319. \n                {                                 \
    320. \n                    x=a[i];                       \
    321. \n                    pos=i-len;                    \
    322. \n                    while(pos>=0&&a[pos]>x)       \
    323. \n                    {                             \
    324. \n                        a[pos+len]=a[pos];        \
    325. \n                        pos=pos-len;              \
    326. \n                    }                             \
    327. \n                    a[pos+len]=x;                 \
    328. \n                }                                 \
    329. \n            }                                     \
    330. \n        }");
    331.     int i,x,step,len,pos;
    332.     int k=3;
    333.     int h[3]={5,3,1} ;
    334.     for (step=0;step<k;step++)
    335.     {
    336.         len=h[step];
    337.         for(i=len;i<n;i++)
    338.         {
    339.             x=a[i];
    340.             pos=i-len;
    341.             while(pos>=0&&a[pos]>x)
    342.             {
    343.                 a[pos+len]=a[pos];
    344.                 pos=pos-len;
    345.             }
    346.         a[pos+len]=x;
    347.         }
    348.     }
    349. }
    Đã được chỉnh sửa lần cuối bởi hailoc12 : 13-06-2007 lúc 12:12 AM. Lý do: Đưa source vào tag code

  5. #15
    Ngày gia nhập
    03 2011
    Bài viết
    13

    Mặc định hỏi về bucket sort

    cho mình hỏi về bucket sort với mọi người ơi:
    thầy mình giao bt sắp xếp mảng a có n phần tử có giá trị từ [0, n*n - 1] bằng bucketsort, mình tạo 1 mảng b gồm n*n phần tử, sau đó gán giá trị các phần tử của mảng a bằng chỉ số của mảng b:
    for (i = 0; i < n; i++)
    b[a[i]] = a[i];
    nếu các phần tử của mảng a có giá trị khác nhau thì tét đúng nhưng nếu một vài phần tử mảng a có giá trị trùng nhau thì tét sai, mọi người giúp mình chỗ chèn phần tử từ mảng a vào b với, hic

  6. #16
    Ngày gia nhập
    11 2011
    Bài viết
    4

    Mặc định thuật toán sắp xếp Bubblesort

    Mình cũng có bài viết về thuật toán BubbleSort viết bằng C++(Mình cũng tham khảo thêm ý của thầy giáo nữa).Các bạn tham khảo có gì thiếu sót thì bổ sung cho mình với nhé
    C++ Code:
    1. #include<conio.h>
    2. #include<iostream.h>
    3. #include<string.h>
    4. #include<dos.h>
    5. void nhapday(int *a,int n,char ch)//Nhập dãy số cần sắp xếp
    6.   {for(int i=1;i<=n;i++)
    7.     {cout<<ch<<"["<<i<<"]:";
    8.     cin>>a[i];
    9.     }
    10.   }
    11. void inday(int *a,int n)//In dãy số
    12.   {for(int i=1;i<=n;i++)
    13.     cout<<a[i]<<" ";
    14.     }
    15. void BubbleSort(int *a,int n)//Sắp xếp dãy số theo thuật toán nổi bọt
    16.   {
    17.   int i,j,tg;
    18.   cout<<"\ni  j";
    19.   for(i=1;i<n;i++)
    20.     for(j=n;j>i;j--)
    21.      {if(a[j-1]>a[j])
    22.        {tg=a[j];
    23.        a[j]=a[j-1];
    24.        a[j-1]=tg;
    25.        }
    26.      cout<<"\n"<<i<<"  "<<j<<":";
    27.      inday(a,n);
    28.      delay(1500);
    29.   }
    30.  }
    31. void main()
    32. {int n,i;
    33. int a[100];
    34. clrscr();
    35. cout<<"\nSo phan tu can phai sap xep la:";
    36. cin>>n;
    37. nhapday(a,n,'a');
    38. cout<<"\nDay phan tu vua nhap la:";
    39. inday(a,n);
    40. cout<<"\nQua trinh sap xep la:";
    41. BubbleSort(a,n);
    42. cout<<"\nDay phan tu vua sap xep xong la:";
    43. inday(a,n);
    44. getch();
    45. }

  7. #17
    Ngày gia nhập
    01 2012
    Nơi ở
    hà nôi 2
    Bài viết
    59

    cho mình hỏi là cách chọn chốt của quick sort tại cái thuật toán này phụ thuộc vào chốt nhiều, có cách nào chọn chốt tốt nhất hay không, hay thường chỉ chọn ở đoạn giữa của dãy thôi. Mình mới học C nên không biết nhiều. mong chỉ bảo tận tình
    I'm still a chicken
    rất vui khi được làm quen với mọi người ^_^ http://www.facebook.com/chung.v.nguyen.14

  8. #18
    Ngày gia nhập
    05 2010
    Bài viết
    29

    Cài đặt sắp xếp chèn (Insertion sort)

    Nhờ các bác góp ý xem đúng chưa

    C Code:
    1. void hoanvi(int *a, int *b)
    2. {
    3.  int temp;
    4.  temp=*a;
    5.  *a=*b;
    6.  *b=temp;
    7. }
    8.  
    9. void insertion_sort(int a[], int n)
    10. {
    11.  for(int i=1;i<n;++i)
    12.  {
    13.   int j=i;
    14.   while((a[j]<a[j-1])&&(j>0))
    15.     {
    16.      hoanvi(&a[j],&a[j-1]);
    17.      j--;
    18.     }
    19.  }
    20. }

  9. #19
    Ngày gia nhập
    01 2012
    Nơi ở
    hà nôi 2
    Bài viết
    59

    bổ sung cho heap sort cách tính vị trí của nút cha và con( nút gốc và lá). Theo bài của chủ thread thì gốc cây nhị phân tính từ 1 do vậy nút cha ở phần tử thứ i là i/2.
    Nếu nút gốc đỉnh tính từ 0 và chỉ số các nút là từ 0->n-1 thì nút(lá) trái ở vị trị thứ i là 2*i+1 phải là 2*i+2, còn nút cha của phần thứ i là (i-1)/2
    Nếu nút gốc đỉnh tính từ 1 và chỉ số các nút tính từ 1->n thì nút(lá) trái ở vị trị thứ i là 2*i phải là 2*i+1, còn nút cha của phần thứ i là i/2
    I'm still a chicken
    rất vui khi được làm quen với mọi người ^_^ http://www.facebook.com/chung.v.nguyen.14

  10. #20
    Ngày gia nhập
    04 2013
    Nơi ở
    Hà Nội
    Bài viết
    4

    Trích dẫn Nguyên bản được gửi bởi PoPoPoPo Xem bài viết
    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.
    có 7 thuật toán thôi ak? MÌnh nhớ có 8 cái tương đối nổi tiếng mà

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