Information Technology VietNam

Bạn có muốn phản ứng với tin nhắn này? Vui lòng đăng ký diễn đàn trong một vài cú nhấp chuột hoặc đăng nhập để tiếp tục.

3 posters

    Code các giải thuật về sắp xếp

    Vy Thanh Định
    Vy Thanh Định
    Web Master
    Web Master


    Giới tính : Nam Bài gửi : 228
    Tổng Điểm : 544
    Điểm Thưởng : 16
    Sinh Nhật : 19/05/1990 Bị Dụ Dỗ : 11/09/2009
    Tuổi : 34

    Code các giải thuật về sắp xếp Empty Code các giải thuật về sắp xếp

    Bài gửi by Vy Thanh Định 8/11/2009, 09:56

    Bubble sort

    Code:

    #include <stdio.h>
    #include <stdlib.h>
    #include <conio.h>

    #define MAXLIST 200
    #define TRUE 1
    #define FALSE 0


    int nodes[MAXLIST];

    void bubblesort(int nodes[], int n)
    {
      int temp, i, j;
      int codoicho = TRUE;

      for(i = 1; i < n && codoicho == TRUE; i++)
      {
          codoicho = FALSE;
          for(j = 0; j < n-i; j++)
             if(nodes[j] > nodes[j+1])
             {
               codoicho = TRUE;
               temp = nodes[j];
               nodes[j] = nodes[j+1];
               nodes[j+1] = temp;
             }
      }
    }

    void main()
    {
      int chucnang;
      char c;

    //  clrscr();

      do
      {
          printf("\n\n\tBUBBLE SORT");
          printf("\n\nCac chuc nang cua chuong trinh:\n");
          printf("  1: Tao danh sach voi %d so ngau nhien\n", MAXLIST);
          printf("  2: Bubble Sort\n");
          printf("  3: Duyet danh sach\n");
          printf("  0: Ket thuc chuong trinh\n");
          printf("Chuc nang ban chon: ");
          scanf("%d", &chucnang);
          switch(chucnang)
          {
             case 1:
             {
               for(int i = 0; i < MAXLIST; i++)
                   nodes[i] = rand(1000);
               printf("\nDa tao xong danh sach voi %d so ngau nhien", MAXLIST);
               break;
             }
             case 2:
             {
               bubblesort(nodes, MAXLIST);
               printf("\nDa sap xep xong danh sach theo giai thuat Bubble Sort");
               break;
             }
             case 3:
             {
               printf("\nDUYET DANH SACH:\n");
               for(int i = 0; i < MAXLIST; i++)
                   printf("%8d", nodes[i]);
               break;
             }
          }
      } while(chucnang != 0);
    }

    Đã test rất kỹ, yên tâm mà mò nha Very Happy
    Vy Thanh Định
    Vy Thanh Định
    Web Master
    Web Master


    Giới tính : Nam Bài gửi : 228
    Tổng Điểm : 544
    Điểm Thưởng : 16
    Sinh Nhật : 19/05/1990 Bị Dụ Dỗ : 11/09/2009
    Tuổi : 34

    Code các giải thuật về sắp xếp Empty Re: Code các giải thuật về sắp xếp

    Bài gửi by Vy Thanh Định 8/11/2009, 10:00

    Quick Sort

    Code:

    #include <stdio.h>
    #include <stdlib.h>
    #include <conio.h>

    #define MAXLIST 200
    #define TRUE 1
    #define FALSE 0

    // Khai bao danh sach ke chua cac nut can sap xep
    int nodes[MAXLIST];

    void partition(int nodes[], int low, int up, int *pivot)
    {
      int nuttruc, l, u, temp;
      nuttruc = nodes[low];  // Chon phan tu dau lam truc
      l = low;
      u = up;
      while(l < u)
      {
          // quet len
          while(nodes[l] <= nuttruc && l < up)
             l++;

          // quet xuong
          while(nodes[u] > nuttruc)
             u--;

          if(l < u)
          {
             // Doi cho hai phan tu tai hai vi tri down va up
             temp = nodes[l];
             nodes[l] = nodes[u];
             nodes[u] = temp;
          }
      }
      // Doi cho phan tu truc va phan tu tai vi tri up
      nodes[low] = nodes[u];
      nodes[u] = nuttruc;
      *pivot = u;
    }

    void quicksort(int nodes[], int low, int up)
    {
      int pivot;
      if(low >= up)                        // dieu kien dung
          return;
      if(low < up)                        // buoc de qui
      {
          partition(nodes, low, up, &pivot);
          quicksort(nodes, low, pivot-1);
          quicksort(nodes, pivot+1, up);
      }
    }

    // Chuong trinh chinh
    void main()
    {
      int chucnang;
      char c;

    //  clrscr();

      do
      {
          // menu chinh cua chuong trinh
          printf("\n\n\tQUICKSORT");
          printf("\n\nCac chuc nang cua chuong trinh:\n");
          printf("  1: Tao danh sach voi %d so ngau nhien\n", MAXLIST);
          printf("  2: Quick Sort\n");
          printf("  3: Duyet danh sach\n");
          printf("  0: Ket thuc chuong trinh\n");
          printf("Chuc nang ban chon: ");
          scanf("%d", &chucnang);
          switch(chucnang)
          {
             case 1:
             {
               for(int i = 0; i < MAXLIST; i++)
                   nodes[i] = rand(1000);
               printf("\nDa tao xong danh sach voi %d so ngau nhien", MAXLIST);
               break;
             }
             case 2:
             {
               quicksort(nodes, 0, MAXLIST-1);
               printf("\nDa sap xep xong danh sach theo giai thuat Quick Sort");
               break;
             }
             case 3:
             {
               printf("\nDUYET DANH SACH:\n");
               for(int i = 0; i < MAXLIST; i++)
                   printf("%8d", nodes[i]);
               break;
             }
          }
      } while(chucnang != 0);
    }
    Vy Thanh Định
    Vy Thanh Định
    Web Master
    Web Master


    Giới tính : Nam Bài gửi : 228
    Tổng Điểm : 544
    Điểm Thưởng : 16
    Sinh Nhật : 19/05/1990 Bị Dụ Dỗ : 11/09/2009
    Tuổi : 34

    Code các giải thuật về sắp xếp Empty Re: Code các giải thuật về sắp xếp

    Bài gửi by Vy Thanh Định 8/11/2009, 10:02

    Merge sort

    Code:

    #include <stdio.h>
    #include <stdlib.h>
    #include <conio.h>

    #define MAXLIST 200
    #define TRUE 1
    #define FALSE 0

    int nodes[MAXLIST];

    void mergesort(int nodes[], int n)
    {
      int i, j, k, low1, up1, low2, up2, size;
      int dstam[MAXLIST];
      size = 1;
      while(size < n)
      {
          low1 = 0;
          k = 0;
          while(low1+size < n)
          {
             low2 = low1+size;
             up1 = low2-1;
             up2 = (low2+size-1 < n) ? low2+size-1 : n-1;
             for(i = low1, j = low2; i <= up1 && j <= up2; k++)
               if(nodes[i] <= nodes[j])
                   dstam[k] = nodes[i++];
               else
                   dstam[k] = nodes[j++];
             for(; i <= up1; k++)
               dstam[k] = nodes[i++];
             for(; j <= up2; k++)
               dstam[k] = nodes[j++];
             low1 = up2+1;
          }
          for(i = low1; k < n; i++)
             dstam[k++] = nodes[i];
          for(i = 0; i < n; i++)
             nodes[i] = dstam[i];
          size *= 2;
      }
    }

    // Chuong trinh chinh
    void main()
    {
      int chucnang;
      char c;

    //  clrscr();

      do
      {
          // menu chinh cua chuong trinh
          printf("\n\n\tMERGE SORT");
          printf("\n\nCac chuc nang cua chuong trinh:\n");
          printf("  1: Tao danh sach voi %d so ngau nhien\n", MAXLIST);
          printf("  2: Merge Sort\n");
          printf("  3: Duyet danh sach\n");
          printf("  0: Ket thuc chuong trinh\n");
          printf("Chuc nang ban chon: ");
          scanf("%d", &chucnang);
          switch(chucnang)
          {
             case 1:
             {
               for(int i = 0; i < MAXLIST; i++)
                   nodes[i] = rand(1000);
               printf("\nDa tao xong danh sach voi %d so ngau nhien", MAXLIST);
               break;
             }
             case 2:
             {
               mergesort(nodes, MAXLIST);
               printf("\nDa sap xep xong danh sach theo giai thuat Merge Sort");
               break;
             }
             case 3:
             {
               printf("\nDUYET DANH SACH:\n");
               for(int i = 0; i < MAXLIST; i++)
                   printf("%8d", nodes[i]);
               break;
             }
          }
      } while(chucnang != 0);
    }
    Vy Thanh Định
    Vy Thanh Định
    Web Master
    Web Master


    Giới tính : Nam Bài gửi : 228
    Tổng Điểm : 544
    Điểm Thưởng : 16
    Sinh Nhật : 19/05/1990 Bị Dụ Dỗ : 11/09/2009
    Tuổi : 34

    Code các giải thuật về sắp xếp Empty Re: Code các giải thuật về sắp xếp

    Bài gửi by Vy Thanh Định 8/11/2009, 10:03

    Heap sort

    Code:

    #include <stdio.h>
    #include <stdlib.h>
    #include <conio.h>

    #define MAXLIST 200
    #define TRUE 1
    #define FALSE 0

    int nodes[MAXLIST];

    void heapsort(int nodes[], int n)
    {
      int k, x, s, f, ivalue;

      // chuyen danh sach nodes[] thanh heap
      for(k = 1; k < n; k++)
      {
          x = nodes[k]; // Nut can them vao heap

          // tac vu insert(nodes[], k, x)
          s = k;            // s la nut con
          f = (s-1)/2;      // f la nut cha
          while(s > 0 && nodes[f] < x)
          {
             nodes[s] = nodes[f]; // keo nut < x xuong mot muc
             s = f;
             f = (s-1)/2;
          }
          nodes[s] = x;      // dien nut x vao vi tri phu hop
      }

      // lan luot xoa nodes[0] tren heap, copy no ve vi tri thich hop tren ds
      for(k = n-1; k > 0; k--)
      {
          // tac vu removeroot(nodes[], k+1)
          ivalue = nodes[k]; // ivalue la nut hien tai o vi tri k
          nodes[k] = nodes[0];    // chuyen nut goc xuong vi tri k

          f = 0;  // f la nut cha, s la nut con lon hon
          // s = largeson(0, k-1)
          if(k == 1)
             s = -1;
          else
             s = 1;
          if(k > 2 && nodes[2] > nodes[1])
             s = 2;
          while(s >= 0 && ivalue < nodes[s])
          {
             nodes[f] = nodes[s];  // doi nut con lon hon len 1 muc
             f = s;

             // s = largeson(f, k-1)
             s = 2*f+1;
             if(s+1 <= k-1 && nodes[s] < nodes[s+1])
               s = s+1;
             if(s > k-1)
               s = -1;
          }
          nodes[f] = ivalue;
      }
    }

    // Chuong trinh chinh
    void main()
    {
      int i, chucnang;
      char c;

      clrscr();

      do
      {
          // menu chinh cua chuong trinh
          printf("\n\n\tHEAPSORT");
          printf("\n\nCac chuc nang cua chuong trinh:\n");
          printf("  1: Tao danh sach voi %d so ngau nhien\n", MAXLIST);
          printf("  2: Heap Sort\n");
          printf("  3: Duyet danh sach\n");
          printf("  0: Ket thuc chuong trinh\n");
          printf("Chuc nang ban chon: ");
          scanf("%d", &chucnang);
          switch(chucnang)
          {
             case 1:
             {
               for(i = 0; i < MAXLIST; i++)
                   nodes[i] = rand(1000);
               printf("\nDa tao xong danh sach voi %d so ngau nhien", MAXLIST);
               break;
             }
             case 2:
             {
               heapsort(nodes, MAXLIST);
               printf("\nDa sap xep xong danh sach theo giai thuat Heap Sort");
               break;
             }
             case 3:
             {
               printf("\nDUYET DANH SACH:\n");
               for(i = 0; i < MAXLIST; i++)
                   printf("%8d", nodes[i]);
               break;
             }
          }
      } while(chucnang != 0);
    }
    ltv2009
    ltv2009
    Top Poster
    Top Poster


    Giới tính : Nữ Bài gửi : 198
    Tổng Điểm : 450
    Điểm Thưởng : 5
    Sinh Nhật : 17/10/1990 Bị Dụ Dỗ : 10/10/2009
    Tuổi : 34

    Code các giải thuật về sắp xếp Empty Re: Code các giải thuật về sắp xếp

    Bài gửi by ltv2009 11/11/2009, 00:52

    Ái chà thanks nha. Cố gắng phát huy nà Very Happy
    kocogi
    kocogi
    Member
    Member


    Giới tính : Nam Bài gửi : 22
    Tổng Điểm : 24
    Điểm Thưởng : 0
    Sinh Nhật : 18/03/1990 Bị Dụ Dỗ : 26/11/2009
    Tuổi : 34

    Code các giải thuật về sắp xếp Empty Re: Code các giải thuật về sắp xếp

    Bài gửi by kocogi 26/11/2009, 21:55

    Tự sướng :
    Code:

    #include <stdio.h>
    #include <conio.h>
    #include <mem.h>
    #define MAX 1000
    int a[MAX];
    int b[MAX];
    int n;

    void swap(int *a,int *b){
        int t = *a;
        *a = *b;
        *b = t;
    }

    void xuat(int *a){
        int i;
        for (i=0;i<n;i++) printf(" %d",a[i]);
        printf("\n");
    }

    void selectionSort(){
        memmove(b,a,sizeof(b));
        printf("Selection Sort : \n");
        int i,j;
        for (i=0;i<n-1;i++)
        for (j=i+1;j<n;j++)
            if (b[i] > b[j]) swap(&b[i],&b[j]);
        xuat(b);
    }

    void bubbleSort(){
        memmove(b,a,sizeof(b));
        printf("Bubble Sort : \n");
        int i,j;
        for (i=0;i<n-1;i++)
        for (j=n-1;j>i;j--)
            if (b[j] < b[j-1]) swap(&b[j],&b[j-1]);
        xuat(b);
    }

    void shakerSort(){
        memmove(b,a,sizeof(b));
        printf("Shaker Sort : \n");
        printf("Day ban dau :");
        xuat(b);
        int left,right,k;
        int j;
        left = 0; right = n-1; k = n-1;
        while (left < right){
              for (j=right;j>left;j--)
                  if (b[j] < b[j-1]){
                      swap(&b[j],&b[j-1]);
                      k = j;
                  }
              printf("Sau khi don gia tri min ve phia ben trai :");
              xuat(b);
              left = k;
              for (j=left;j<right;j++)
                  if (b[j] > b[j+1]){
                      swap(&b[j],&b[j+1]);
                      k = j;
                  }
              right = k;
              printf("Sau khi don gia tri max ve phia ben phai :");
              xuat(b);
        }
        printf("Day sau khi sap xep :\n");
        xuat(b);
    }


    void insertionSort(){
        memmove(b,a,sizeof(b));
        printf("Insertion Sort : \n");
        int i,j;
        int x;
        for (i=1;i<n;i++){
            x = b[i];
            j = i-1;
            while (j >= 0 && x < b[j]){
                  b[j+1] = b[j];
                  j--;
            }
            b[j+1] = x;
        }
        xuat(b);
    }

    void binaryInsertionSort(){
        memmove(b,a,sizeof(b));
        printf("Binary Insertion Sort : \n");
        int i,j;
        int x;
        int lo,hi,mid;
        for (i=1;i<n;i++){
            x = b[i];
            lo = 0; hi = i-1;
            do
            {
                  mid = (lo + hi)/2;
                  if (x > b[mid]) lo = mid + 1;
                  else hi = mid - 1;
            }
            while (lo <= hi);
            for (j=i;j>lo;j--) b[j] = b[j-1];
            b[lo] = x;
    //        xuat(b);
        }
        xuat(b);
    }

    void shellSort(){
        memmove(b,a,sizeof(b));
        printf("Shell Sort : \n");
        int i,j,h;
        int x;
        h = n/2;
        while (h != 0){
              for (i=h;i<n;i++){
                  x = b[i];
                  j = i-h;
                  while (j >= 0 && b[j] > x){
                        b[j+h] = b[j];
                        j -= h;
                  }
                  b[j+h] = x;
              }
              h = h/2;
        }
        xuat(b);
    }

    void adjust(int root,int endnode){
        int t = b[root];
        int r;
        while (root*2+1 <= endnode){
              r = root*2+1;
              if (r < endnode && b[r] < b[r+1]) r++;
              if (t >= b[r]) break;
              b[root] = b[r];
              root = r;
        }
        b[root] = t;
    }

    void heapSort(){
        memmove(b,a,sizeof(b));
        printf("Heap Sort : \n");
        int r,i,t;
        for (r=(n-1)/2;r>=0;r--) adjust(r,n-1);
        for (i=n-1;i>0;i--){
            t = b[0];
            b[0] = b[i];
            b[i] = t;
            adjust(0,i-1);
        }
        xuat(b);
    }

    void qsort(int lo,int hi){
        int i,j,t;
        int k = b[(lo+hi)/2];
        i = lo; j = hi;
        do
        {
            while (i < hi && b[i] < k) i++;
            while (j > lo && b[j] > k) j--;
            if (i <= j){
                t = b[i];
                b[i] = b[j];
                b[j] = t;
                i++; j--;
            }
        }
        while (i <= j);
        if (lo < j) qsort(lo,j);
        if (i < hi) qsort(i,hi);
    }

    void quickSort(){
        memmove(b,a,sizeof(b));
        printf("Quick Sort : \n");
        qsort(0,n-1);
        xuat(b);
    }

    void merge(int src[],int des[],int fi1,int fi2,int len){
        int la1,la2;
        int ndes = fi1;
        la1 = fi1+len;
        la2 = fi2+len;
        if (la2 > n) la2 = n;
        while (fi1 < la1 && fi2 < la2){
              if (src[fi1] < src[fi2])
                  des[ndes] = src[fi1++];
              else
                  des[ndes] = src[fi2++];
              ndes++;
        }
        if (fi1 < la1) memmove(des+ndes,src+fi1,(la1-fi1)*sizeof(b[0]));
        else memmove(des+ndes,src+fi2,(la2-fi2)*sizeof(b[0]));
    }

    void mergeByLen(int src[],int des[],int len){
        int i,j;
        for (i=0;i+len<n;i+=(len*2))
        {
    //        printf("%d %d\n",i,i+len);
            merge(src,des,i,i+len,len);
        }
    //    printf("%d\n",i);
    //    xuat(des);
    }

    void mergeSort(){
        memmove(b,a,sizeof(b));
        int t[MAX];
        printf("Merge Sort : \n");
    //    xuat(b);
        int flag = 1;
        int len = 1;
        while (len < n){
              if(flag) mergeByLen(b,t,len);
              else mergeByLen(t,b,len);
              len = len*2;
              flag = !flag;
        }
        if (!flag) memcpy(b,t,n*sizeof(b[0]));
        xuat(b);
    }

    int main(){
        int i;
        FILE *fi = fopen("sort.in","r");
        fscanf(fi,"%d",&n);
        for (i=0;i<n;i++) fscanf(fi,"%d",&a[i]);
        fclose(fi);
        printf("Day ban dau : \n");
        xuat(a);
        selectionSort();
        bubbleSort();
        insertionSort();
        binaryInsertionSort();
        shellSort();
        heapSort();
        quickSort();
        mergeSort();
        for (i=0;i<79;i++) printf("_");
        printf("\n");
        printf("Giai thich shaker sort :\n");
        shakerSort();
        getch();
        return 1;
    }

    Sponsored content


    Code các giải thuật về sắp xếp Empty Re: Code các giải thuật về sắp xếp

    Bài gửi by Sponsored content


      Hôm nay: 25/11/2024, 13:20